Введение в теорию алгоритмов

История возникновения теории алгоритмов. Определение понятия "Алгоритм", основные требования, предъявляемые к алгоритму. Классификации алгоритмических моделей. Машина Поста.

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

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

Несколько примеров интуитивного понятия алгоритма: (с4 –с5)

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

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

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

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату».

(А. Марков)

Различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд общих требований (формальные свойства алгоритмов) (с6)

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

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

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

Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.

Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

Итак, долгое время понятие алгоритма считалось само собой разумеющимся.

Математика привыкла к тому, что задачи, которые она ставила постепенно решались, но как раз, в то время, возникла идея что ряд проблем не имеет решения (не просто они пока не известны, а не имеет вообще) т.е. существуют неразрешимые задачи. Нет алгоритма их решения.

А как доказать, что алгоритма не существует? Для этого и нужно точное понятие алгоритма.

Т.е. понятие алгоритма возникло давно, но как предмет математического исследования это понятие было рассмотрено только в начале XX. Алгоритм стал точным математическим объектом, про который можно доказывать теоремы.

Итак, теория алгоритмов возникла, как отрасль, в ответ на потребность доказательства неразрешимости некоторых проблем, и стала заниматься исследованием того, что такое алгоритм и с появлением вычислительных машин нашла свое главное применение в информатике.

Интуитивное определение алгоритма не позволяет рассматривать свойства

алгоритмов как свойства формальных объектов. Поэтому математическое определение алгоритма необходимо по следующим причинам:

1) только при наличии формального определения алгоритма можно сделать вывод о разрешимости или неразрешимости каких-либо проблем;

2) это дает возможность для сравнения алгоритмов, предназначенных для решения одинаковых задач;

3) это дает возможность для сравнения различных проблем по сложности алгоритмов их решения.

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

Пути уточнения этого понятия (алгоритма) различны и приводят к разным алгоритмическим моделям, которые собственно и являются предметами рассмотрения теории алгоритмов.

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

Схема определения понятия «алгоритм»: (с7)

Понятие данных. Алгоритм работает с данными. Требования к данным: должны формироваться из какого-либо конечного множества символов – алфавита. Далее из символов алфавита формируются последовательности символов – слова. Чаще всего алгоритму разрешается работать не с любыми словами в алфавите, а построенными по определенным правилам, называемым грамматикой языка. Т.е. то, что называется правильно построенными выражениями(цепочками).

Память. Не во всех алгоритмических моделях память присутствует явно, но так или иначе ясно, что данные должны быть где-то записаны (как входные, так и те что возникают в процессе вычисления). Должны быть определены ячейки памяти и должно быть установлено соответствие между единицами данных и единицами памяти. Можно считать, что в одной единице памяти записывается один символ алфавита.

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

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

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

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими формально строгие определения понятия алгоритма связаны с введением специальных математических конструкций — формальных алгоритмических систем или моделей вычислений.