Введение
Математические основы информатики — сочетание слов странное, с какой стороны на него ни посмотри.
Если это про применение математических методов в информатике — а об этом, безусловно, предстоит вести речь, — то почему нет, например, математических основ физики или химии, где математика весьма изощренно используется уже столетия?
Если о том, что информатика как научная теория своим происхождением и развитием обязана математике, то, как повзрослевшее дитя, она давно уже выпорхнула из родового гнездышка, обзавелась пестрым оперением информационных технологий — и стоит ли поминать в этой ситуации старушку-мать, т.е. математику. Современное определение информатики как науки, изучающей информационные процессы в природе, технике и обществе, вообще не содержит и намека на какую-то связь с математикой.
Математические основы информатики
Разберемся по порядку. Основные информационные процессы, как известно, — это получение, хранение, передача и обработка информации. Именно их изучение и представляет собой основную цель информатики. Надо только еще сказать, что акцент делается на автоматизации этих процессов. Не случайно бытует мнение, что сам термин ИНФОРМАТИКА происходит от соединения слов ИНФОРмация и автоМАТИКА. Без указанного акцента информатика неизбежно становится сборищем фрагментов других научных дисциплин: семиотики, изучающей знаковые системы, лингвистики, изучающей закономерности языка как средства передачи информации, психологии, изучающей, в частности, процессы обработки информации человеком, этологии, изучающей поведение животных, архивоведения, формулирующего правила хранения информации, библиологии, занимающейся организацией хранения и поиска информации, и т.д.1
Получение информации
Пока человек получает информацию непосредственно из окружающего мира с помощью своих органов чувств, никакой автоматизации, а значит, и никакой информатики в этом нет. Но, для того чтобы сохранить эту информацию, чтобы передать ее другим людям (даже если это только его первобытные соплеменники), чтобы осмыслить ее, нужно тем или иным способом зафиксировать информацию. Возникает потребность в знаковой системе и, следовательно, в способах кодирования информации посредством такой системы. Постепенно выкристаллизовывались понятия языка и алфавита. Естественные языки, т.е. языки человеческого общения, не формализованы, а значит, и автоматизация представления информации с помощью таких языков была задачей неразрешимой. Первые существенные продвижения в формализации естественных языков связаны со становлением структурной лингвистики и знаменитыми именами Хомского, Щербы и др. Тем не менее и сегодня проблема формализации естественных языков далека от своего решения. Вполне возможно, что она просто неразрешима.
Какой же язык стал первым в истории человечества формализованным языком? Язык записи натуральных чисел. Четко определенный алфавит, состоящий из 10 цифр, четко фиксированные правила записи чисел с помощью этих цифр — записью натурального числа называется любая упорядоченная последовательность цифр, не начинающаяся с 0. Но, пожалуй, самое главное — однозначно определен смысл каждой такой записи: мы точно знаем, какое натуральное число она обозначает. Эти три свойства и указывают на формальный характер данного языка2. Ничего подобного мы не можем сказать о многих словах, скажем, русского языка. Что обозначает слово “лук”, или слово “звезда”, или слово “коса”?
Этот формальный язык впоследствии был расширен для записи обыкновенных, а затем и десятичных дробей, и, наконец, вещественных и даже комплексных чисел.
Итак, первые эффективные средства и методы формального кодирования информации оказались разработанными именно в математике. Информатика естественно восприняла их. Более того, соображения чисто технического характера привели к тому, что в алфавите формального языка, предназначенного для фиксации произвольной информации, осталось всего два символа, которые традиционно обозначают цифрами 0 и 1. Но информатика поставила в вопросах кодирования принципиально новые задачи: разработка кодов, предотвращающих искажение информации во время передачи по каналам связи, создание экономичных кодов (т.е. таких, которые для передачи или сохранения информации требуют минимального числа кодирующих символов), разработка методов кодирования, защищающих информацию от несанкционированного проникновения. Отвечая на эти вызовы, математики начали развивать методы, позволяющие решить эти задачи.
Автоматизация процесса обработки информации также требовала формального представления обрабатываемой информации. Формальную обработку информации естественно представлять себе как преобразование одного сообщения, записанного на формальном языке, в другое сообщение, записанное на том же языке. Для нас запись “14 + 17” полна содержательно смысла: она показывает, что к каким-то 14 предметам надо добавить еще 17. И ответ мы можем получить разными способами. Важно же, однако, то, что преобразовывать это сообщение в ответ, т.е. в сообщение 31, можно поручить автоматическому устройству, для которого составлена соответствующая инструкция. Как известно, такая инструкция обычно состоит из указания последовательности производимых действий и называется алгоритмом. Именно в математике, в действиях над числами появляются первые алгоритмы, в том числе знаменитый алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел.
Тем самым, автоматизируемая, т.е. формальная, обработка информации требует создания подходящего алгоритма. С точки зрения информатики алгоритмы вовсе не обязаны быть направленными на решение именно числовых задач. Обрабатывать можно любые сообщения, записанные на некотором языке. Например, можно попросить автомат заменить в тексте слово “детектив” на слово “роман”. Формальный подход здесь диктует нам не интересоваться, что произойдет со смыслом текста, подвергшегося такой обработке. Важно лишь то, что сам процесс такой замены полностью формализуем.
И снова информатика ставит задачи, связанные с существованием алгоритмов, исследованием их свойств, оценкой эффективности, доказательством правильности работы. Математическая подоплека кодирования информации и здесь естественным образом трансформирует эти задачи в математические3.
Эти и другие вопросы привели к тому, что в математике образовалось направление, названное дискретной математикой. Сегодня это самостоятельная бурно развивающаяся весьма обширная и разнообразная область математики. Те ее достижения, которые непосредственно связаны с информационными процессами, и образуют так называемые “математические основы информатики”.
А что же школьная математика? Имеется ли в ней место этим вопросам? Конечно, нет. Ведь курс школьной математики сформировался (и это остается краеугольным камнем его сегодняшней идеологии) как курс, обеспечивающий другие школьные предметы — в первую очередь физику — математическим инструментарием. У кого, к примеру, в реальной жизни хоть раз возникла необходимость решать квадратное уравнение или исследовать поведение какой-либо тригонометрической функции? Думаю, что практически ни у кого. Но квадратичная функция и квадратные уравнения нужны для того, чтобы в физике описывать равноускоренное движение, в частности, движение тела у поверхности Земли. А тригонометрические функции нужны для описания колебательных и периодических процессов. Информатика в школу пришла поздно — в середине 80-х годов. И пришла она в заключительное звено школьного образования — 10-е и 11-е классы. Для изложения ее математических основ ни времени, ни места в курсе школьной математики уже нет.
Конечно, если мы говорим о базовом курсе информатики, в котором едва-едва удается представить основные положения этой науки и познакомить с элементами информационных компьютерных технологий, то математические основы информатики вряд ли будут в нем адекватно востребованы. Но если говорить об информатике как профильном курсе, который ориентирован на знание, понимание и умение применять фундаментальные аспекты информатики, то без изучения математических основ этого добиться невозможно.
В наших лекциях речь пойдет именно о таких основах. И начнем мы, естественно, с вопросов, связанных с кодированием информации.
Разумеется, мы предполагаем, что читатель осведомлен, что в компьютере любая информация кодируется словами двухсимвольного алфавита, текстовая информация кодируется посредством 8-битного ASCII или 16-битного Unicode, числа записываются в двоичной системе счисления, а также умеют переводить числа из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную и обратно. Всю необходимую информацию по этим вопросам можно найти в любом учебнике по базовому куру информатики для средней школы.
Источник — http://inf.1september.ru/2007/17/01.htm
Автор — Гейн Александр Георгиевич