Skip to content

Latest commit

 

History

History
56 lines (51 loc) · 5.41 KB

exam.md

File metadata and controls

56 lines (51 loc) · 5.41 KB
Raw

Темы (окончательные) к экзамену по ФП 2023-2024

Вопросы-автоматы на оценку F обозначены ‡.

  1. Функции в программировании и функции в математике. Сходства и отличия. ‡ Понятие чистой функции
  2. ‡ Алгебраические типы данных. Что такое и в чем их алгебраичность?
    • Boolean blindness
  3. ‡ Хвостовая рекурсия. Уметь объяснять, чем хвостовая лучше обычной обычной рекурсии примерах. CPS
    • Переход к хвостовой рекурсии. (Переписать функцию, что дал экзаменатор)
  4. Continuation passing style. Преобразование функций из стандартного (direct) стиля в CPS
    • ‡ Быть готовыми переписать функцию в CPS (функция выбирается экзаменатором)
  5. Лямбда-исчисление
    • ‡ Привести (подготовить заранее) трассу вычисления факториала (или фибоначчи) для каждой из стратегий (CBN, CBV, NO, AO) для "голого" лямбда исчисления. (Функцию и стратегию выбирает экзаменатор.) Демонстрировать понимание того, как проходят редукции в указанной стратегии
    • Понятие исчисления. Аксиомы, правила вывода, посылки и заключения. Доказательства
    • ‡ Определение языка лямбда-выражений. Три правила (α, β, η) преобразования лямбда-выражений.
    • Лямбда исчисление как универсальный язык программирования. Числа Чёрча, арифметика, ветвления
    • Редексы. Стратегии вычисления лямбда-термов: CBN, CBV, CBNeeded, NO, AO. Достоинства и недостатки
    • Написание рекурсивных функций без использования рекурсии. Комбинаторы неподвижной точки для разных стратегий. Примеры
    • Проблема останова
    • Capture avoiding substitution. Индексы и уровни де Брёйна
    • SKI
  6. ‡ Определение монады. Стандартные монады: Maybe/Option, Result, List, Identity, Parser, Concurrency.
    • Как в использовании отличаются монады и исключения?
  7. Аппликативные функторы. Чем отличаются от монад, и когда их стоит предпочитать монадам?
  8. Парсер-комбинаторы.
    • ‡ Пример: синтаксический анализатор языка a^n b^n c^n (где а,b,c -- символы алфавита, ^n -- n вхождений подряд). Плохой вход должен детектироваться максимально рано.
  9. Унификация и подстановки. Occurs check.
    • Уметь демонстрировать преимущества и недостатки включения/выключения occurs check.
    • ‡ Уметь проунифицировать на примере экзаменатора.
  10. ‡ STLC. Понятие схемы типов.
  11. Вывод типов в системе Хиндли-Милнера. Правила, которые отличают от STLC.
  12. ‡ Понятие мемоизации
    • Пример: эффективное вычисление чисел Фибоначчи
  13. Ленивые списки (потоки)
    • Стандартные задачи: фибоначчи
  14. PFDS. ‡ Понятие неизменяемых и устойчивых (persistent) типов данных.
  15. PFDS. Чисто функциональные очереди. Три реализации и их асимптотики.
  16. PFDS. Понятие префиксных деревьев и HAMT.
  17. Схемы рекурсии. На примере списков и деревьев. Ката- и анаморфизмы.
  18. Схемы рекурсии. Хиломорфизм. Решения задач: фибоначчи, binary partition, LCS, merge sort.
    • ‡ Идея реализации динамического программирования через схемы рекурсии