1. Исторически обзор теории алгоритмов.
2. Определение МТ.
3. Тезис Черча-Тьюринга.
4. Машина Маркова.
5. Нумерация машин Тьюринга.
6. Пример невычислимой функции, построенной по методу диагонализации Кантора.
7. Распознающие машины Тьюринга и языки. Проблема распознавания языков.
8. Неразрешимость проблемы самоприменимости.
9. Неразрешимость проблемы остановки.
10. Другие примеры неразрешимых алгоритмически задач.
11. Методы задания машин Тьюринга.
12. Граф-схемы и их связь диаграммой состояний автоматов.
13. Рекурсивные функции и их построение из простейших.
14. Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.
15. Тезис Черча.
16. Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.
17. Сложность. Подходы к определению сложности алгоритмов.
18. Алгоритмическая, информационная и инфологическая сложность.
19. Понятие вычислительной сложности. Примеры ее определения.
20. Детерминированная и недетерминированная машина Тьюринга.
21. Класс P и NP.
22. Классы со-NP, PSPACE, NPSPACE.
23. Задача ВЫПОЛНИМОСТЬ и теорема С.Кука о полноте задачи ВЫПОЛНИМОСТЬ.
24. Другие NP-полные задачи. Примеры сводимости в классе NP.
25. Метод резолюции Робинсона для задачи ВЫПОЛНИМОСТЬ.
26. Метод отсечение литер для задачи ВЫПОЛНИМОСТЬ.
27. Метод групповых резолюций для задачи ВЫПОЛНИМОСТЬ.
28. Гипотеза P≠ТЗ и ее обоснование.
29. Дерево решений. Эвристическая оценочная функция.
30. Распознавание регулярных языков.
Исторически обзор теории алгоритмов
Слово
алгоритм происходит от имени
среднеазиатского ученого средневековья
Муххамад ибн Мусаал-Хорезми
жил
с 783 по 850 гг. он написал книгу «Об индийском
счете». С помощью арабских чисел описал
действия над ними в столбец. 817-840 –
возглавлял библиотеку. 842-848 – возглавлял
экспедицию-это последние упоминания.
Вплоть
до
30-х
годов нашего столетия понятие алгоритма
оставалось интуитивно понятным, имевшем
скорее методологическое, а не математическое
значение. Вместе с тем уже древние греки
обнаружили ряд проблем, для которых им
не удалось построить алгоритм (или
разрешающую процедуру). Такими проблемами
были проблема разбиения произвольного
угла на три равных угла с помощью циркуля
и линейки, проблема построения круга,
равновеликого заданному квадрату,
проблема отыскания рациональных корней
произвольного диафанова уравнения
(уравнение с рациональными коэффициентами
и целочисленными переменными), например,
.Решение
таких проблем потребовало привлечения
новых логических средств.
Алгоритм – точное предписание определения вычислительного процесса, идущий под варьированием исходных данных к исходному результату.
Алгоритм – это точное предписание о выполненных в определенном порядке некоторых системных операций, ведет к решению всех задач данного числа.
Алгоритм – это последовательность действий, которое ведет к конечному результату.
Алгоритм – это последовательность действий, направленное на получение определенного результата за число шагов.
Свойства алгоритма:
массовость
повторяемость
детерминизм
дискретность
результативность
завершаемость
Массовость - возможность использовать алгоритм для решения целого круга задач в рамках некоторой общей проблемы.
Повторяемость - получение одного и того же результата для одних и тех же данных.
Детерминизм - означает, что шаги алгоритма не оставляют двусмысленности и выбор каждого последующего шага определен однозначно.
Дискретность – алгоритм может представлять процесс решения задачи, как по следованное выполнение некоторых простых шагов, для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результате обозначается во времени дискретно.
Результативность – завершение алгоритма определенным результатом.\
Завершаемость – при корректно завершении исходных данных алгоритм должен завершает работу и выдавать результат за конечное число шагов. Существует не завершающий алгоритм, теоретически такой алгоритм не может быть результат, но вероятность =0.
В конце 17 в. немецкий ученый Г.В. Лейбниц выдвинул идею об универсальной характеристике, т.е. об универсальном решателе задач. Для реализации своей идеи Лейбниц ввел язык для записи задач, который можно назвать прообразом языка логики первого порядка. Существенным толчком в деле разработки точного математического понятия алгоритма была поставленная великим немецким математиком Д.Гильбертом задача построения доказательства произвольной формулы, выразимой в языке данной формальной теории, средствами этой теории. Средствами этой теории. Ему удалялось доказать, что любая полезная система аксиом является неполный. В ней существует высказывания, истинность которых нельзя опровергнуть или подвергнуть. Точное математически строгое определение алгоритма сформулировал английский ученый Алан Тьюринг. По его мнению ученый рассматривал проблему представления вычисления функции с точки зрения их записи из простейших. Было введено понятие класс рекурсивных и частично рекурсивных функций.