Файл: информатика.doc

Сопоставление алгоритмических моделей

Функция называется вычислимой, если имеется алгоритм, вычисляющий ее значение.

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

Данные определения не являются формально строгими, т.е. не позволяют предсказать, окажется ли некоторая функция вычислимой или нет (или, что тоже самое: как по характеру функции определить, можно ли построить алгоритм для ее вычисления?). По этой причине весьма важным для по­строения теории алгоритмов был тезис Черча, который утверждал, что всякая частично рекурсивная функция является вычислимой. Другими словами, если функцию удалось построить с помощью 'суперпозиции, рекурсии и минимизации из простейших арифметических, то существует алгоритм, ее вычисляющий. Далее последовал тезис Тьюринга, утверждавший, что для всякой вычислимой функции можно построить машину Тьюринга, которая ее вычисляет. Можно доказать, что алгоритмы Поста также сводятся к алгоритмам, реализуемых с помощью частично рекурсивных функций. Справедливо и обратное утверждение. В частности задачи, ре­шенные для машины Поста, являются примером реализации одной из простейших рекурсивных функций - функции непосредственного следования. Позднее была доказана теорема о сводимости одной алгоритмической модели к другой, следствием которой явились утверждения типа: «любую рекурсивную функцию можно вычислить с помощью соответствующей машины Тьюринга» или «для любой задачи, решаемой с помощью машины Тьюринга, существует решающий ее нормачъный алгоритм Маркова». Таким образом, все модели оказываются эквивалентными, в чем виден глубокий смысл, так как результат обработки информации, безусловно, определяется характером функции (алгоритмом) и входными данными, но не зависит от вида алго­ритмической модели.

Проблема алгоритмической разрешимости.

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

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

Интерес математиков к задачам подобного рода привел к постановке вопроса: возможно ли, не решая задачи, доказать, что она алгоритмически неразрешима, т.е. что нельзя построить алгоритм, который обеспечил бы ее общее решение? Ответ на это вопрос важен, в том числе, и с практической точки зрения, например, бессмысленно пытаться решать задачу на компьютере и разрабатывать для нее программу, если доказано, что она алгоритмически неразрешима. Именно для ответа на данный вопрос и понадобилось сначала дать строгое определение алгоритма, без чего обсуждение его существования просто не имело смысла. Построение такого определения, как уже знаем, привело к появлению формальных алгоритмических систем, что дало возможность математического доказательства неразрешимости ряда проблем. Оно сводится к доказательству невозможности построения рекур­сивной функции, решающей задачу, либо (что эквивалентно) к невозможности построения машины Тьюринга для нее, либо несостоятельности любой (какой-либо) другой модели из представленных в предыдущем пункте. Т.е. задача считается алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), которая ее решает. Первые доказательства алгоритмической неразрешимости касались некоторых вопросов логики и самой теории алгоритмов. Оказалось, например, что неразрешима задача установления истинности произвольной формулы исчисления предикатов (т.е. исчисление предикатов неразрешимо) - эта теорема была доказана в 1936 г Черчем.

В 1946-47 гг. А.А. Марков и Э. Пост независимо друг от друга доказали отсутствие алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.

В теории алгоритмов к алгоритмически неразрешимой относится «проблема остановки»: можно ли по описанию алгоритма (Q) и входным данным (х) установить, завершится ли выполнение алгоритма результативной остановкой? Эта проблема имеет прозрачную программистскую интерпретацию. Часто ошибки разработки программы приводят к зацикливанию - ситуации, когда цикл не завершается и не происходит завершения работы программы и остановки. Неразрешимость проблемы остановки означает, что нельзя создать общий (т.е. пригодный для любой программы) алгоритм отладки программ. Неразрешимой оказывается и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который для любых двух алгоритмов (программ) выяснял бы, всегда ли они приводят к одному и тому же результату или нет.результатов: ИСТИНА или ЛОЖЬ. Этот класс можно считать разновидностью первого, поскольку предикат - это функция, принимающая два значения в зависимости от условия. Тем не менее, разделение этих классов задач полезно, так как приводит к двум важным понятиям теории алгоритмов - вычислимая функция и разрешимое множество.

Функция называется вычислимой, если имеется алгоритм, вычисляющий ее значение.

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

5. Понятие и применение рекурсивных алгоритмов при решении задач. Сравнение рекурсивных и итерационных алгоритмов. Анализ сложности алгоритмов. Понятие вычислительной сложности (по времени и памяти). Асимптотические верхние и средние оценки для алгоритмов; сравнение алгоритмов по времени и памяти.

определения.

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

Формы рекурсивных процедур.

