Информатика и вычислительная техника
Статья
  • формат doc
  • размер 230,69 КБ
  • добавлен 17 июня 2013 г.
Алгоритмы и алгоритмическая сложность
Лектор Герман О.В. Остальные выходные данные отсутствуют.
Содержание.
Введение в теорию алгоритмов.
Машины Тьюринга.
Распознавание языков машинами Тьюринга.
Рекурсивные множества и функции.
Алгоритмически неразрешимые проблемы.
Использование машин Тьюринга для обоснования универсальности языка программирования.
Понятие вычислительной сложности.
Распознавание языков. язык выполнимость.
Метод резолюций Робинсона.
Инфологическая сложность задач.
Постулаты теории инфологической сложности.
Обоснование несуществования эффективного алгоритма в классе задач распознавания свойств.
Дополнительные сведения о структуре класса NP.
Примеры NP- полных задач.
Описание задач на языке логики.
Метод групповых резолюций.
Обзорная.
Похожие разделы