Компьютерные науки

Функциональное программирование

В программе рассматривается парадигма функционального программирования на базе F# с изучением лямбда-исчисления и формальной семантики.
Студентов 2015 Выпускников 158 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Программирование
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Эта учебная программа посвящена основам функционального программирования. В учебной программе изучаются декларативные подходы, рекурсия, функциональные структуры данных, мемоизация и ленивые вычисления, а также интерпретаторы, монады и метапрограммирование. Практическая часть охватывает написание компиляторов и асинхронные вычисления, при этом освоение темы построено на переходе от математических основ к промышленным возможностям языка F#. Учебная программа будет полезна разработчикам на императивных языках, которым необходимо освоить чистый стиль написания кода без побочных эффектов, а также математикам для плавного введения в компьютерные науки.
Цели
  • Познакомить с теоретическими основами функциональной парадигмы.
  • Сформировать навыки декларативного программирования и работы с рекурсией.
  • Дать опыт использования F# для реализации сложных алгоритмов.
Чему я научусь?
  • Применять замыкания, отложенные вычисления и сопоставление с образцом.
  • Работать с функциональными структурами данных: списками и деревьями.
  • Реализовывать парсеры, интерпретаторы и асинхронные операции.

Авторы

Сошников Дмитрий Валерьевич
Сошников Дмитрий Валерьевич
Кандидат физико-математических наук, доцент технологический евангелист Microsoft в России.
Чему я научусь?
  • Применять замыкания, отложенные вычисления и сопоставление с образцом.
  • Работать с функциональными структурами данных: списками и деревьями.
  • Реализовывать парсеры, интерпретаторы и асинхронные операции.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Определение и краткая история функционального программирования Знакомство. Определение функционального программирования и его история.
2 Абстракция и декомпозиция. Декларативное программирование Абстракция и декомпозиция при функциональном подходе. Декларативное программирование. Плюсы и минусы.
3 Парадигмы программирования Зачем надо изучать функциональное программирование.
4 Функциональное программирование в реальной жизни Построение множества Мандельброта. Функциональное программирование в реальной жизни. Пример визуализации на F#. Рекомендуемая литература. Информация о... Построение множества Мандельброта. Функциональное программирование в реальной жизни. Пример визуализации на F#. Рекомендуемая литература. Информация о курсе. ещё
Функциональное программирование в реальной жизни тест для курса Функциональное программирование 20 мин
5 Основные принципы функционального программирования Введение в лямбда-исчисление. Редукция. Язык функционального программирования как лямбда-редуктор. Функции нескольких аргументов. Каррирование. Условное выражение. Определение... Введение в лямбда-исчисление. Редукция. Язык функционального программирования как лямбда-редуктор. Функции нескольких аргументов. Каррирование. Условное выражение. Определение имен. Области видимости. ещё
6 Сопоставление с образцом. Рекурсия. Циклы Циклические конструкции. Виды рекурсии.
7 Пример: построение графика 2D-функции Пример: построение графика 2D-функции и построение графика трехмерной функции
Пример: построение графика 2D-функции тест для курса Функциональное программирование 20 мин
8 Рекурсивные структуры данных. Списки Рекурсивные структуры данных. Основные операции работы со списками.
9 Примеры работы со списками Примеры работы со списками. Перестановки. Вычисление простых чисел. Работа с изображениями. Синтаксис порождения списка list comprehension.
Примеры работы со списками тест для курса Функциональное программирование 35 мин
10 Хвостовая рекурсия. Порядковое представление списков и матриц Хвостовая рекурсия. Порядковое представление списков и матриц.
11 Функциональные структуры данных Функциональные структуры данных. Представление очереди. Многомерные массивы.
Функциональные структуры данных тест для курса Функциональное программирование 35 мин
12 Деревья Деревья общего вида и двоичные деревья. Обход дерева. Реализация обхода с помощью функции с отложенным вычислением.
13 Деревья выражений и деревья поиска. Продолжения Деревья поиска. Деревья выражений. Хвостовая рекурсия для деревьев. Продолжения (continuations).
Деревья выражений и деревья поиска. Продолжения тест для курса Функциональное программирование 20 мин
14 Введение в л-исчисление Основные модели вычислений. Синтаксис л-исчисления. Чистое и прикладное л-исчисление. Преобразования л-выражений. Редукция. Бетта-редукция и замена переменной.
15 Нормальный и аппликативный порядок редукции. Теорема Чёрча-Россера Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера... Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера и теорема стандартизации. Экстенсиональность. Слабая заголовочная нормальная форма. ещё
16 Описание рекурсивных функций. Комбинаторы и комбинаторная логика Описание рекурсивных функций. Оператор неподвижной точки. Комбинаторы и комбинаторная логика.
Описание рекурсивных функций. Комбинаторы и комбинаторная логика тест для курса Функциональное программирование 40 мин
17 От л-исчисления к языку программирования Представление условных выражений, списков и натуральных чисел в лямбда исчислении.Вычислимость.Эквивалентность алгоритмических моделей.
18 Замыкания, генераторы и отложенные вычисления Переопределение имен. Замыкания. Генераторы - как способ работы с бесконечными последовательностями, отложенные вычисления.
19 Последовательности и ленивые вычисления в F#. Мемоизация F# sequences. Примеры. Ленивые вычисления. Мемоизация.
20 Пример: реализация машины Тьюринга Определение. Пример. Реализация на F#. Зиппер.
Пример: реализация машины Тьюринга тест для курса Функциональное программирование 20 мин
21 Типизация в языках функционального программирования Классификация языков программирования по видам типизации. Типизированное лямбда исчисление. Вывод типов.
22 Формальная семантика языков функционального программирования Классификация формальных семантик.Теория доменов. Теорема о неподвижной точке. Семантика для простейшего языка.
23 Доказательство свойств программ Доказательство корректности программ на примерах. Проблема самопременимости.
Доказательство свойств программ тест для курса Функциональное программирование 30 мин
24 Реализация функциональных языков. Eval-Apply-интерпретаторы Реализация функциональных языков. Eval-Apply-интерпретаторы.
25 Реализация функциональных языков: интерпретаторы и абстрактные машины Обработка рекурсии и ленивые вычисления в Eval-Apply модели. SECD-машина.
26 Реализация функциональных языков: редукция графов, потоковые реализации Редукция графов. Эффект разделения. Пара слов о потоковых графах.
27 Анализ искусственных и естественных языков Языки и грамматики. Лексический анализ. Синтаксический разбор. Специализированные утилиты.
Анализ искусственных и естественных языков тест для курса Функциональное программирование 15 мин
28 Метапрограммирование: Quotations Метапрограммирование. Quotations. Примеры. DLinq технология.
29 Императивное ядро в функциональных языках. Монады. Computational Workflows Императивное ядро в функциональных языках. Монады. Примеры.
30 Асинхронные и параллельные вычисления Подходы к параллельным вычислениям. Asychrnous Workflows. Примеры.
Асинхронные и параллельные вычисления тест для курса Функциональное программирование 20 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^