Введение в теоретическую информатику

Обзор

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

Программа курса

• Урок 1.1 - Сложные проблемы
• Урок 1.2 - Анализ алгоритмов и RAM
• Урок 1.3 - Big O (Опционально)
• Урок 1.4 - Связывание похожих проблем
• Набор задач 1
• Урок 2.1 - Множество решений и неразрешимость
• Урок 2.2 - Недетерминированный RAM
• Урок 2.3 - SAT
• Урок 2.4 - Доказательство SAT (Опционально)
• Урок 2.5 - NP-полнота через сведения
• Набор задач 2
• Урок 3 - Решение NP-полных проблем
• Набор задач 3
• Урок 4.1 - Обрезка входных данных
• Урок 4.2 - Предобработка
• Урок 4.3 - Измерение сложности
• Набор задач 4
• Урок 5.1 - Фактор аппроксимации
• Урок 5.2 - Кратчайший тур
• Урок 5.3 - Сведения и факторы аппроксимации
• Урок 5.4 - PTAS
• Набор задач 5
• Урок 6.1 - Рандомизация
• Урок 6.2 - Что вы узнали
• Набор задач 6
• Урок 7.1 - Пределы вычислений
• Урок 7.2 - Больше неразрешимости
• Набор задач 7
• Экзамен

Инструкторы

• • Sebastian Wernicke
• • Sean Bennett
• • Sarah Norell