City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Selected Topics in Computer Science
Kazan / spring 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества

  • формулировку и доказательство можно понять за ограниченное время, у нас имеющееся
  • результат достаточно фундаментальный для того, чтобы практическим программистам стоило про него знать
  • результат не общеизвестный (последнее можно будет скорректировать по ходу дела)
Примерный перечень возможных тем:
  • понятие универсальной функции (хранимой программы) и диагональная конструкция алгоритмически неразрешимых проблем (перечислимого неразрешимого множества)
  • конкретные модели и доказательство неразрешимости конкретных задач (подстановки в словах = проблема тождества слов в полугруппах)
  • теорема Клини о неподвижной точке и self-referential конструкции
  • понятие сводимости как средство доказательства неразрешимости и полиномиальной сводимости как средства сравнения сложности
  • case study: потоки в сетях, сведение к ним (двудольного) паросочетания, вероятностный и детерминированный полиномиальные алгоритмы
  • правила доказательства свойств программ: примеры
  • вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
  • пример результата из теории сложности: что значит и почему BPP содержится в \( \Sigma_2 \)
  • теория смыкается с практикой: регулярные выражения и конечные автоматы
  • алгебра и computer science: разделение секрета, коды Рида–Соломона
  • алгебра и computer science: IP=PSPACE
  • пример из теории кодирования: границы Гилберта и Шеннона
  • пример из теории информации: шенноновская энтропия как граница для средней длины префиксного (или даже однозначного) кода
  • колмогоровская сложность (пример результата: теорема о сложности пары)
  • PCP: эквивалентность проверки доказательства и gap reduction
  • доказательства с двумя пруверами: пример, когда квантовая механика позволяет перейти границу для классической
  • псевдослучайные генераторы: почему тестирование равносильно предсказанию

Date and time Class|Name Venue|short Materials
26 March
18:00–21:10
Лекция 1-2, Lecture 2-й учебный корпус К(П)ФУ No
27 March
18:00–21:10
Лекция 3-4, Lecture 2-й учебный корпус К(П)ФУ No
28 March
18:00–21:10
Лекция 5-6, Lecture 2-й учебный корпус К(П)ФУ No