- •Исторически обзор теории алгоритмов
- •Определение машины Тьюринга
- •Тезис Черча-Тьюринга
- •Машина Маркова
- •Нумерация мт
- •Пример невычислимой функции, построенной по методу диагонализации Кантора.
- •Распознающие машины Тьюринга и языки. Проблема распознавания языков.
- •Неразрешимость проблемы самоприменимости.
- •Неразрешимость проблемы остановки.
- •Другие примеры неразрешимых алгоритмически задач.
- •Методы задания машин Тьюринга.
- •Граф-схемы и их связь диаграммой состояний автоматов.
- •Рекурсивные функции и их построение из простейших.
- •Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.
- •Тезис Черча.
- •Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.
- •Сложность. Подходы к определению сложности алгоритмов.
- •Алгоритмическая, информационная и инфологическая сложность.
- •19. Понятие вычислительной сложности. Примеры ее определения.
- •20. Детерминированная и недетерминированная машина Тьюринга.
- •21. Класс p и np.
- •22. Классы со-np, pspace, npspace.
- •23. Задача выполнимость и теорема с.Кука о полноте задачи выполнимость.
- •24. Другие np-полные задачи. Примеры сводимости в классе np.
- •25. Метод резолюции Робинсона для задачи выполнимость.
- •26. Метод отсечение литер для задачи выполнимость.
- •27. Метод групповых резолюций для задачи выполнимость.
- •28. Гипотеза p≠pn и ее обоснование.
- •29. Дерево решений. Эвристическая оценочная функция.
- •30. Распознавание регулярных языков.
Распознающие машины Тьюринга и языки. Проблема распознавания языков.
Существуют различные МТ одни выполняют счетные функции(умножение).
Сущ. тип машин которые могут быть распознающими.
Если машина видит слово, а точнее прочитывает его она может сказать:
в первом случае машина закончит свою работу в состоянии YES(т.е слово написано правильно), а во втором – в состоянии NO(не правильно). Подобные машины называют распознающими. Распознать некоторый объект – значит определить, удовлетворяет ли он определенным условиям или нет. Задача распознавания в общем может быть неразрешимой. Например, нельзя построить распознаватель для выяснения вопроса о существовании рациональных корней произвольного диофантова уравнения, о чем говорилось во введении.
Теорема. Всякий недетерминированный регулярный автомат можно реализовать с помощью эквивалентного детерминированного регулярного автомата.
Неразрешимость проблемы самоприменимости.
Алгоритмическая неразрешимость проблемы самораспознавания.
Любопытно заметить, что данная проблема имеет содержательный аналог в лице проблемы о деревенском брадобрее. Последняя формулируется так. В одном селе брадобрей бреет тех и только тех людей, которые не бреются сами. Спрашивается, бреет ли он самого себя?
Ответ не может быть ни положительным, ни отрицательным. Значит, такого брадобрея не существует (брадобрей играет роль машины для распознавания языка L.)
Неразрешимость проблемы остановки.
В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:
Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.
Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы остановки для любых возможных входных данных не может существовать. Мы можем сказать, что проблема остановки неразрешима на машине Тьюринга.
Другие примеры неразрешимых алгоритмически задач.
В математике проблемой разрешения (Entscheidungsproblem) называется задача, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения S на этом языке), и после конечного числа шагов останавливался бы и выдавал один из двух ответов: «Истина» или «Ложь», в зависимости от того, истинно или ложно утверждение S. Не требуется, чтобы алгоритм давал какое-либо обоснование своего ответа, однако ответ всегда должен быть верным. Такой алгоритм мог бы, к примеру, определить, истинны ли такие утверждения, как гипотеза Гольдбаха или гипотеза Римана, несмотря на то, что никакого доказательства (или опровержения) этих утверждений пока не известно.
Фрактал(множество Мандельдеброта) множества Мандельброта. Простое хранение 24-битного цвета каждого пикселя этого изображения требует 1,62 миллиона бит; но маленькая компьютерная программа может воспроизвести эти 1,62 миллиона бит используя определение множества Мандельброта. Таким образом, колмогоровская сложность «сырого» файла, кодирующего это изображение, много меньше 1,62 миллиона бит.