- •1. Словарные функции.
- •Словарные функции.
- •2. Вычислимые функции. Мт.
- •3. Словарное предствление мт.
- •4. Массовые алгоритмические проблемы. Разрешимые и перечислимые множества.
- •5. Теорема Поста.
- •6. Проблема остановки. Теорема Тьюринга.
- •7. Проблема пустой ленты. Проблема зацикливания.
- •Проблема зацикливания.
- •8. Понятие массовой и индивидуальной задачи.
- •9. Понятие полиномиального алгоритма и труднорешаемой задачи
- •10. Понятие схемы кодирования.
- •11. Задачи распознавания. Переход от оптимизационной задачи к задаче распознавания
- •Задачи разновидности языка и кодирование.
- •Примеры. Массовая задача и изоморфизм подграфу.
- •12. Язык. Связь между задачами распознавания и языками. Задачи разновидности языка и кодирование.
- •Примеры. Массовая задача и изоморфизм подграфу.
- •13. Детерминированные мт и класс p.
- •14. Недетерминированное вычисление и класс np.
- •15. Взаимоотношения между класами p и np.
- •16. Полиномиальная сводимость.
- •18. Теорема Кука. 6 основных np-полных задач.
- •Доказательство результатов об np-полноте.
- •Шесть основных np-полных задач.
- •19. Методы док-ва np-полноты. Метод сужения. Некоторые методы доказательства np-полноты.
- •Сужение задачи.
- •20. Методы доказательства np-полноты. Метод локальной замены Некоторые методы доказательства np-полноты.
- •Локальная замена.
- •21. Методы доказательства np-полноты. Метод построения компонент. Некоторые методы доказательства np-полноты.
- •Метод построения компонент.
- •22. Анализ подзадач np-полной задачи. Применение теории np-полноты для анализа задач.
- •Анализ подзадач.
- •23. Сильная np-полнота.
- •24. Псевдополиномиальные алгоритмы.
- •25. Именная форма. Высказывания. Операции над высказываниями.
- •26. Основные логические законы. Логические тождества.
- •27. Правила обращения с кванторами.
- •28. Техника доказательств.
- •29. Операции над множествами и одноместными предикатами.
- •30. Булевы функции.
3. Словарное предствление мт.
МТ однозначно задаётся своей программой. Если упорядочить её команды произвольным образом и применить описанный ниже способ кодировки, с помощью которого последовательность команд представлена цепочкой в алфавите МТ, то мы получим её описание в собственном алфавите.
Пусть V – алфавит МТ, Q – множество её состояний, K(q) – порядковый номер соответствующий номеру состояния q.
Введём вспомогательный символ *, не входящий в алфавит V. Каждой команде вида: qa→q’a’d, сопоставим цепочку в алфавите W, который определяется . Сопоставленная цепочка будет иметь вид: *K(q)a*K(q’)a’d. Упорядоченной последовательности команд будет соответствовать последовательность цепочек в алфавите W, конкатенация этих цепочек определяет цепочку αT. Последняя однозначно описывает машину Тьюринга T с точностью до переименованного состояния.
Следующий шаг заключается в переходе от представления в алфавите W в алфавит V.
Пусть алфавит V содержит n символов, упорядочим их произвольным образом. Алфавит W упорядочим так, чтобы символы из алфавита V имели те же номера, а дополнительные символы имели номера:
Закодировав согласно описанному ранее способу все цепочки из V* (перенумеровав их) и все цепочки из W*, мы можем, зная номер цепочки αT, сопоставить ей цепочку βT из множества V* с тем же самым номером. Найденная цепочка будет словарным представлением МТ в её алфавите и по этой цепочке βT можно однозначно восстановить машину Тьюринга с точностью до наименования её состояния.
4. Массовые алгоритмические проблемы. Разрешимые и перечислимые множества.
Необходимо указать алгоритм, который бы определял, обладает ли предъявляемый объект из некоторого класса объектов интересующим нас свойством. Другими словами, необходимо определить, принадлежит ли рассматриваемый объект множеству M всех объектов обладающих заданным свойством. Если существует такой частичный алгоритм, то говорят, что множество перечислимо, а поставленная массовая алгоритмическая проблема частично разрешима. Если же алгоритм всюду определён, то множество M разрешимо и поставленная проблема также разрешима.
Пусть V – алфавит, и множество M является подмножеством всех цепочек V*. Функция FM называется предикатом отображения: .
Частичная характеристическая функция множества M – это функция , которая определяется только для цепочек из множества M, т.е. , .
Множество M называется разрешимым, если его характеристическая функция FM вычислима. Множество M называется перечислимым, если его частичная характеристическая функция вычислима. Разрешённое множество M означает, что существует всегда останавливающаяся МТ , позволяющая для любых цепочек из V* через конечное число шагов узнать, принадлежит ли эта цепочка множеству M или нет. Перечислимость M означает, что существует МТ , которая останавливается только в том случае, когда поданная на вход цепочка принадлежит M.
5. Теорема Поста.
Теорема Поста:
Множество разрешимо тогда и только тогда, когда перечислимыми являются множество M и его дополнение .
Доказательство.
Необходимость:
Если множество M разрешимо, то характеристическая функция этого множества FM вычислима, т.е. существует МТ , которая останавливается в обоих случаях. Частичная функция HM реализации МТ из машины зацикливается в случае, когда цепочка не принадлежит M. МТ строится аналогично.
Достаточность:
Если M и перечислимы, то существуют МТ и , которые вычисляют частичные характеристические функции. Для построения МТ используем следующий алгоритм:
Последовательно выполняются команды, сначала , потом . Если останавливается МТ , то в качестве ответа выдаётся символ 1. Если не останавливается, то запускается , если она остановилась, то выдаётся в качестве ответа 0. Если она не остановилась, то процесс повторяется. За конечное число шагов функционирование построенной МТ завершится.