22. Интуитивное понятие алгоритма. Требования к алгоритмам.

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

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

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

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

Это не является определением, т.к. выражение «единый», «конечное число шагов» лишены математической точности.

Требования, предъявляемые к алгоритму:

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

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

3. Детерминированность — повтор результата при повторе исходных данных.

4. Корректность — способность алгоритма давать правильные результаты решения задачи при различных исходных данных.

5. Конечность — решение задачи должно быть полученоза конечное число шагов алгоритма, "зацикливание" недопустимо.

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

23. Формализация понятия алгоритма и универсальные алгоритмические модели.

Введенного на интуитивном уровне понятия алгоритма и опытным путем установленных свойств алгоритмов вполне достаточно для решения широкого круга математических задач. Достаточно такого подхода и при решении практических задач программирования компьютеров. Однако, в тех случаях, когда задача оказывается сложной и алгоритмическое решение задачи найти не удается, встает вопрос о ее алгоритмической разрешимости. При этом требуется понятие алгоритма формализовать, т.е. четко определить исполнителя алгоритмов, с помощью которого можно провести доказательство алгоритмической неразрешимости задачи. В первой половине XX века почти параллельно было разработаны несколько подходов к формализации алгоритмов — рекурсивные функции, абстрактные машины Тьюринга и Поста, λ-исчисление, нормальные алгорифмы (так это традиционно называется в математике) Маркова, впоследствии оказавшиеся эквивалентными. Некоторые из этих подходов оказали воздействие на становление информатики и нашли отражение в производственных языках программирования — таких как Lisp (λ-исчисление), Рефал (нормальные алгорифмы Маркова). Последний язык — используется в исследованиях и разработках в области искусственного интеллекта, — кстати, чуть ли не единственный, разработанный в России и получивший мировое признание.

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

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