Письменный экзамен

Пятница, 18 мая 2012
ФМЛ 239, Актовый зал

Описание

ВОПРОСЫ К ЭКЗАМЕНУ

  1. Понятие о функциональном стиле программирования. Отличительные особенности этого стиля.
  2. Язык Haskell: типы, функции и задание определяющих уравнений для функций. Образцы и сопоставление с ними.
  3. Рекурсия и накапливающие параметры. Эффективность рекурсивных функций. Концевая рекурсия. Примеры.
  4. Язык Haskell: списки и операции над ними. Способы задания списков.
  5. Задание синонимов для типов данных. Определение новых типов данных, конструкторы. Параметризация типов данных.
  6. Сложные типы данных. Определение деревьев и функций их обработки. Сортировка с помощью двоичного дерева.
  7. Функции высших порядков. Отображение (map) и свертка (foldr) списков. Определение функций с помощью лямбда-выражений в Haskell.
  8. Свертка деревьев. Примеры программирования с помощью свертки сложных структур данных - деревьев и списков.
  9. Частичное применение функций. Карринг и сечение. Каррирование и декаррирование функций.
  10. Функциональное представление конечных и бесконечных множеств. Фильтрация списков.
  11. Понятие об энергичном и ленивом вычислениях. Конъюнкция и дизъюнкция по МакКарти. Бесконечные структуры данных.
  12. Встроенные в язык операции над бесконечными списками. Программа вычисления списка простых чисел способом решета Эратосфена.
  13. Графическое представление бесконечных списков как потоков. Программирование с помощью завязывания узлов. Построение списка из чисел Фибоначчи.
  14. Определение анализатора для регулярных языков с помощью функций высших порядков.
  15. Определение классов и их реализации. Расширение классов. Стандартные классы Eq, Ord и Show.
  16. Основные черты и особенности языка ЛИСП.
  17. Комбинаторное программирование. Система программирования FP Дж.Бэкуса. Примеры программ.
  18. Лямбда-исчисление: базовые понятия и правила редукций. Нормальная форма и ее единственность.
  19. Различные порядки редукций в лямбда-исчислении. Проблема конфликта имен переменных. Слабая заголовочная нормальная форма.
  20. Прямая и косвенная рекурсия в лямбда-исчислении. Комбинатор неподвижной точки. Y-комбинатор Карри.
  21. Представление констант и основных функций в чистом лямбда-исчислении: логические функции и значения, списки.
  22. Чистое лямбда-исчисление: способы представления арифметических значений и функций.
  23. Интерпретаторы и компиляторы. Перевод конструкций языков функционального программирования в расширенное лямбда-исчисление.
  24. Представление программ расширенного лямбда-исчисления в виде объектов языка Haskell. Схема интерпретации в Eval / Apply интерпретаторе.
  25. Реализация Eval / Apply интерпретатора программ. Вопрос об энергичной и ленивой схемах интерпретации.
  26. Архитектура и представление SECD-машины. Интерпретация работы энергичной SECD-машины.
  27. Функциональные эквиваленты императивных программ: представление императивной программы в виде функции состояния.
  28. Представление выражений в виде графов. Редукция графов. Решение проблемы разделения переменных. Фиктивные ссылочные узлы.
  29. Комбинаторная редукция. Основные комбинаторы и функция абстрагирования от переменных.
  30. Комбинаторная редукция: оптимизации Карри.
  31. Комбинаторная редукция: сохранение аппликативных подвыражений.
  32. Комбинаторная редукция графов.