Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Тема 2. ТЕОРИЯ АЛГОРИТМОВ
Содержание
- 1. Тема 2. ТЕОРИЯ АЛГОРИТМОВ
- 2. §1. ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ И ОСНОВНЫЕ ТРЕБОВАНИЯ К НИМ
- 3. Известно, что в математике существуют различные вычислительные
- 4. Считается, что термин «алгоритм» происходит от искаженного
- 5. Можно дать следующее определение понятия алгоритма. Определение.
- 6. Несмотря на то, что существует множество всевозможных
- 7. 3. Дискретность. Алгоритм должен быть построен таким
- 8. Для формирования алгоритма используется конечный набор операций
- 9. Обычно операторы, которые используются для вычислений, обозначаются
- 10. Группа операторов, выполняющихся многократно при одной реализации
- 11. Существует множество способов описания алгоритма, особенно можно
- 12. Слайд 12
- 13. 2. Линейная форма записи. Запиcи для предшествующего
- 14. 3. Представление алгоритма в виде структурной схемы
- 15. Слайд 15
- 16. Существуют государственные стандарты, которые определяют правила выполнения
- 17. В начале параграфа мы уже приводили два
- 18. 1. Связано с машинной математикой. В нем
- 19. 2. Связано с уточнением понятия эффективно вычислимой
- 20. 3. Связано с понятием нормальных алгоритмов (алгорифмов) А.А.Маркова, которые трактуют способы обработки некоторых синтаксических конструкций.
- 21. §2. РЕКУРСИВНЫЕ ФУНКЦИИ
- 22. Исходная идея построения точного определения алгоритма, опирающегося
- 23. Введем понятие вычислимой функции так, чтобы это
- 24. Среди алгоритмических проблем довольно распространенной является такая,
- 25. Определение. Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значение.
- 26. Понятие алгоритма в этом определении берется в
- 27. Переход от понятия алгоритма к понятию вычислимой
- 28. Курт Гёдель родился 28 апреля 1906 года в Моравии,
- 29. Любая алгоритмическая модель, в том числе рекурсивные
- 30. Определение. Частично рекурсивная функция это числовая
- 31. Простейшие функции следующие: оператор сдвига или
- 32. Как указано в определении, перечисленные простейшие функции
- 33. Набор операторов, обеспечивающих преобразование простейших функций, следующий.1.
- 34. Пример. Функции константы 1 и 2 могут
- 35. 2. Оператор примитивной рекурсии. Говорят, что функция
- 36. Приведенная схема справедлива для общего случая n-местной
- 37. Определение. Частичная функция f(x1,…, xn) называется примитивно
- 38. и так далее…Очевидно, что функция f будет
- 39. Пример. Функция двух переменных S(x,y) = x+y
- 40. 3. Операция минимизации ( -оператор). Пусть
- 41. Приведенная запись трактуется как следующие утверждения: наименьшее
- 42. Алгоритм вычисления функции можно представить в следующем
- 43. Шаг 3. Берется следующее значение y и
- 44. Пример. Рассмотрим функцию f(x,y)=x-y, которая может быть
- 45. Определение. Функция называется
- 46. Определение. Функция называется общерекурсивной,
- 47. Как видно из приведенных выше определений, класс
- 48. Понятие частично рекурсивной функции является одним из
- 49. Определение (тезис А. Черча). Каждая интуитивно вычислимая
- 50. Приведенный тезис дает алгоритмическое истолкование понятия частично
- 51. Тезис Черча оказался достаточным, чтобы придать необходимую
- 52. §3. МАШИНА ТЬЮРИНГА
- 53. Машина Тьюринга (МТ) это абстрактное устройство,
- 54. Пост, Эмиль Леон (англ. Post Emil Leon, 11
- 55. Общий вид МТ приведен на рисунке.
- 56. Она состоит из следующих компонент: 1. Управляющее устройство,
- 57. 2. Лента, разбитая на ячейки. В каждой
- 58. 3. Устройство обращения к ленте – головка,
- 59. Можно сказать, что в МТ реализуется система
- 60. Реализация указанной последовательности действий называется тактом, т.е.
- 61. Конкретная машина Тьюринга задается перечислением элементов множеств
- 62. Существует несколько способов представления набора правил преобразования,
- 63. В таблице описывающей функционирования МТ возможным состояниям
- 64. Диаграмма переходов – это граф, вершинам которого
- 65. Пример. Пусть на ленте записаны два натуральных
- 66. Для сложения чисел 2 и 3 начальное
- 67. Слайд 67
- 68. Пример. Иногда требуется реализовать задачу таким образом,
- 69. Начальное состояние МТ для чисел 2 и 4 должно иметь вид Заключительное состояние МТ
- 70. В основе алгоритма будет лежать следующая идея:
- 71. Множества A и Q определены так:
- 72. Полное состояние МТ, однозначно определяющее ее дальнейшее
- 73. Очевидно, применять машину Тьюринга для задачи,
- 74. Запись
- 75. Тьюринг убедительно показал разнообразие возможностей предложенной им
- 76. Пусть функция g определена как композиция функций
- 77. По своему устройству МТ крайне примитивна. Она
- 78. МТ один из путей уточнения
- 79. Этот тезис так же как и
- 80. §4. НОРМАЛЬНЫЕ АЛГОРИТМЫ А.А.МАРКОВА
- 81. Нормальный алгоритм — понятие, введенное в
- 82. Если в классической математике исследователь имеет
- 83. Понятие конструктивного объекта не определяется, а
- 84. Существование такого конструктивного объекта считается доказанным
- 85. Каждый конструктивный объект определяется непосредственно предшествующим
- 86. Другими словами, классическая и конструктивная математики
- 87. Определение 1. Алгоритмом в алфавите А
- 88. Пример. Сформируем алгоритм, удовлетворяющий введенному определению. Пусть
- 89. Однако Определение 1 является слишком общим,
- 90. Пример. Рассмотрим вариант определения алгоритма в
- 91. Из следующего указания о способе применения
- 92. Схема подстановок вместе с указанием, как ими
- 93. Очевидно, что в приведенном примере возможны
- 94. С первого взгляда можно решить, что
- 95. Определение. Два алгоритма A1 и A2 в
- 96. Для того чтобы дать точное математическое определение
- 97. Определение. Задается алфавит А и фиксируется схема
- 98. Теперь становится видно, что приведенный в определении
- 99. Это утверждение является гипотезой; оно не
- 100. Можно отметить, что теория нормальных алгоритмов
- 101. Этот вид абстракции не предполагает индивидуализации
- 102. Понимать под «построением» с точки зрения
- 103. Абстракция потенциальной осуществимости наиболее широко применяется
- 104. В заключение можно отметить, что алгоритм
- 105. §5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОСНОВНЫХ МОДЕЛЕЙ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ
- 106. Известно, что все рассмотренные ранее модели
- 107. Различные варианты решения проблем привели к построению
- 108. Традиционно все алгоритмические задачи принято делить на
- 109. В первом случае алгоритм Q начинает работать
- 110. В задачах, отнесенных ко второму классу,
- 111. Эти определения не являются строгими, т.к.
- 112. Позднее была доказана теорема о сводимости
- 113. §6. ПРОБЛЕМА АЛГОРИТМИЧЕСКОЙ РАЗРЕШИМОСТИ
- 114. Всякому алгоритму соответствует задача, для решения
- 115. Под термином «алгоритм» в математике обычно
- 116. Кроме того, она дала толчок развитию
- 117. Первые доказательства алгоритмической неразрешимости касались самой теории
- 118. Эту проблему легко проиллюстрировать практическим примером.
- 119. Несомненная польза определения алгоритмической неразрешимости состоит
- 120. Важность и практическая значимость абстрактных алгоритмических
- 121. Скачать презентанцию
§1. ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ И ОСНОВНЫЕ ТРЕБОВАНИЯ К НИМ
Слайды и текст этой презентации
Слайд 4 Считается, что термин «алгоритм» происходит от искаженного имени узбекского математика
(аль-Хорезми - ал Хорезми - ал Горезми – алгоритм), который
еще в IX веке разработал основополагающий трактат по арифметике и алгебре («Книга о восстановлении и противопоставлении»), где и предложил простейшие арифметические алгоритмы.
Слайд 5 Можно дать следующее определение понятия алгоритма.
Определение. Алгоритм – это
план действий, состоящий из последовательности понятных человеку операций, приводящих к
искомому результату. Алгоритм состоит из элементарных шагов, число которых конечно.Учитывая, что решаемые с помощью алгоритмов задачи являются однотипными, о них можно говорить как о массовой проблеме и тогда возможно следующее определение для алгоритма.
Определение. Общий, единообразный, точно определяемый способ решения любой задачи из некоторой заданной массовой проблемы называется алгоритмом.
Оба приведенных ниже определения относятся к не строгим определениям, которые называются интуитивными.
Слайд 6 Несмотря на то, что существует множество всевозможных алгоритмов, применяемых при
решении различных задач, можно выделить основные требования, применяемые к любому
алгоритму:1. Понятность. Алгоритм должен быть доступен для понимания определенному классу пользователей.
2. Определенность. Это требование означает точность формулировок, исключение неоднозначности толкования на любом шаге алгоритма, то есть при одних и тех же исходных данных задача должна иметь одно и то же решение.
Слайд 7 3. Дискретность. Алгоритм должен быть построен таким образом, что если
в начальный момент задается конечный набор исходных величин, то набор
величин следующего шага может быть получен по определенному закону из величин предыдущего шага.4. Элементарность шага. Закон получения следующего набора величин из предшествующего должен быть простым.
5. Массовость. Означает универсальность алгоритма для решения любой задачи из некоторого класса и возможность его использования при любых допустимых исходных данных.
6. Конечность и результативность. Состоит в получении искомого результата после конечного числа шагов.
Слайд 8 Для формирования алгоритма используется конечный набор операций
Совокупность величин, объединенных знаком операции, называется оператором, а сами величины операндами.
Выделяют следующие типы элементарных операторов:
1. Сингулярный (когда операндом является одна величина).
2. Бинарный (выполняет операции с двумя операндами).
Слайд 9 Обычно операторы, которые используются для вычислений, обозначаются буквами A1, A2,
… An, здесь индекс имеет смысл метки, выделяющей данный оператор.
Тогда алгоритм можно представить как последовательность таких операторов (A1, A2, … An), которые выполняются дискретно в порядке их записи. Для обеспечения возможности изменения порядка действий вводят операции отношения – предикаты Pi, Pi – это условный оператор. В зависимости от истинности этого оператора выполняется переход к тому или иному следующему оператору алгоритма. Применяя Pi, можно осуществлять ветвление алгоритма.
Слайд 10 Группа операторов, выполняющихся многократно при одной реализации алгоритма, называется циклом.
Если
при решении задачи используется некоторый алгоритм, то процесс обычно разделяют
на два этапа:1. Составление алгоритма (описание), т.е. происходит формализация процесса решения для некоторого класса задач.
2. Реализация алгоритма, т.е. построенный алгоритм применяется к некоторому набору исходных данных с целью получения результата.
Слайд 11 Существует множество способов описания алгоритма, особенно можно выделить следующие варианты
описания:
1. Словесное описание. Словесное описание производится на естественном языке, однако
при этом должны быть четко выделены шаги. При описании шагов используются формулы, общепринятые математические знаки и символы. Описание является корректным, если оно может быть воспринято и однозначно интерпретировано другим лицом.
Слайд 13
2. Линейная форма записи. Запиcи для предшествующего алгоритма в линейной
форме имеет вид
Запись означает, что после
выполнения Ai будет выполняться оператор с меткой m. Запись означает, что после выполнения Pi, в случае его истинности, выполняется следующий за ним оператор, в противном случае осуществляется переход на оператор с меткой m.
Слайд 14 3. Представление алгоритма в виде структурной схемы или блок-схемы. Такая
схема представляет собой граф: вершинам соответствуют шаги (действия), а ребрам
– переходы, отображающие последовательность выполнения шагов.В качестве примера далее приведена блок-схема описанного выше алгоритма.
Слайд 16 Существуют государственные стандарты, которые определяют правила выполнения алгоритмов.
В блок-схеме
каждый шаг может быть либо элементарным, либо многокомпонентным, представляющим собой
самостоятельный алгоритм. Преимуществами такого представления являются:Возможность распараллеливания процесса разработки алгоритма.
Возможность связывания алгоритмов при решении комплексных задач.
Возможность пошаговой детализации алгоритма.
Слайд 17
В начале параграфа мы уже приводили два различных определения алгоритма.
Различные исследователи теории алгоритмов в процессе ее развития выработали множество
определений, это объяснялось тем, что они исходили из различных технических и логических соображений. Однако со временем было доказано, что все эти определения равносильны, т.е. определяют одно и то же понятие. Поэтому сегодня в подходах к определению алгоритма можно выделить три основных направления:
Слайд 18
1. Связано с машинной математикой. В нем сущность понятия алгоритма
раскрывается путем рассмотрения процессов, осуществляемых в машине.
Впервые это было
сделано английским математиком Аланом Тьюрингом (Turing) в 1937 году. Он предложил самую общую и вместе с тем самую простую концепцию вычислительной машины. 
Слайд 19 2. Связано с уточнением понятия эффективно вычислимой функции. Результатом исследований
было выделение особого класса частично рекурсивных функций, которые имеют
строгое математическое определение.Алонзо Чёрч
Слайд 20 3. Связано с понятием нормальных алгоритмов (алгорифмов) А.А.Маркова, которые трактуют
способы обработки некоторых синтаксических конструкций.
Слайд 22 Исходная идея построения точного определения алгоритма, опирающегося на понятие рекурсивной
функции, состоит в том, что любые данные можно закодировать натуральными
числами в некоторой системе счисления, и тогда всякое их преобразование сведется к последовательности вычислительных операций, а результат обработки также будет представлять собой целое число.В данном подходе любой алгоритм, единый для данной числовой функции, вычисляет ее значение, а его элементарными шагами оказываются обычные арифметические и логические операции. Функции, удовлетворяющие таким требованиям, называются вычислимыми.
Слайд 23 Введем понятие вычислимой функции так, чтобы это не было напрямую
связано с понятием алгоритма.
Функция вида f:XY будет называться частичной,
если она определена не для всех xX. Совокупность тех элементов множества X, для которых определены элементы в Y, называется областью определения функции, а совокупность тех элементов Y, которые соответствуют элементам X, называют областью значений функции. Если область определения функции из X в Y совпадает с множеством X, то функцию называют всюду определенной.
Слайд 24 Среди алгоритмических проблем довольно распространенной является такая, которая требует найти
алгоритм для решения некоторой задачи, условия которой сформулированы следующим образом.
Исходные данные представлены в виде конечной системы целочисленных параметров , а результатом является целое число y. Следовательно, стоит вопрос о существовании алгоритма для вычисления значения числовой функции, зависящей от аргументов .
Слайд 25
Определение. Функция
называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить
ее значение.
Слайд 26 Понятие алгоритма в этом определении берется в интуитивном смысле, поэтому
и понятие эффективно вычислимой функции оказывается интуитивным, однако при переходе
от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство, а именно: совокупность процессов, удовлетворяющих требованиям, предъявляемым к алгоритмам, достаточно обширна и не поддается полному описанию, совокупность же вычислимых функций, удовлетворяющих перечисленным условиям, ограничена и легко описывается в обычных математических терминах.
Слайд 27 Переход от понятия алгоритма к понятию вычислимой функции удобен с
той точки зрения, что позволяет перенести требования, предъявляемые к алгоритмам,
на множество числовых функций. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком понимании алгоритма, носит название совокупности рекурсивных функций. Впервые это понятие было введено австрийским математиком Куртом Гёделем в 1931 г.
Слайд 28
Курт Гёдель родился 28 апреля 1906 года в Моравии, входившей тогда в
состав Австро-Венгерской империи, а ныне образующей часть Чехии.
Слайд 29 Любая алгоритмическая модель, в том числе рекурсивные функции, должна предусматривать
определение элементарных шагов алгоритма и способов построения из них какой-то
последовательности преобразований, обеспечивающих необходимую последовательность обработки данных.В рекурсивной модели такими «элементарными шагами» являются так называемые простейшие числовые функции, из комбинации которых строятся более сложные функции. С учетом этого введем следующее определение.
Слайд 30
Определение. Частично рекурсивная функция это числовая функция, которая строится
следующим образом. Определяется конечное число простейших функций и операций. Выполнимость
функций должна быть очевидна, а с помощью операций из них можно порождать другие, более сложные функции.
Слайд 31 Простейшие функции следующие:
оператор сдвига или функция следования, позволяет
получить любое число натурального ряда.
оператор аннулирования или константа
0.,где . Выражение называется оператором проектирования или селекторной функцией. Каждая из функций равна одному из своих аргументов. Индекс m выделяет m-ю переменную.
Слайд 32
Как указано в определении, перечисленные простейшие функции всюду определены и
интуитивно вычислимы. Над ними можно выполнить ряд операций (часто используется
термин оператор), которые обладают тем свойством, что их применение к функциям, вычислимым в интуитивном смысле, порождает новые функции, также заведомо вычислимые в интуитивном смысле.Частичные функции, которые можно получить при помощи этих операторов из простейших функций, также будут частично рекурсивными, т.е. класс построенных таким образом частично рекурсивных функций совпадает с классом функций, допускающих алгоритмическое вычисление.
Слайд 33 Набор операторов, обеспечивающих преобразование простейших функций, следующий.
1. Суперпозиция функций. Пусть
задана функция
и функции , , … , , тогда говорят, что функция получена суперпозицией из функций h и , если имеет место следующее равенство:
Слайд 34 Пример. Функции константы 1 и 2 могут быть получены следующей
суперпозицией из простейших функций:
Очевидно, что таким же образом может быть
получено любое число натурального ряда.
Слайд 35 2. Оператор примитивной рекурсии. Говорят, что функция получена из функций
и с помощью оператора примитивной рекурсии, если она может
быть задана схемой примитивной рекурсии:
Слайд 36 Приведенная схема справедлива для общего случая n-местной функции, т.е. когда
n>=1, в том случае, когда n=0 , схема примитивной рекурсии
имеет следующий вид:где a – постоянная одноместная функция, равная числу а (т.е. константа).
Слайд 37 Определение. Частичная функция
f(x1,…, xn) называется примитивно рекурсивной, если ее
можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя
лишь из простейших функций.Если функции h и интуитивно вычислимы, то будет интуитивно вычислима и f. Например, если – это набор аргументов, соответствующих , то значения для f могут быть найдены следующим образом:
Слайд 38
и так далее…
Очевидно, что функция f будет всюду определена, если
всюду определены функции h и .
Слайд 39 Пример. Функция двух переменных S(x,y) = x+y может быть получена
по схеме примитивной рекурсии.
Известно, что для x+y справедливы следующие выражения:
х+0=х;
x+(y+1)=(x+y)+1.
Следовательно,
их можно переписать в видеS(x,0)=x;
S(x,y+1)=S(x,y)+1,
или иначе
Из приведенных равенств видно, что функция двух переменных S(x,y) получается по схеме примитивной рекурсии из функции одной переменной и функции трех переменных.
Слайд 40 3. Операция минимизации ( -оператор). Пусть задана некоторая функция
f(x,y). Фиксируя значение х выясняем, при каком y .
Так как
результат решения задачи зависит от x, то наименьшее значение y, при котором имеет место , является функцией от x, поэтому используется следующие обозначение:
Слайд 41 Приведенная запись трактуется как следующие утверждения: наименьшее y такое, что
f(x,y) = 0.
Исходя из вышеизложенного, можно определить функцию и для
нескольких переменных:Переход от функции к функции принято называть применением - оператора.
Слайд 42 Алгоритм вычисления функции можно представить в следующем виде.
Шаг 1. Вычисляется
. Если , то полагается
.Если , то переход на шаг 2.
Шаг 2. Вычисляется .
Если , то полагается
Если , то переход на шаг 3.
Слайд 43 Шаг 3. Берется следующее значение y и повторяется действие, аналогичное
предшествующему шагу.
Шаг N. Если перебраны все значения y и для
любого из них , то функция в этом случае считается неопределенной.
Слайд 44 Пример. Рассмотрим функцию f(x,y)=x-y, которая может быть получена с помощью
оператора минимизации
f(x,y)=z(y+z=x)=z[I32(x,y,z)+I33(x,y,z)=I31(x,y,z)] .
Вычислим, например, f(7,2), т.е. значение функции при y
= 2 и x = 7. Положим y = 2, а x будем придавать последовательные значения :z=0, 2+0=27; z=1, 2+1=37;
z=2, 2+2=47; z=3, 2+3=57;
z=4, 2+4=67; z=5, 2+5=7=7.
Таким образом, найдено значение функции f(7,2) = 5.
![Пример. Рассмотрим функцию f(x,y)=x-y, которая может быть получена с помощью оператора минимизацииf(x,y)=z(y+z=x)=z[I32(x,y,z)+I33(x,y,z)=I31(x,y,z)] . Вычислим, например, f(7,2), т.е. значение](/img/thumbs/eac7e8460a7a898b133c427060669a63-800x.jpg "Тема 2. ТЕОРИЯ АЛГОРИТМОВ Пример. Рассмотрим функцию f(x,y)=x-y, которая может быть получена с помощью оператора")
Слайд 45
Определение. Функция называется частично рекурсивной, если
она может быть получена в конечное число шагов из простейших
функций при помощи операций суперпозиции, схем примитивной рекурсии и-оператора исходя лишь из простейших функций.
Слайд 46
Определение. Функция называется общерекурсивной, если она частично
рекурсивна и всюду определена.
Общерекурсивными можно, например, считать следующие функций:
1)
;2) О(х) ;
3) ;
4) f(y,x)=y+x ;
5) f(y,x)=y*x .
Слайд 47
Как видно из приведенных выше определений, класс частично рекурсивных функций
шире класса примитивно рекурсивных функций, т.к. все примитивно рекурсивные функции
являются всюду определенными, а среди частично рекурсивных функций встречаются функции, не всюду определенные, а также нигде не определенные.
Слайд 48 Понятие частично рекурсивной функции является одним из базовых понятий теории
алгоритмов.
Его значение состоит в том, что, с одной стороны,
каждая стандартно заданная частично рекурсивная функция вычислима путем некоторой процедуры механического характера, отвечающей интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных алгоритмов ни строились, во всех случаях неизменно оказывалось, что вычислимые посредством них числовые функции являлись частично рекурсивными. Поэтому общепринятой является научная гипотеза, формулируемая как тезис Черча.
Слайд 49
Определение (тезис А. Черча). Каждая интуитивно вычислимая функция является частично
рекурсивной. Или другими словами: класс алгоритмически вычислимых частичных числовых функций
совпадает с классом всех частично рекурсивных функций
Слайд 50 Приведенный тезис дает алгоритмическое истолкование понятия частично рекурсивной функции.
Его
нельзя доказать, т.к. он связывает нестрогое понятие интуитивно вычислимой функции
со строгим математическим понятием частично рекурсивной функции.Однако проводимые в течение ряда лет исследования показали целесообразность того, что понятия частично рекурсивной функции и вычислимой частичной функции можно считать эквивалентными.
Слайд 51
Тезис Черча оказался достаточным, чтобы придать необходимую точность формулировкам алгоритмических
проблем и в ряде случаев сделать возможным доказательство их неразрешимости.
Причина заключается в том, что обычно в алгоритмических проблемах математики речь идет не об алгоритмах, а о вычислимости некоторых специальным образом построенных функций.В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. Поэтому обычная математическая техника позволяет иногда непосредственно доказать, что решающая задачу функция не может быть рекурсивной.
Слайд 53 Машина Тьюринга (МТ) это абстрактное устройство, идея которого была
предложена американским математиком Э.Постом и англичанином А.Тьюрингом. Их идея основывалась
на следующей посылке. Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четко следовать указаниям алгоритма. Автоматизм, присущий этой операции, естественно было бы передать от человека машине.
Слайд 54
Пост, Эмиль Леон (англ. Post Emil Leon, 11 февраля 1897, Августов,
Царство Польское (ныне Польша) — 21 апреля 1954, Нью-Йорк) —
американский математик и логик; один из основателей многозначной логики (1921); основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.
Слайд 56 Она состоит из следующих компонент:
1. Управляющее устройство, которое может находиться
в одном из состояний, образующих множество . Множество
Q называется внутренним алфавитом МТ. Для любой МТ число состояний конечно и фиксировано. Множество Q выступает в качестве внутренней памяти.
Слайд 57 2. Лента, разбитая на ячейки. В каждой ячейке должен быть
записан один из символов конечного алфавита из множества .
В
начале на ленте записывается входное слово, по одной букве в расположенных подряд ячейках. В пустых ячейках записывается знак пробела . Лента считается бесконечной, на ней фиксируются исходные и промежуточные данные, а также записывается результат. Лента выступает в качестве внешней памяти, т.к. она считается бесконечной, то это свидетельствует о том, что МТ является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера. Множество А, называется внешним алфавитом МТ.
Слайд 58 3. Устройство обращения к ленте – головка, осуществляющая считывание и
запись данных. В общем случае МТ работает следующим образом:
1. Считывается
значение символа , над которым устанавливается головка.2. В зависимости от пары значений производится следующая последовательность действий:
а) запись нового значения в ту ячейку, над которой стоит головка;
б) смещение головки на одну ячейку вправо или влево;
в) переход в новое состояние
Слайд 59
Можно сказать, что в МТ реализуется система предельно простых команд
обработки информации. Эта система команд обработки дополняется также предельно простой
системой команд перемещения головки по ленте: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на единицу, либо остаться неизменным.Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Это, конечно, удлиняет процесс обработки, но позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.
Слайд 60 Реализация указанной последовательности действий называется тактом, т.е. работа МТ состоит
из отдельных тактов.
В зависимости от того, какая была записана исходная
информация на ленте, возможны два варианта работы МТ. Пусть на ленте записана информация B0 (построенная из символов А), тогда:1. После конечного числа тактов МТ приходит в заключительное состояние qz , и на ленте изображена некоторая информация В, также построенная из символов А. В этом случае говорят, что МТ применима к В0 и перерабатывает ее в В.
2. Если МТ не приходит в состояние qz , то говорят, что машина не применима к В0.
Слайд 61 Конкретная машина Тьюринга задается перечислением элементов множеств A и Q,
а также набором правил преобразования. Очевидно, что различных множеств A,
Q и правил преобразования может быть бесконечно много, т.е. и машин Тьюринга также может быть бесконечно много.Правила преобразования, которые выполняет МТ, определяются системой команд, которые описываются следующим образом:
,
где dk – смещение ( R – вправо, L – влево,
E – без изменений).
Слайд 62 Существует несколько способов представления набора правил преобразования, т.е. работа МТ
может быть описана следующим образом:
1. Системой команд.
2. Таблицей.
3. Диаграммой (графом)
переходов.
Слайд 63 В таблице описывающей функционирования МТ возможным состояниям соответствуют строки, а
столбцам – входные символы. На их пересечении записывается следующая команда,
которая соответствует паре<состояние, символ>. Таблица имеет следующий вид:
Слайд 64 Диаграмма переходов – это граф, вершинам которого соответствуют состояния МТ,
а ребрам – команды
Рассмотрим примеры реализации МТ.
Слайд 65 Пример. Пусть на ленте записаны два натуральных числа в унарном
коде.
(Унарный код это представление числа в виде соответствующей
последовательности единиц. Например, 5=11111=15).Числа разделены символом операции сложения. Требуется реализовать операцию сложения таким образом, чтобы после ее реализации на ленте был записан результат, а управляющее устройство находилось на первом символе результата.
Слайд 66 Для сложения чисел 2 и 3 начальное состояние МТ имеет
следующий вид.
Реализация алгоритма будет базироваться на следующей идее. Из
исходного положения требуется дойти до символа "+", заменить его на символ «1», затем дойти до конца записи и заменить последнюю единицу на символ пробела – «», после чего управляющее устройство следует вернуть в начальное положение. Для приведенного примера алфавиты A и Q имеют вид.
Опишем вышеизложенное в виде системы команд:
Слайд 68 Пример. Иногда требуется реализовать задачу таким образом, чтобы на ленте
сохранились исходные данные и вместе с ними результаты выполненных
действий.Пусть требуется выполнить с помощью МТ умножение двух натуральных чисел, представленных в унитарном коде, с сохранением исходных данных.
Слайд 70 В основе алгоритма будет лежать следующая идея: записав символ «=»
после исходных данных, за ним следует повторить второе число столько
раз, какое количество единиц содержит первое число. Описание МТ в виде системы команд имеет следующий вид:
Слайд 72 Полное состояние МТ, однозначно определяющее ее дальнейшее поведение, называется конфигурацией
или машинным словом.
Конфигурация определяется следующим образом: Ki=alqiar, где qi
– текущее состояние; al – последовательность символов, записанных слева;
ar – последовательность символов, записанных справа, включая ячейку, над которой находится головка.
Вся совокупность входных конфигураций, при которых машина обеспечивает получение результата, образует класс решаемых задач.
Слайд 73 Очевидно, применять машину Тьюринга для задачи, не входящей в
класс решаемых, бессмысленно. С другой стороны, во многих случаях возможно
расширение класса решаемых задач за счет создания другой машины Тьюринга.Возникает вопрос: можно ли построить такую универсальную машину (хотя бы на теоретическом уровне), которая решала бы любую задачу? Этот вопрос относится к проблеме алгоритмической разрешимости.
Слайд 74 Запись – это обозначение
машины
с исходными данными
. Запись означает, что МТ перерабатывает входное слово в выходное слово .
Если для некоторой функции
существует МТ, которая правильно ее вычисляет, будучи запущенной в начальной конфигурации, то эта функция называется правильно вычислимой по Тьюрингу.
Слайд 75 Тьюринг убедительно показал разнообразие возможностей предложенной им конструкции и пришел
к выводу, который известен как тезис Тьюринга: всякий алгоритм может
быть реализован соответствующей машиной Тьюринга.Ранее, в разделе, посвященном частичнорекурсивным функциям, была рассмотрена операция композиции, которая позволяла строить новую функцию на основе существующих функций. Аналогичную операцию можно реализовать применительно к машинам Тьюринга.
Слайд 76
Пусть функция g определена как композиция функций f1 и f2,
т.е. g=f2(f1(x)). Результат g получается как результат применения f2 к
результату работы f1. Для того чтобы эта функция была определена, необходимо и достаточно, чтобы f1 была определена на x, а f2 на f1(x).Теорема. Если функции f1(x) и f2(y) вычислимы по Тьюрингу, то их композиция f2(f1(x)) также вычислима по Тьюрингу.
Построенную т.о. машину T называют композицией машин T1 и T2 и обозначают T2 (T1).
Слайд 77 По своему устройству МТ крайне примитивна. Она намного проще самых
простых компьютеров. Примитивизм состоит в том, что у нее предельно
прост набор элементарных операций, производимых головкой, – считывание и запись, а также в том, что доступ к ячейкам памяти в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты.По этой причине даже такие простые действия, как сложение с единицей или сравнение двух символов на равенство, МТ производит за несколько шагов, а обычные операции: сложение, умножения или деление требуют гораздо большего числа элементарных действий.
Однако МТ была придумана не как модель или прототип реальных вычислительных машин, а для того чтобы показать принципиальную возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически.
Слайд 78 МТ один из путей уточнения понятия алгоритма. Тьюринг
убедительно показал разнообразие возможностей предложенной им конструкции и пришел к
выводу, который известен как тезис Тьюринга.Определение (тезис А.Тьюринга). Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Слайд 79 Этот тезис так же как и тезис Черча, невозможно
доказать, т.к. он связывает нестрогое определение понятия алгоритма со строгим
определением машины Тьюринга. Поэтому этот тезис может быть опровергнут, если удастся привести пример алгоритма, который невозможно реализовать с помощью тьюринговой схемы, однако пока все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых схем.
Слайд 81 Нормальный алгоритм — понятие, введенное в конструктивную математику русским
ученым А.А.Марковым.
Под конструктивной математикой понимается такое направление в математике,
которое, как и классическая математика, имеет своим предметом исследование форм и количественных отношений объективной действительности, но отличается от классической математики некоторыми особенностями. 
Слайд 82 Если в классической математике исследователь имеет дело с объектами,
о которых известно, что они обладают такими то свойствами, и
при этом полностью отвлекается от способов построения такого объекта, то в конструктивной математике исследователь ограничивается конструктивными объектами, существование которых считается доказанным лишь тогда, когда указывается способ потенциально осуществимого построения (конструирования) данного объекта.
Слайд 83 Понятие конструктивного объекта не определяется, а лишь поясняется примерами.
В качестве элементарного конструктивного объекта берутся, например, буквы, входящие в
то или иное слово. Из этих элементарных конструктивных объектов по некоторым правилам, принятым по соглашению, строится слово, а из слов еще более сложные конструктивные объекты.
Слайд 84 Существование такого конструктивного объекта считается доказанным лишь тогда, когда
указывается способ потенциально осуществимого построения (конструирования) объекта. Так, например, если
применять алгоритм вычитания столбиком к паре (404, 55), то последовательно возникнут такие конструктивные объекты:
Слайд 85 Каждый конструктивный объект определяется непосредственно предшествующим конструктивным объектом. В
операциях с конструктивными объектами не применяется абстракция актуальной бесконечности, т.е.
бесконечности завершенной, из которой исходит классическая математика.В конструктивной математике руководствуются абстракцией потенциальной осуществимости, согласно которой бесконечное множество не дано в завершенном виде, ибо оно есть бесконечность потенциальная, его можно только неограниченно продолжать строить (конструировать) по определенным правилам.
Слайд 86 Другими словами, классическая и конструктивная математики по-разному определяют понятие
«существование» математического объекта.
Если в классической математике объект признается существующим,
когда он не несет в себе формально-логического противоречия, то в конструктивной математике существовать — значит быть построенным.Рассмотрим, каким образом осуществляется переход от ранее введенного интуитивного определения алгоритма к понятию «алгоритм в алфавите А», которое является ключевым понятием в рассматриваемой модели представления алгоритмов.
Слайд 87 Определение 1. Алгоритмом в алфавите А называется всякое общепонятное
точное предписание, определяющее потенциально осуществимый процесс над словами из А,
допускающее любое слово в качестве исходного и последовательно определяющее новые слова в этом алфавите.Алгоритм применим к некоторому слову Р, если, отправляясь от этого слова и действуя согласно предписаний, мы получим в конце концов новое слово Q, на котором процесс оборвется. Будем тогда говорить, что алгоритм перерабатывает Р в Q.
Слайд 88 Пример. Сформируем алгоритм, удовлетворяющий введенному определению. Пусть требуется переписать заданное
слово Р в обратном порядке следования букв, которое задано следующей
последовательностью символов: a1, a2, …, an. Алгоритм будет иметь вид.Шаг 1. Положить счетчик i равным n. Значение слова Q положить равным пустому слову, т.е. не содержащему ни одного символа.
Шаг 2. Взять символ c индексом i и присоединить его справа к строящемуся слову Q.
Шаг 3. Если счетчик i равен 1, то полученное слово Q есть результат и алгоритм свою работу закончил. Остановка.
Если счетчик i не равен 1, то положить i = i -1 и перейти к шагу 2.
Очевидно, что этот алгоритм представляет собой совершенно точное предписание, применимое к любому слову.
Слайд 89 Однако Определение 1 является слишком общим, т.к. уточнение понятия
«алгоритм в алфавите А» связано с использованием аппарата подстановок, т.е.
с построением ассоциативного исчисления. Рассмотрим следующий, более уточненный вариант определения.Определение 2. Будем считать, что алгоритм в алфавите А задается в виде некоторой системы допустимых подстановок, дополненной общепонятным точным предписанием о том, в каком порядке и как нужно применять допустимые подстановки, и когда наступает остановка.
Слайд 90 Пример. Рассмотрим вариант определения алгоритма в смысле определения 2.
Пусть алфавит А содержит три буквы: А = {а, b,
с} , а алгоритм определен с помощью следующей системы подстановок:
Слайд 91 Из следующего указания о способе применения этих подстановок: исходя
из произвольного слова Р, следует просмотреть схему подстановок в том
порядке, в каком они выписаны, разыскивая первую формулу, левая часть которой входит в Р. Если же такой формулы не найдется, то процесс обрывается сразу же. В противном случае берется первая из найденных формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово Р, что дает новое слово Р1, в алфавите А. Затем слово Р1 играет роль Р, т.е. вновь берется в качестве исходного, и процесс повторяется. Остановка наступает в том случае, если на n-м шаге получено слово Pn, в которое не входит ни одна из левых частей формул схемы подстановок.
Слайд 92
Схема подстановок вместе с указанием, как ими пользоваться, определяет алгоритм
в алфавите А. Этот алгоритм перерабатывает:
слово babaac в слово
bbcaaac (применена 3-я формула); слово cbacacb последовательно в слова cbacacb, ccacacb, abcacb, bcacacb, bcacacc (применены формулы: 1,2,3,1) и, наконец, в bcacacc, на котором процесс обрывается; слово bсасаbс порождает бесконечно повторяющуюся последовательность слов bcacabc, bcacbcac, bcacccac, bcacabc (применены формулы: 3, 1, 2) и т. д., т.е. остановка нe наступит, и, следовательно, к слову bcacabc алгоритм не применим.
Слайд 93 Очевидно, что в приведенном примере возможны три результата при
начале преобразований из исходного слова:
тупиковое состояние (например, слово bbcaaac);
бесконечно
кружиться по циклу (например, слово bcacabc); двигаться достаточно долго, не попадая в циклы.
Слайд 94 С первого взгляда можно решить, что определение алгоритма в
смысле определения 1 уже, чем определение в смысле определения 2.
Однако оказывается, что на деле такого сужения нет, ибо для любого известного алгоритма в смысле определения 1 может быть построен эквивалентный ему алгоритм в смысле определения 2. Это, конечно, не доказательство того, что определения 1 и 2 равносильны: такого доказательства не может существовать вообще в силу неточности и расплывчатости обоих определений (везде фигурируют слова «общепонятное, точное предписание»).Во всяком случае, очевидно, что Определение 2 это шаг вперед по пути уточнения понятия «алгоритм». Уточним теперь понятие эквивалентности алгоритмов.
Слайд 95
Определение. Два алгоритма A1 и A2 в некотором алфавите называются
эквивалентными, если области их применимости совпадают, и результаты переработки ими
любого слова из общей области применимости также совпадают.Иначе говоря, если алгоритм A1 применим к некоторому слову Р, то и A2 должен быть применим к этому слову, и наоборот. Оба алгоритма должны перерабатывать слово Р в некоторое слово Q. Если же один из алгоритмов не применим к некоторому слову B, то и другой алгоритм должен быть не применим к нему.
Слайд 96
Для того чтобы дать точное математическое определение алгоритма, потребовалось сделать
еще один шаг по пути дальнейшего уточнения. Этот шаг был
сделан А. A. Марковым. Построенный им нормальный алгоритм так же, как и алгоритм в смысле Определения 2, выражен в терминах системы подстановок, однако вместо расплывчатого «общепонятного указания» о том, как пользоваться подстановками, Марков дал стандартные, раз и навсегда определенные точные указания о порядке использования подстановок. Определение нормального алгоритма Маркова таково.
Слайд 97 Определение. Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает,
исходя из произвольного слова P и алфавита А, просмотреть формулы
подстановок в том порядке, в каком они заданы в схеме, разыскивая формулу с левой частью, входящей в Р. Если такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в Р, что дает новое слово Р1 в алфавите А. После только что выполненного первого шага процесса приступают ко второму его шагу, отличающемуся от первого только тем, что роль Р играет Р1. Далее делают аналогичный третий шаг и т.д. до тех пор, пока не придется оборвать процесс. Оборваться же он может лишь двумя способами: во-первых, когда получим такое слово Рn, что ни одна из левых частей формул схемы подстановок не будет в него входить; во-вторых, когда при получении слова Рn придется применить последнюю формулу. В обоих этих случаях мы считаем, что наш алгоритм перерабатывает слово Р в слово Рn.
Слайд 98 Теперь становится видно, что приведенный в определении 2 пример является
примером «почти нормального» алгоритма. Вся разница состоит в том, что
там остановка наступает лишь в одном случае, когда ни одна из подстановок не применима, а здесь остановка может наступать в двух случаях.Различные нормальные алгоритмы отличаются друг от друга лишь алфавитами и системами допустимых подстановок. Чтобы задать какой-либо нормальный алгоритм, достаточно задать алфавит и систему подстановок.
Понятие алгоритма в некотором алфавите было уточнено А.А. Марковым следующим образом: всякий алгоритм в алфавите А эквивалентен некоторому нормальному алгоритму в этом же алфавите.
Слайд 99 Это утверждение является гипотезой; оно не может быть строго
доказано, т.к. с одной стороны, фигурирует интуитивное понятие «всякий алгоритм»,
а с другой – строго определенное понятие «нормальный алгоритм». На это утверждение можно смотреть как на закон, который не доказан, но который проверен и подтвержден всем нашим опытом.В пользу высказанной гипотезы говорит и тот факт, что никому еще не удалось сформулировать пример такого алгоритма в алфавите А, для которого нельзя было бы построить эквивалентный ему нормальный алгоритм.
Слайд 100 Можно отметить, что теория нормальных алгоритмов строится в рамках
абстракции потенциальной осуществимости.
Абстракция потенциальной осуществимости — один из видов
абстракции, при которой мысленно отвлекаются от реальных границ конструктивных возможностей человеческого создания, связанных с ограниченностью жизни человека в пространстве и времени, и руководствуются принципами потенциальной, т.е. становящейся бесконечности, в отличие от абстракции актуальной, т.е. завершенной бесконечности.
Слайд 101 Этот вид абстракции не предполагает индивидуализации каждого элемента бесконечного
множества, не предполагает, что может быть осуществлено бесконечное число операций,
но основывается на том, что может быть осуществлено любое конечное число операций — шагов, букв, чисел и т.п.Например, при рассмотрении слов в данном алфавите абстракция потенциальной осуществимости будет означать, по А.А. Маркову, отвлечение от практических границ наших возможностей в пространстве, времени и материале при построении слова. Так, это бывает в том случае, когда отвлекаются от практической невозможности написать на данной доске мелом сколь угодно длинные слова и начинают рассуждать так, как если бы указанная процедура была возможна.
Слайд 102 Понимать под «построением» с точки зрения абстракции потенциальной осуществимости
(дается и другая трактовка) — это значит понимать под «построением»
не только практически выполнимое в данных материальных условиях построение, но и построение потенциально осуществимое, т.е. осуществимое в предположении, что после каждого шага процесса построения требуемого слова мы располагаем возможностями для выполнения следующего шага.
Слайд 103 Абстракция потенциальной осуществимости наиболее широко применяется в области информационных
технологий и вычислительной техники, она лежит в основаниях таких теорий,
как теория алгоритмов, теория абстрактных автоматов, булевых алгебр и т.п., составляющих теоретический фундамент вычислительных систем. Но теории, применяющие абстракцию потенциальной осуществимости, как и любая другая теория, имеют ограниченную область применения.Показано, что допустимость применения абстракции потенциальной осуществимости ограничена предположением о том, что изменения некоторого свойства объекта не приводят к изменению основных свойств (качеств) данного объекта. Построенные в принятом алфавите слова надо рассматривать как потенциально осуществимые конструктивные объекты.
Слайд 104 В заключение можно отметить, что алгоритм А.А. Маркова можно
рассматривать наравне с частичнорекурсивными функциями и машинами Тьюринга как «стандартную
форму» представления для любого заданного алгоритма, т.е. полагается, что вообще любой алгоритм может быть задан в форме нормального алгоритма Маркова. Это утверждение можно рассматривать как гипотезу, и притом значительно менее ясную, чем гипотеза Маркова, о которой шла речь выше, т.к. она не может даже быть высказана в точных терминах, но интуитивный смысл ее очевиден.
Слайд 106
Известно, что все рассмотренные ранее модели алгоритмов возникли в
результате попыток решить как теоретические проблемы (например, определение алгоритмической разрешимости
задачи), так и практические (например, определение принципов работы устройства, производящего автоматизированную обработку информации).
Слайд 107 Различные варианты решения проблем привели к построению так называемых абстрактных
алгоритмических моделей, которые приведены на рисунке. Очевидно, что имеет смысл
рассмотреть взаимосвязь отдельных моделей.
Слайд 108 Традиционно все алгоритмические задачи принято делить на два больших класса:
Задачи, связанные с вычислением значения функции.
Задачи, связанные с распознаванием
принадлежности объекта заданному множеству, т.е. проверка обладания объектом, заданным свойством.
Слайд 109 В первом случае алгоритм Q начинает работать с исходными данными,
представленными в виде некоторого слова P, составленным на основе алфавита
A, и за конечное число шагов (преобразований) он должен остановиться и выдать результат Pn=fq(P). Результат зависит, т.е. является функцией, от исходного слова, а также последовательности обработки, т.е. самого алгоритма. При этом вычисление понимается в широком смысле – как алфавитное преобразование.
Слайд 110 В задачах, отнесенных ко второму классу, в результате выполнения
алгоритма проверяется истинность высказывания, что xM, и выдается один из
двух возможных результатов: истина или ложь.Этот класс можно считать разновидностью первого, поскольку предикат – это функция, принимающая два значения в зависимости от условия. Тем не менее разделение этих классов задач полезно, т.к. приводит к двум важным понятиям теории алгоритмов: вычислимая функция и разрешимое множество.
Функция называется вычислимой, если имеется алгоритм, вычисляющий ее значение. Множество называется разрешимым, если имеется алгоритм, который для любого объекта позволяет определить, принадлежит он данному множеству или нет.
Слайд 111 Эти определения не являются строгими, т.к. не позволяют предсказать,
окажется ли некоторая функция вычислимой или нет. Поэтому очень важным
моментом для построения теории алгоритмов было формулирование тезиса Черча, который утверждал, что всякая частично рекурсивная функция является вычислимой. Другими словами, если функцию удалось простроить с помощью суперпозиции, рекурсии и минимизации из простейших функций, то существует алгоритм, ее вычисляющий.Далее последовал тезис Тьюринга, утверждавший, что для всякой вычислимой функции можно построить машину Тьюринга, которая ее вычисляет.
Слайд 112 Позднее была доказана теорема о сводимости одной алгоритмической модели
к другой, следствием которой явились утверждения типа: «любую рекурсивную функцию
можно вычислить с помощью соответствующей машины Тьюринга» или «для любой задачи, решаемой с помощью машины Тьюринга, существует решающий ее нормальный алгоритм Маркова».Таким образом, все модели оказываются эквивалентными, и это имеет глубокий смысл, т.к. результат обработки информации определяется алгоритмом и входными данными, но не зависит от вида алгоритмической модели.
Слайд 114
Всякому алгоритму соответствует задача, для решения которой он был
построен. Обратное утверждение в общем случае является неверным по двум
причинам: во-первых, одна и та же задача может решаться различными алгоритмами; во-вторых, можно предположить пока, что имеются задачи, для которых алгоритм вообще не может быть построен.
Слайд 115 Под термином «алгоритм» в математике обычно понимается процедура, позволяющая
путем выполнения последовательности определенных элементарных шагов получать однозначный результат, не
зависящий от того, кто эти шаги выполнял, т.е. само построение решения можно считать доказательством существования алгоритма.Однако известен целый ряд математических задач, разрешить которые в общем виде не удавалось. Это в свою очередь привело к проблеме, которую можно сформулировать так: возможно ли, не решая задачи, доказать, что она алгоритмически неразрешима, т.е. невозможно построить алгоритм, который обеспечил бы ее общее решение.
Решение этой проблемы очень важно в первую очередь с практической точки зрения, т.к. сразу позволит избежать затрат времени и ресурсов на решение проблем, которые являются алгоритмически неразрешимыми.
Слайд 116 Кроме того, она дала толчок развитию и теоретической мысли,
т.к. понадобилось сначала дать строгое определение алгоритма, без чего обсуждение
его существования просто не имело смысла. Построение такого определения, как мы знаем, привело к появлению формальных алгоритмических моделей, что дало возможность математического доказательства неразрешимости ряда задач.Доказательство сводилось к тому, что показывалась невозможности построения рекурсивной функции, решающей задачу, либо к невозможности построения машины Тьюринга для нее, либо к невозможность построения нормального алгоритма Маркова.
То есть задача считается алгоритмически неразрешимой, если не существует машины Тьюринга, или рекурсивной функции, или нормального алгоритма Маркова, которой ее решает, что естественным образом вытекает из уже показанной ранее эквивалентности алгоритмических моделей.
Слайд 117
Первые доказательства алгоритмической неразрешимости касались самой теории алгоритмов. Было доказано,
что неразрешима задача установления истинности произвольной формулы исчисления предикатов, т.е.
исчисление предикатов неразрешимо (теорема была доказана в 1936 г. Черчем). Кроме того, к алгоритмически неразрешимой относится и так называемая проблема остановки, формулировка которой звучит следующим образом: можно ли по описанию алгоритма и входным данным установить, завершится ли выполнение алгоритма результативной остановкой?
Слайд 118 Эту проблему легко проиллюстрировать практическим примером. Действительно, одна из
самых распространенных ошибок при разработке программ связана с зацикливанием, т.е.
ситуацией, когда цикл не завершается и не происходит завершения работы программы и остановки.Неразрешимость проблемы остановки означает, что нельзя создать общий, т.е. применимый для любой задачи, алгоритм отладки программ.
Неразрешимой оказывается и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который бы для любых двух алгоритмов выяснял, всегда ли они приводят к одному и тому же результату или нет.
Слайд 119 Несомненная польза определения алгоритмической неразрешимости состоит в том, что
если для задачи доказано, что она алгоритмически неразрешима и это
доказательство имеет смысл закона, то можно не тратить усилия на поиск решения, подобно тому, как законы сохранения энергии в физике делают бессмысленными попытки построения вечного двигателя.Однако следует помнить, что алгоритмическая неразрешимость какой-либо задачи в общем виде допускает, что имеют решения какие-либо ее частные случаи. Можно считать справедливым и обратное утверждение: решение частного случая задачи не означает, что ее можно решить в самом общем случае, т.е. не свидетельствует о ее общей алгоритмической разрешимости.
Слайд 120 Важность и практическая значимость абстрактных алгоритмических систем состоит в
том, что они позволяют оценить возможность нахождения общего решения некоторого
класса задач.Существование алгоритмически неразрешимых проблем приводит к тому, что оказывается невозможным построить универсальный алгоритм, пригодный для решения любой задачи, а следовательно, не имеет смысла предпринимать шаги по его созданию.
С алгоритмически неразрешимыми проблемами часто сталкиваются при решении задач, относящихся к области искусственного интеллекта. Известно, что невозможно полностью автоматизировать такие аспекты человеческой деятельности, как: перевод с одного языка на другой, выделение смыслового содержания некоторого текста, обучение других людей, сочинение стихов и т.п.
