Контрольные вопросы по курсу “Алгоритмы и алгоритмическая сложность ”
Исторически обзор теории алгоритмов.+
Определение машины Тьюринга.+
Тезис Черча-Тьюринга. +
Машина Маркова.+
Нумерация машин Тьюринга.+
Пример невычислимой функции, построенной по методу диагонализации Кантора.+
Распознающие машины Тьюринга и языки. Проблема распознавания языков.+
Неразрешимость проблемы самоприменимости.+
Неразрешимость проблемы остановки.+
Другие примеры неразрешимых алгоритмически задач.+
Методы задания машин Тьюринга+-
Граф-схемы и их связь диаграммой состояний автоматов. +
Рекурсивные функции и их построение из простейших.+
Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции.+
Тезис Черча.+
Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.+
Сложность.Подходы к определению сложности алгоритмов.+
Алгоритмическая, информационная и инфологическая сложность.+
Понятие вычислительной сложности. Примеры ее определения.+
Детерминированная и недетерминированная машина Тьюринга.+
Класс P и NP.+
Классы co-NP, PSPACE, NPSPACE.+
Задача ВЫПОЛНИМОСТЬ и теорема С.Кука о полноте задачи ВЫПОЛНИМОСТЬ.+
Другие NP-полные задачи. Примеры сводимости в классе NP.+
Метод резолюций Робинсона для задачи ВЫПОЛНИМОСТЬ.+
Метод отсечения литер для задачи ВЫПОЛНИМОСТЬ.+
Метод групповых резолюций для задачи ВЫПОЛНИМОСТЬ.+
Гипотеза P≠NP и ее обоснование.+
Дерево решений. Эвристическая оценочная функция.+ (конспект)
Распознавание регулярных языков+
1. Исторический обзор теории алгоритмов
Слово алгоритм (algorithm) происходит от имени среднеазиатского ученого средневековья Муххамад ибн Мусаал-Хорезми ( Магомет, сын Моисея, из Хорезма (Узбекистан) (жил с 783 по 850 гг.)) В 1983 году отмечалось 1200-летие со дня его рождения. В Европе слово алгоритм использовалось для обозначения произвольных вычислительных процессов.
Вместе
с тем уже древние греки обнаружили ряд
проблем, для которых им не удалось
построить алгоритм (или разрешающую
процедуру). Такими проблемами были
проблема разбиения произвольного угла
на три равных угла с помощью циркуля и
линейки, проблема построения круга,
равновеликого заданному квадрату,
проблема отыскания рациональных корней
произвольного диофантова уравнения,
например,
.
С понятием алгоритма связывали последовательность операций, которая могла быть охарактеризована такими свойствами как
массовость
повторяемость
детерминизм
Массовость означала возможность использовать алгоритм для решения целого круга задач в рамках некоторой общей проблемы.
Повторяемость означает получение одного и того же результата для одних и тех же данных.
Детерминизм означает, что шаги алгоритма не оставляют двусмысленности и выбор каждого последующего шага определен однозначно.
В конце 17 в. немецкий ученый Г.В. Лейбниц выдвинул идею об универсальной характеристике, т.е. об универсальном решателе задач. Для реализации своей идеи Лейбниц ввел язык для записи задач, который можно назвать прообразом языка логики первого порядка. Лейбницу не удалось создать универсальный алгоритм.
Существенным толчком в деле разработки точного математического понятия алгоритма была поставленная великим немецким математиком Д.Гильбертом задача построения доказательства произвольной формулы, выразимой в языке данной формальной теории, средствами этой теории.
Точное математически строгое определение алгоритма сформулировал английский ученый Алан Тьюринг.
Важнейшими задачами теории алгоритмов являются следующие:
доказательство алгоритмической разрешимости/неразрешимости проблемы;
построение эффективного алгоритма или доказательство, что такого алгоритма нет;
анализ сложности алгоритма;
разработка языков спецификации алгоритмов и задач;
проблема построения сведения одних задач к другим; и др.
Проблема построения эффективных алгоритмов имеет прямое отношение к практике. Оказалось, что существует целый класс важных для практики задач, для которых до настоящего времени не удалось найти хороших решающих процедур. Более того, для этих задач нет даже приближенных алгоритмов. Классы этих задач известны как классы NP-полных и NP-трудных задач.
Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница.
Собственно, и для алгоритмов актуальна проблема построения доказательства того, что они правильно решают задачу. Поэтому уместно назвать алгоритмы, для которых требуемые доказательства имеются – доказательно конструируемыми алгоритмами.