Содержание
- 2. В широком смысле слова алгоритм– это текст, который в определенных обстоятельствах может привести к однозначному развитию
- 3. Каждый алгоритм служит для решения некоторого класса задач. Задачи должны быть записаны на некотором языке. Результат
- 4. Свойства алгоритма Дискретность. Алгоритм – это процесс последовательного построения выражений таким образом, что в начальный момент
- 5. Детерминированность. Выражение, получаемое в какой-то не начальный момент, однозначно определяется выражением, полученным в предшествующие моменты времени.
- 6. Элементарность шагов алгоритмов. Закон получения последующего выражения из предшествующего должен быть простым. (Для исполнителя!).
- 7. Массовость алгоритма. Начальное выражение может выбираться из некоторого потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать
- 8. Результативность алгоритма. Последовательный процесс построения выражений языка должен быть конечным и давать результат, то есть решение
- 9. Основная задача теории алгоритмов – это решение проблемы алгоритмической разрешимости, а не поиск правила (способа/метода) ее
- 10. В рамках такого подхода к определению понятия алгоритма можно определить три основных направления: Первое направление связано
- 11. Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в
- 12. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это
- 13. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это
- 14. Частично рекурсивные функции
- 15. Таким образом процесс алгоритмического решения задачи должен быть дискретным. Он распадается на элементарные шаги и представляет
- 16. Поскольку, тексты (слова над конечным алфавитом) могут быть занумерованы, то цепочка текстов «задача– решение» превратится в
- 17. Такой цепочке можно поставить в соответствие числовую функцию реализующую отображение определенную на множестве номеров задач и
- 18. Далее, если не сделано специальных оговорок, мы будем предполагать, что рассматриваемые функции являются числовыми, их значения
- 19. Если функция определена на собственном подмножестве множества то будем называть ее частично рекурсивной.
- 20. Определим простейшие функции и элементарные операции над функциями.
- 21. 1. Суперпозиция(или композиция). Пусть даны частичная функция и частичные функции Элементарные операции над частичными функциями.
- 23. В противном случае функция считается неопределенной. Для функции полученной суперпозицией функций будем использовать обозначение
- 24. Примеры.
- 25. 2.Рекурсия Начнем с частных случаев. Пусть заданы функция и число a. Уравнения: однозначно определяют функцию
- 26. Последовательно вычисляя, находим:
- 33. 3. Минимизация.
- 36. Частичные функции, которые могут быть получены из простейших с помощью конечного числа операций суперпозиции, рекурсии и
- 37. Запись частично рекурсивной функции с помощью простейших функций и операций будем называть рекурсивной схемой. Рекурсивная схема
- 38. По рекурсивной схеме функции f может быть построено ее рекурсивное описание: конечная последовательность частичных функций такая,
- 39. Одна и та же функция может быть определена с помощью разных рекурсивных схем. Это согласуется с
- 41. Рекурсивная схема представляет собой слово над счетным алфавитом, содержащим в качестве символов натуральные числа, обозначения для
- 42. Вычислимость и разрешимость Отметим, что традиционно считающиеся вычислимыми функции имеют рекурсивные описания и, значит, частично рекурсивны.
- 43. Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна. Построим пример
- 44. Подмножество множества натуральных чисел называется разрешимым, если его характеристическая функция рекурсивна.
- 45. Содержательно разрешимость множества M означает, что существует алгоритм, позволяющий по любому числу x определить за конечное
- 46. Подмножество множества натуральных чисел M⊂N называется перечислимым, если оно является областью значений некоторой общерекурсивной функции f.
- 47. Утверждение: Всякое непустое разрешимое множество M является перечислимым. Доказательство. Определим перечисляющую функцию f. Пусть m– произвольный
- 48. Обратное, вообще говоря, неверно. Не всякое перечислимое множество является разрешимым. Перечислимое множество разрешимо лишь в том
- 49. Поскольку, что частично рекурсивные функции можно эффективно перенумеровать, используя их рекурсивные описания, то некоторые номера соответствуют
- 50. Теорема. Множество номеров общерекурсивных функций не перечислимо. Доказательство. Предположим противное. Пусть – общерекурсивная функция, множеством значений
- 51. Это определение дает алгоритм вычисления значений функции . В соответствии с тезисом Черча, функция частично рекурсивна,
- 52. Вообще неперечислимые и неразрешимые семейства функций– это не «экзотика», а, скорее, норма. Приведем без доказательства следующую
- 53. Иными словами, если C– некоторое семейство вычислимых функций такое, что есть функции, входящие в это семейство,
- 54. Так, по номеру функции нельзя узнать, является ли она монотонной, периодической и т.п. Заметим, что, нумеруя
- 55. Теорема Райса утверждает, что по номеру алгоритма нельзя узнать, периодична ли, например, функция, вычисляемая в соответствии
- 56. Машина Тьюринга Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь
- 57. Идею такой машины предложил в 1937 году английский математик А. Тьюринг.
- 58. Машина Тьюринга включает в себя: Внешний алфавит - конечное множество символов В этом алфавите в виде
- 59. Внутренний алфавит - конечное множество символов Для любой машины число состояний фиксировано. Два состояния имеют особое
- 60. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на
- 61. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е.
- 62. Логическое устройство. В зависимости от текущего внутреннего состояния, и считанного с ленты символа, переходит в новое
- 63. Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой
- 64. Таким образом, машина Тьюринга может быть представлена в виде четверки:
- 65. Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом
- 66. Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга
- 67. Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо,
- 68. ПРИМЕР Построим машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.
- 69. Внешний алфавит - . Внутренний алфавит - , при этом состояние сохраняется до тех пор, пока
- 70. При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно,
- 71. Начальное состояние , головка установлена на первой единице последовательности единиц. Рабочая программа машины Тьюринга имеет вид:
- 72. Проверим работоспособность машины Тьюринга:
- 73. Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.
- 74. Нормальные алгоритмы Маркова Нормальный алгоритм Маркова представляет собой систему подстановок
- 75. Слово z считается включенным в слово у, если у может быть представлено как:
- 76. Работа нормального алгоритма Маркова: Исходное слово просматривается слева направо с целью выявления вхождения первого правила подстановки.
- 77. После того, как первое правило больше не встречается в данном слове, аналогично применяется второе правило подстановки.
- 78. ПРИМЕР Построить нормальный алгоритм Маркова, стирающий последовательность единиц. Нормальный алгоритм Маркова для данной задачи представляет собой
- 79. Первая подстановка стирает все единицы до последней. Вторая (заключительная) подстановка заменяет последнюю единицу пробелом .
- 80. Тезис А. Черча. Если функция выполнима, то она может быть представлена в виде нормального алгоритма Маркова.
- 81. Один из видов чертежей– графы, которые, сохранив присущую чертежам наглядность, допускают точное теоретико-множественное описание и тем
- 83. Скачать презентацию