Алгоритмы. кругом алгоритмы!

(Вместо предисловия)

Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлен, узнав, что всю жизнь пользуется прозой. Мы с Вами, дорогой наш читатель, тоже можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов. Мы буквально окружены тесным кольцом алгоритмов, не сознавая, разумеется, этого и, по существу, не зная даже, что такое алгоритм.

В каждодневной жизни человеку приходится решать большое число разного рода задач, в широком смысле этого слова, не только математических или физических, которые требуют применения определенных алгоритмов.

Когда мы переходим улицу на регулируемом светофором перекрестке, мы выполняем определенный алгоритм, когда же переходим улицу в месте, не регулируемом светофором, выполняем другой алгоритм (эти алгоритмы заданы правилами уличного движения). Когда мы вытачиваем деталь на станке, то выполняем определенный алгоритм. Когда приготовляем чай, пользуемся определенным алгоритмом (иногда заданным инструкцией, напечатанной на упаковке). Когда медицинская сестра берет у нас кровь из пальца на анализ, она исполняет определенный алгоритм, и когда она делает нам инъекцию, то опять исполняет определенный алгоритм (этим алгоритмам ее обучали в медицинском училище). И когда мы берем книги в библиотеке, мы выполняем определенные правила пользования библиотечными книгами, т. е. тоже определенный алгоритм. И когда.

Разве возможно перечислить все задачи, при решении которых мы исполняем определенные алгоритмы? Одна школьная математика содержит огромное разнообразие алгоритмов, начиная от алгоритмов выполнения арифметических действий над натуральными числами, дробями и заканчивая алгоритмами решения всякого рода уравнений, неравенств, систем уравнений и т. д. Хотя, разумеется, мы очень редко применяем слово «алгоритм». В самой математике^ где возникло понятие алгоритма, многие, столетия разрабатывались алгоритмы для решения все новых и новых классов задач и при этом мате-

матики не задумывались над тем, что такое алгоритм.

Действительно, если найден общий метод решения любой задачи из нового класса задач, нам незачем задумываться над вопросом, является ли этот метод алгоритмом. Метод есть и мы его применяем к любой задаче данного класса задач, для которого он предназначен. Так формулу корней квадратного уравнения мы используем при решении любого квадратного уравнения. Интуитивно ясно, что данная формула задает общий метод (алгоритм) решения любого квадратного уравнения.

Почему же в течение многих веков в математике, где все строго определяется и доказывается, обходились лишь интуитивным понятием алгоритма?

Один из создателей математических теорий алгоритмов советский математик А. А. Марков (1903— 1979) считал, что это было допустимо, пока термин «алгоритм» встречался в математике лишь в высказываниях следующего типа: «Для решения таких-то задач имеется алгоритм, и вот в чем он состоит».

По той же причине интуитивное понятие алгоритма достаточно и когда ставится вопрос о переводе уже имеющегося алгоритма в программу для решения задачи на ЭВМ. Программа — это лишь запись алгоритма на языке, понимаемом данной ЭВМ.

В математике часто возникают так называемые алгоритмические проблемы, когда требуется найти единый метод (алгоритм) для решения любой задачи из данного класса однотипных задач. Алгоритмические проблемы возникали и решались в различных областях математики на протяжении всей ее истории. Однако в первые десятилетия XX века накопилось много классов задач, для решения которых алгоритма найти не удавалось. Усилия, прилагавшиеся к нахождению алгоритмов решения этих классов задач, привели к мысли: а вдруг для того или иного класса просто невозможно найти алгоритм, т. е. искомый алгоритм не существует?

Если это действительно так, то необходимо прекратить поиск, ибо безнадежно искать то, чего нет. Но тогда возникает необходимость в доказательстве несуществования искомого алгоритма. А чтобы доказать несуществование алгоритма для решения некоторого класса задач, нужно уже знать точно, что такое алгоритм, т. е. надо перевести интуитивное понятие алгоритмов в точное, математическое понятие.

В рамках математической логики в 30-х годах

XX века было выработано точное определение понятия алгоритма, причем были построены различные варианты математического уточнения этого понятия, иными словами, различные математические теории алгоритмов. Благодаря этому удалось обнаружить неразрешимые алгоритмические проблемы, т. е. несуществование соответствующих алгоритмов. Теперь, когда не удается найти алгоритм для некоторого класса задач, можно попытаться доказать, что искомый алгоритм не существует.

Слово «алгоритм» все чаще употребляется все большим числом людей самых различных профессий, все чаще появляется на страницах печати, упоминается в связи с использованием ЭВМ, проникло и в школьное обучение. Этим словом обозначается одно из фундаментальных понятий современной математики и информатики.

Для изучения математики и информатики в рамках школьных программ, обязательных для всех учащихся, вполне достаточно интуитивного понятия алгоритма. Однако для тех учащихся VIII —XI классов, которые интересуются этими предметами, для любителей математики и информатики будет не только интересно, но и полезно более глубокое изучение понятия алгоритма, включающее его математическое уточнение.

Озаглавив эту книгу вопросом «Что такое алгоритм?», авторы ставят перед собой две цели: прежде всего закрепить и несколько обобщить уже имеющиеся у Вас интуитивные представления о том, \что такое алгоритм, а затем ознакомить Вас с двумя математическими уточнениями этого понятия (в виде нормального алгоритма Маркова и машины Тьюринга).

В соответствии с поставленными целями содержание книги разделено на три части.

В первой части разъясняется на примерах из школьной математики, что обычно понимают под алгоритмом, какими свойствами обладает любой алгоритм, каковы основные виды алгоритмов. Рассматриваются три формы представления (задания) алгоритмов: с помощью словесного предписания, блок-схемы и алгоритмической записи, причем показывается эквивалентность этих форм переводом одной формы в другую.

Вторая часть книги посвящена двум упомянутым выше математическим уточнениям понятия алгоритма. Знакомство с точным, математическим понятием

алгоритма способствует и лучшему, правильному усвоению интуитивного понятия и его приложений. Но оно имеет и другое, не менее важное, назначение. Понятие алгоритма в виде идеализированной, допускающей точное математическое определение машины Тьюринга, предшествовавшей реальным ЭВМ, уже знакомит с принципами работы этих машин.

В заключительной части книги рассматриваются приложения алгоритмов к играм, к решению некоторых экономических задач, к программированию.

Уважаемый читатель! Авторы хотели бы особо подчеркнуть, что предлагаемая Вам книга не предназначена для легкого чтения. Ее нужно читать с бумагой и карандашом в руках, а точнее, ее нужно изучать, стараясь при этом самостоятельно решать все предлагаемые задачи.

Мы уверены в том, что труд, который Вы затратите при чтении этой книги, принесет пользу.

Желаем Вам успехов!

Авторы