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

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

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

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

Смотрите также