Обзорный курс по теоретической информатике

Санкт-Петербург, осень 2013

Описание

Курс призван познакомить слушателей с некоторыми классическими результатами и идеями теоретической информатики (Theoretical Computer Science), которые будут полезны как исследователям, так и программистам, желающим расширить свой кругозор. В частности:

  • Мы узнаем, что теоретическая информатика предлагает свои трактовку понятия доказательства: если в математике доказательство обязано быть текстом, то информатика рассматривает случаи, когда доказательство — это интерактивный процесс, иногда для проверки доказательства его не обязательно полностью прочитывать, а иногда можно доказывать, не сообщая никакой дополнительной информации, кроме верности доказываемого утверждения.

  • Выясним, как случайные числа помогают при построении алгоритмов и сведений между задачами.

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

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

  • Познакомимся с классическими параллельными алгоритмами.

  • Узнаем классическое и алгоритмическое понятие количества информации.

  • Поговорим о коммуникационной сложности при совместном вычислении функции, когда сложность измеряется количеством информации, которым должны обменяться участники. Выясним, какое отношение коммуникационная сложность имеет к сложности обычных алгоритмов.

  • Выясним, что множество языков, которые задаются регулярными выражениями или конечными автоматами, совпадают с множеством языков, которые распознаются с константной памятью. Изучим, какие задачи можно решить с логарифмической памятью.

Преподаватели