Условия получения автомата по ТМВ
Для получения экзаменационной оценки автоматом по предмету ТМВ требуется, помимо сдачи контрольных, практических и прочих работ, сделать следующее на выбор:
- Пройти 3 курса (Algorithmic Toolbox, Data Structures и Algorithms on strings) специализации: https://www.coursera.org/specializations/data-structures-algorithms и защитить каждый из них по отдельности лично мне. Курсы доступны бесплатно, при условии запроса финансовой помощи. Инструкция есть здесь: https://wiki.appmat.ru/index.php/Coursera Можно подавать на все курсы сразу, при этом не надо начинать бесплатный пробный период, иначе будет в материальной помощи будет отказано.
- Сделать 200 задач на литкоде https://leetcode.com (при этом задачи выполненные для получения автомата по теории графов не засчитываются) и закоммитить их в гитхаб. Задачи будут проверены на списывание. При обнаружении списывания возможность автомата отпадает.
- Сделать конспект лекций на wiki.appmat.ru (1 человек)
- Сделать конспект семинаров на wiki.appmat.ru (1 человек)
- Подготовить публикацию по теме курса в формате сайта habr.com (соответствующего качества). В дополнение к автомату будет выдан инвайт на хабр за эту статью. Список тем представлен ниже.
Список тем для написания статьи на Хабр
- Регулярные языки. Регулярные выражения, конечные автомати, графы переходов. Эквивалентность графов переходов и конечных автоматов.
- Контекстно-свободные грамматики. Нормальная форма для КС-грамматик. Примеры языков, задаваемых КС-грамматиками. Лемма о разрастании КС-грамматик. Неконтекстность языка a^n b^n c^n.
- Контекстно-свободные грамматики. Нормальная форма для КС-грамматик. Примеры языков, задаваемых КС-грамматиками. Алгоритм Кока-Янгера-Касами.
- Вычислимость, разрешимость, перечислимость. Теорема Поста. Универсальные функции. Существование перечислимого неразрешимого множества.
- Машина Тьюринга. Примеры: задача удвоения слова; сложение в унарной системе счисления.
- Лямбда-функции. Множество свободных переменных, операция подстановки. Бета-редукция.
- Лямбда-функции. Сложение, умножение. Каррирование в python.
- Частично-рекурсивные функции. Примеры: сложение, умножение, возведение в степень.
- Частично-рекурсивные функции. Функция Аккермана. Теорема о непримитивной рекурсивности функции Аккермана.
- Амортизационный анализ. Учетные стоимости операций для бинарного счетчика и динамического массива.
- Эквивалентность ассоциативных исчислений и машин Тьюринга.
- Квантовая машина Тьюринга. Квантовая схема. Квантовый алгоритм. Алгоритм Дойча — Йожи. Алгоритм Гровера. Алгоритм Шора. Языки Q# и Haskell для программирования квантовых алгоритмов.