• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2019/2020

Вычислимость и сложность

Язык: русский

Программа дисциплины

Аннотация

В курсе будут обсуждаться примеры неразрешимых проблем и сведение одних проблем к другим. Слушатели научатся быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели, различать различные виды трудности задач. Для освоения учебной дисциплины студенты должны владеть следующими знаниями и компетенциями: Математика в объеме программы средней школы.
Цель освоения дисциплины

Цель освоения дисциплины

  • Целями освоения дисциплины «Вычислимость и сложность» являются: знакомство с ос-новными вычислительными моделями, используемыми в теории вычислений (машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами), знакомство с понятиями алгоритма, вычислимой функции, разрешимых и перечислимых множеств.
Результаты освоения дисциплины

Результаты освоения дисциплины

  • В результате студент должен знать основные вычислительные модели, используемыми в теории вычислений (многоленточные машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами).
  • В результате студент должен знать понятия алгоритма, вычислимой функции, разрешимых и перечислимых множеств, нумерации вычислимых функций.
  • В результате студент должен уметь строить алгоритмы для решения задач.
  • В результате студент должен уметь приводить примеры неразрешимых проблем и научить сводимости одних проблем к другим.
  • В результате студент должен уметь быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели.
  • В результате студент должен владеть методами установления вычислительной трудности задач различного типа: давать представление о том, как устанавливается "эталонные задачи", и научиться сводить данную задачу к одной из эталонных трудных задач.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Вычислительные модели: многоленточные машины Тьюринга, частично-рекурсивные функции, машины с неограниченными регистрами. Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов. Тезис Чёрча.
  • Понятие вычислимой функции, разрешимого множества.
  • Перечислимые множества.
  • Перечислимость и разрешимость (теорема Поста, теорема о проекции разреши-мого множества).
  • Теорема о графике вычислимой функции.
  • Универсальные вычислимые функции.
  • Построение перечислимого неразрешимого множества.
  • Алгоритмически неразрешимые проблемы в теории алгоритмов.
  • Примеры других алгоритмически неразрешимых проблем в алгебре и теории чисел.
  • m-Сводимость, m-полные перечислимые множества.
  • Полиномиальная эквивалентность по времени и памяти вычислительных моде-лей. Класс P функций, вычислимых за полиномиальное время.
  • Сводимость одной задачи к другой. Полные в данном классе задачи.
  • Класс NP функций, вычислимых за полиномиальное время, и эквивалентные определения.
  • NP-трудные и NP-полные задачи. Проблема перебора (P=NP?) и предположи-тельная трудность NP-трудных задач.
  • Теорема Кука-Левина об NP-полноте проблемы выполнимости нулевых функ-ций.
  • NP-полнота других задач: 3-КНФ, 3-РАСКРАСКА, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ГАМИЛЬТОНОВ ЦИКЛ.
  • Класс PSPACE функций, вычислимых за полиномиальное количество памяти, и эквивалентные определения.
  • Теорема Савича.
  • PSPACE полнота задачи TQBF и других.
Элементы контроля

Элементы контроля

  • неблокирующий Created with Sketch. Первое индивидуальное домашнее задание
  • неблокирующий Created with Sketch. Первая контрольная работа
  • неблокирующий Created with Sketch. Второе домашнее задание
  • неблокирующий Created with Sketch. Вторая контрольная работа
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.3 * Вторая контрольная работа + 0.2 * Второе домашнее задание + 0.3 * Первая контрольная работа + 0.2 * Первое индивидуальное домашнее задание
Список литературы

Список литературы

Рекомендуемая основная литература

  • - Бабенко М.А., Левин М.В. — Введение в теорию алгоритмов и структур данных - Московский центр непрерывного математического образования - 2016 - ISBN: 978-5-4439-2396-3 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/80136

Рекомендуемая дополнительная литература

  • - Львовский С.М. — Работа в системе LaTeX - Национальный Открытый Университет "ИНТУИТ" - 2016 - ISBN: - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/100443