Теория вычислений 2022

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.

Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.


Общая информация

Официальное название: «Теория вычислений».

Преподаватель: Павел Захаров, телеграм: @DuckBinLaden, Анна Енгоян, телеграм: @yaognennaya

Время и место (с 31 января): понедельник, 16:20, корпус на Покровском бульваре, аудитория TBA.

Записи занятий: А надо ли?

Телеграм-чат: TBA

Таблица с оценками: TBA

История

31 января 2021. Занятие 1. TBA

Правила оценивания

Оценка складывается из двух пунктов:

  • Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.
  • Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).

Итоговая оценка формируется как Oитоговая = 0,7 * Oзадачки + 0,3 * Оэкз.

Наборы задач

  • TBA

Интересные статьи

Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).

  • J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).
  • Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).
  • Richard M. Karp. Reducibility among combinatorial problems (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).
  • M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)

Литература

  1. Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
  2. Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
  3. Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)