Список пройденных тем.

1. Введение в теорию вычислений.
2. Регулярные языки, детерминированные и недетерминированные конечные автоматы (ДКА и НКА), замкнутость регулярных языков относительно операций объединения и конкатенкции.
3. Замкнутость регулярных языков относительно операции *. Регулярные выражения. Обобщенные конечные автоматы (ОНКА). Эквиалентность ДКА и регулярных выражений. (ogg/theora, 654 МБ torrent/ftp.)
4. Лемма о накачке для регулярных языков. Примеры доказательств нерегулярности языков. Контекстно-свободные (КС) грамматики и языки. (ogg/theora, 549 МБ torrent/ftp.)
5. Неоднозначность в КС-грамматиках. Левый и правый вывод. Деревья вывода. Автоматы с магазинной памятью (МП-автоматы). (ogg/theora, 512 МБ torrent/ftp.)
6. Эквивалентность КС-грамматик и (недетерминированных) МП-автоматов. Лемма о накачке для КС-языков. (mkv/theora, 505 МБ torrent/ftp.)
7. Доказательство леммы о накачке для КС-языков. Нормальная форма Хомского. (mkv/theora, 574 МБ torrent/ftp.)
8. Машины Тьюринга (МТ). Рекурсивно-перечислимые (РП) языки. МТ, принимающие решение, (решатели). Разрешимость по Тьюрингу, рекурсивные языки. Варианты МТ: многоленточные. (mkv/theora, 557 МБ torrent/ftp.)
9. Варианты МТ: недетерминированные, перечислители. Эквивалентность одноленточным детерминированным МТ. Разрешимость проблем A_DFA, A_NFA и A_REX. (mkv/theora, 406 МБ torrent/ftp.)
10. Разрешимость проблем E_DFA, EQ_DFA, A_CFG и E_CFG. Разрешимость проблемы распознавания КС-языков. Теорема Кантора, метод диагонализации. Теорема о существовании нераспознаваемых по Тьюрингу языков. Неразрешимость проблемы A_TM. (mkv/theora, 546 МБ torrent/ftp.)
11. Нераспознаваемая по Тьюрингу проблема. Понятие общей сводимости. Неразрешимость проблем HALT_TM (проблемы останова), E_TM и REGULAR_TM. Теорема Райса. Понятие линейно-ограниченного автомата. (mkv/theora, 480 МБ torrent/ftp.)
12. Разрешимость проблемы A_LBA. Доказательство методом сведения через историю вычислений: неразрешимость E_LBA и ALL_CFG. Проблема соответствий Поста. (mkv/theora, 546 МБ torrent/ftp.)
13. Доказательство неразрешимости проблемы соответствий Поста. Вычислимые функции. Сводимость посредством редукции. Редукция A_TM к HALT_TM. Общий метод доказательства нераспозноваемости языков. Нераспозноваемость EQ_TM и EQ_TM. (mkv/theora, 677 МБ torrent/ftp.)
14. Редукция A_TM к E_TM. Построение машины, пишушей заданную строку на ленту (P_w). Машина, пишущая свое описание на ленту (SELF). Теорема о рекурсии. (mkv/theora, 449 МБ torrent/ftp.)
15. Несуществование редукции A_TM к E_TM. Рекурсивные перечислители. Приложения теоремы о рекурсии: неразрешимость A_TM, нераспознаваемость MIN_TM, теорема о неподвижной точке. (mkv/theora, 558 МБ torrent/ftp.)
16. Предсказатели. Относительная резрешимость. Сводимость по Тьюрингу. Колмогоровская сложность. Определение информации. Оценки колмогоровской сложности. Оптимальность определения информации. (mkv/theora, 558 МБ torrent/ftp.)
17. Несжимаемые и случайные строки. Логические теории. Пример разрешимой логической теории Th(N, +). (mkv/theora, 552 МБ torrent/ftp.)
18. Доказательство разрешимости теории Th(N, +). Теорема Чёрча о неразрешимости теории Th(N, +, ×). Распозноваемость Th(N, +, ×). Конспект доказательства теоремы Гёделя о неполноте. (mkv/theora, 476 МБ torrent/ftp.)

Список пройденных тем по основным концепциям языков программирования и теории компиляции.

1. Введение в Лисп, процедуры как механизм абстракции вычислений.
2. Области видимости. Статическое и динамическое связывание. Процедуры как механизм абстракции данных. Списки в Лиспе. (mkv/theora, 590 МБ torrent/ftp.)
3. Макросы в Лиспе. Отложенные вычисления. Представление бесконечных последовательностей в виде ленивых списков. Работа с последовательностями: итерация, фильтрация, индексация, накопление. (mkv/theora, 529 МБ torrent/ftp.)
4. LL(1)-грамматики. Построение детерминированного МП-автомата по LL(1)-грамматике. Представление истории вычислений в виде отложенного списка в Лиспе. (mkv/theora, 553 МБ torrent/ftp.)
5. Обзор архитектуры ЭВМ. Понятие машинного языка. Общее устройство компиляторов. (mkv/theora, 444 МБ torrent/ftp.)
6. Трехадресный код, архитектуры RISC и CISC. Представление областей видимости в виде списка фреймов. Компиляция основных форм Лиспа. (mkv/theora, 539 МБ torrent/ftp.)