Условия получения автомата по ТМВ

Для получения экзаменационной оценки автоматом по предмету ТМВ требуется, помимо сдачи контрольных, практических и прочих работ, сделать следующее на выбор:

  1. Пройти 3 курса (Algorithmic Toolbox, Data Structures и Algorithms on strings) специализации: https://www.coursera.org/specializations/data-structures-algorithms и защитить каждый из них по отдельности лично мне. Курсы доступны бесплатно, при условии запроса финансовой помощи. Инструкция есть здесь: https://wiki.appmat.ru/index.php/Coursera Можно подавать на все курсы сразу, при этом не надо начинать бесплатный пробный период, иначе будет в материальной помощи будет отказано.
  2. Сделать 200 задач на литкоде https://leetcode.com (при этом задачи выполненные для получения автомата по теории графов не засчитываются) и закоммитить их в гитхаб. Задачи будут проверены на списывание. При обнаружении списывания возможность автомата отпадает.
  3. Сделать конспект лекций на wiki.appmat.ru (1 человек)
  4. Сделать конспект семинаров на wiki.appmat.ru (1 человек)
  5. Подготовить публикацию по теме курса в формате сайта habr.com (соответствующего качества). В дополнение к автомату будет выдан инвайт на хабр за эту статью. Список тем представлен ниже.

Список тем для написания статьи на Хабр

  1. Регулярные языки. Регулярные выражения, конечные автомати, графы переходов. Эквивалентность графов переходов и конечных автоматов.
  2. Контекстно-свободные грамматики. Нормальная форма для КС-грамматик. Примеры языков, задаваемых КС-грамматиками. Лемма о разрастании КС-грамматик. Неконтекстность языка a^n b^n c^n.
  3. Контекстно-свободные грамматики. Нормальная форма для КС-грамматик. Примеры языков, задаваемых КС-грамматиками. Алгоритм Кока-Янгера-Касами.
  4. Вычислимость, разрешимость, перечислимость. Теорема Поста. Универсальные функции. Существование перечислимого неразрешимого множества.
  5. Машина Тьюринга. Примеры: задача удвоения слова; сложение в унарной системе счисления.
  6. Лямбда-функции. Множество свободных переменных, операция подстановки. Бета-редукция.
  7. Лямбда-функции. Сложение, умножение. Каррирование в python.
  8. Частично-рекурсивные функции. Примеры: сложение, умножение, возведение в степень.
  9. Частично-рекурсивные функции. Функция Аккермана. Теорема о непримитивной рекурсивности функции Аккермана.
  10. Амортизационный анализ. Учетные стоимости операций для бинарного счетчика и динамического массива.
  11. Эквивалентность ассоциативных исчислений и машин Тьюринга.
  12. Квантовая машина Тьюринга. Квантовая схема. Квантовый алгоритм. Алгоритм Дойча — Йожи. Алгоритм Гровера. Алгоритм Шора. Языки Q# и Haskell для программирования квантовых алгоритмов.