Вопрос 1. Интуитивное понятие алгоритма.

Термин «алгоритм» – транскрипция имени великого узбекского математика Мухаммеда аль-Хорезми (Мухаммеда из Хорезма, области нынешнего Узбекистана). Мухаммед аль-Хорезми еще в IX веке разработал правила выполнения четырех действий арифметики. Эти правила до сих пор служат простейшими примерами математических алгоритмов.

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

Однако не следует считать алгоритм чисто математическим понятием. Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи, для описания которых используется тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний. Например, чтобы приготовить вкусное блюдо, вы раскрываете поваренную книгу, отыскиваете рецепт (иными словами, алгоритм приготовления) и, следуя его конкретным указаниям (на два стакана муки – 250 г масла, 1 яйцо,…, тесто разрезать на полоски …, в духовке 20—25 минут…), за конечное число шагов решаете поставленную перед собой задачу.

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

В белорусско-русском терминологическом словаре «Информатика» (авторы Быкодоров Ю.А., Кузнецов А.Т., Павловский А.И., Пономаренко В.К., Морозов А.А.) понятие алгоритма трактуется так: «алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных».

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

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

Свойства алгоритмов.

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

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

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

2. Детерминированность – объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.

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

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

Рассмотрим известный пример «бытового» алгоритма – алгоритм перехода улицы: «Посмотри налево. Если машин нет – дойди до середины улицы. Если есть – подожди, пока они проедут.» и т.д. Представьте себе ситуацию: машина слева есть, но она не едет – у нее меняют колесо. Если вы думаете, что надо ждать, то вы правильно поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.

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

4. Конечность – завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.

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

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