В общем случае любая рекурсивная процедура Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Р. Безусловные рекурсивный процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое внимание, так как практическое использование процедур с бесконечным самовызовом невозможно. Такая невозможность вытекает из того, что для каждой копии рекурсивной процедуры необходимо выделять дополнительную область памяти, а бесконечной памяти не существует. Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.

Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.

Структура рекурсивной процедуры может принимать три разных формы:

1. Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).

2. Форма с вьшолнением действий после рекурсивного вызова (с вьшолнением действий на рекурсивном возврате)

3. Форма с вьшолнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

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

Пример рекурс алгоритмаЗадача о Ханойских башнях.

Отображение более сложных рекурсивных связей в алгоритмах покажем на примере задачи о Ханойских башнях. Эта интересная задача была сформулирована в 1883 году математиком Э.Люка. Многие учебные пособия по программированию используют ее как классический пример рекурсивного алгоритма.

Суть задачи состоит в следующем. Где-то далеко в окрестностях города Ханой стоят три башни. Одна из башен состоит из 97 золотых дисков, положенных друг на друга - как кольца в детской пирамиде. Диаметры всех дисков различны и уменьшаются от нижнего к верхнему. Необходимо перенести все диски с одной башни на другую. При этом диски можно переносить только по одному с любой башни на другую. Ставить диск на землю или надевать больший на меньший нельзя! Согласно легенде этой работой заняты монахи

из местного монастыря. День и ночь они заняты переносом дисков с башни на башню. Когда они закончат всю работу - наступит конец света. Кстати, это вполне похоже на правду: для перемещения N дисков на другой стержень (по одному, не кладя больший на меньший) нужно сделать 2n-1 перемещений, что легко следует по индукции.

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

Таким образом, если сформулировать решение для п дисков в терминах п-1 диска, то мы фактически получим алгоритм рекурсивной процедуры, с помощью которой можно легко достичь цели поставленной задачи. Рассмотрим словесное описание алгоритма. Если n=1, тогда переместить этот диск со столбика А на столбик С и остановиться. В противном случае, надо поступить следующим образом: 1. переместить верхние n-1 диск со столбика А на столбик В, используя столбик С как вспомогательный. 2. переместить оставшийся нижний диск со столбика А на столбик С. 3. переместить п-1 диск со столбика В на столбик С, используя столбик А как вспомогательный.

Можно с уверенностью сказать, что т акая последовательность действий даст корректное решение для любого значения п. Это вытекает из следующего. Если n=1, то корректность очевидна. Если n=2, то мы знаем, что уже имеем решение для случая (n-l)-ro диска, которое равно 1. аналогично, если n=3, мы снова имеем решение для (n-l)-ro диска, которое равно 2 и т.д.

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

Program Hanoi_Towers;

Uses Crt;

Var n:Integer;

Procedure Move_Disks (n:Byte; Source, Dest, Tmp: Char);

{ n - число дисков на столбике Source}

{Source - исходный столбик}

{Dest - столбик, на который нужно переставить диски}

{Tmp - вспомогательный столбик}

begin

if n=l then

writeln ('Переставить диск номер 1 со столбика', Source, 'на столбик ',

Dest)

else begin

{переставляем n-1 верхних дисков с исходного столбика на} {вспомогательный, используя целевой диск как промежуточный}

Move_Disks (n-1, Source, Tmp, Dest);

Writeln ('переставить диск номер', п:1, 'со столбика', Source,

'на столбик', Dest);

{ переставляем все п-1 диск, расположенные на вспомогательном} {столбике, на целевой, используя исходный диск как промежуточный}

Move_Disks (n-1, Tmp, Dest, Source);

End End;

^Begin

Write ('введите число дисков:');

Readln (n);

Writeln ('последовательность инструкций для решения задачи:');

Writeln;

Move_Disks (n, 'А', 'С, 'В');

End.

Результат работы программы для числа исходных дисков на столбике А, равного 4, будет таким:

Введите число дисков: 4

Последовательность инструкций для решения задачи:

Переставить диск номер 1 со столбика А на столбик В

Переставить диск номер 2 со столбика на А столбик С

Переставить диск номер 1 со столбика В на столбик С

Переставить диск номер 3 со столбика А на столбик В

Переставить диск номер 1 со столбика С на столбик А

Переставить диск номер 2 со столбика С на столбик В

Переставить диск номер 1 со столбика А на столбик В

Переставить диск номер 4 со столбика А на столбик С

Переставить диск номер 1 со столбика В на столбик С

Переставить диск номер 2 со столбика В на столбик А

Переставить диск номер 1 со столбика С на столбик А

Переставить диск номер 3 со столбика В на столбик С