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