Инспектор
Спонсор: Microsoft
Вы можете этот курс.
Функциональное программирование
: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Курс знакомит слушателей с парадигмой функционального программирования, в которой решение задач сводится к описанию функций, перерабатывающих некоторые входные данные в выходные и строящихся из более простых функций на основе принципов функциональной абстракции и аппликации. Рассматриваются теоретические основы функционального программирования (лямбда-исчисление, комбинаторная логика, вопросы вычислимости), на примере функционального подхода дается представление о некоторых теоретических разделах компьютерных наук (семантика языков программирования, доказательство программ). С другой стороны курс содержит значительную практическую составляющую, основанную на промышленном языке программирования F# (входит в состав Microsoft Visual Studio 2010), рассматриваются вопросы использования функциональных языков для построения компиляторов, грамматического разбора и т.д.
Курс будет интересен как практикующим программистам и студентам, изучившим основы компьютерных наук, так и математикам. Для программистов на императивных языках знакомство с функциональным подходом позволит расширить сознание, перейти на более чистый (свободный от побочных эффектов) стиль программирования с более высоким уровнем абстракции, научиться эффективно использовать новые возможности современных императивных языков (LINQ, лямбда-выражения и т.д.). Для математиков, функциональное программирование может служить безболезненным введением в компьютерные науки, поскольку в рамках курса мы практически «с нуля» строим (начиная от математических основ, вплоть до реализации интерпретатора/компилятора и описания формальной семантики) язык программирования на базе лямбда-исчисления – раздела дискретной математики.
Цель: Познакомить слушателя с основами функционального программирования как дисциплины, находящейся на стыке программирования и дискретной математики; дать, с одной стороны, практические навыки функционального программирования на используемом на практике языке F#, а с другой – показать связь между теоретическими главами computer science и программированием, осветив некоторые теоретические проблемы информатики (вычислимость, семантика языков программирования, доказательство программ) и показав, как они решаются в функциональном подходе.
Необходимые знания: Строго говоря, предварительных знаний для курса не требуется – возможно изучение программирования, начиная с функционального подхода. Однако более традиционным подходом является изучение основ программирования на базе императивного языка, и затем изучение функционального программирования как альтернативной парадигмы. Курс в большей степени ориентирован именно на такой подход.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 1 | Определение и краткая история функционального программирования
Знакомство. Определение функционального программирования и его история.
| - |
Лекция 2 | Абстракция и декомпозиция. Декларативное программирование
Абстракция и декомпозиция при функциональном подходе. Декларативное программирование. Плюсы и минусы.
| - |
Лекция 3 | Парадигмы программирования
Зачем надо изучать функциональное программирование.
| - |
Лекция 4 | Функциональное программирование в реальной жизни
Построение множества Мандельброта. Функциональное программирование в реальной жизни. Пример визуализации на F#. Рекомендуемая литература. Информация о курсе.
| - |
Тест 112 минут | - | |
Лекция 5 | Основные принципы функционального программирования
Введение в лямбда-исчисление. Редукция. Язык функционального программирования как лямбда-редуктор. Функции нескольких аргументов. Каррирование. Условное выражение. Определение имен. Области видимости.
Оглавление | - |
Лекция 6 | Сопоставление с образцом. Рекурсия. Циклы
Циклические конструкции. Виды рекурсии.
| - |
Лекция 7 | Пример: построение графика 2D-функции
Пример: построение графика 2D-функции и построение графика трехмерной функции
| - |
Тест 212 минут | - | |
Лекция 8 | Рекурсивные структуры данных. Списки
Рекурсивные структуры данных. Основные операции работы со списками.
| - |
Лекция 9 | Примеры работы со списками
Примеры работы со списками. Перестановки. Вычисление простых чисел. Работа с изображениями. Синтаксис порождения списка list comprehension.
| - |
Лекция 10 | Хвостовая рекурсия. Порядковое представление списков и матриц
Хвостовая рекурсия. Порядковое представление списков и матриц.
| - |
Лекция 11 | Функциональные структуры данных
Функциональные структуры данных. Представление очереди. Многомерные массивы.
| - |
Тест 321 минута | - | |
Лекция 12 | Деревья
Деревья общего вида и двоичные деревья. Обход дерева. Реализация обхода с помощью функции с отложенным вычислением.
| - |
Лекция 13 | Деревья выражений и деревья поиска. Продолжения
Деревья поиска. Деревья выражений. Хвостовая рекурсия для деревьев. Продолжения (continuations).
Оглавление | - |
Тест 412 минут | - | |
Лекция 14 | Введение в л-исчисление
Основные модели вычислений. Синтаксис л-исчисления. Чистое и прикладное л-исчисление. Преобразования л-выражений. Редукция. Бетта-редукция и замена переменной.
| - |
Лекция 15 | Нормальный и аппликативный порядок редукции. Теорема Чёрча-Россера
Нормальный и аппликативный порядок редукции. Ленивые и энергичные вычисления. Механизмы вызова и проблема разделения. Теорема Чёрча-Россера и теорема стандартизации. Экстенсиональность. Слабая заголовочная нормальная форма.
| - |
Лекция 16 | Описание рекурсивных функций. Комбинаторы и комбинаторная логика
Описание рекурсивных функций. Оператор неподвижной точки. Комбинаторы и комбинаторная логика.
| - |
Тест 524 минуты | - | |
Лекция 17 | От л-исчисления к языку программирования
Представление условных выражений, списков и натуральных чисел в лямбда исчислении.Вычислимость.Эквивалентность алгоритмических моделей.
| - |
Лекция 18 | Замыкания, генераторы и отложенные вычисления
Переопределение имен. Замыкания. Генераторы - как способ работы с бесконечными последовательностями, отложенные вычисления.
| - |
Лекция 19 | Последовательности и ленивые вычисления в F#. Мемоизация
F# sequences. Примеры. Ленивые вычисления. Мемоизация.
| - |
Лекция 20 | Пример: реализация машины Тьюринга
Определение. Пример. Реализация на F#. Зиппер.
| - |
Тест 612 минут | - | |
Лекция 21 | Типизация в языках функционального программирования
Классификация языков программирования по видам типизации. Типизированное лямбда исчисление. Вывод типов.
| - |
Лекция 22 | Формальная семантика языков функционального программирования
Классификация формальных семантик.Теория доменов. Теорема о неподвижной точке. Семантика для простейшего языка.
| - |
Лекция 23 | Доказательство свойств программ
Доказательство корректности программ на примерах. Проблема самопременимости.
| - |
Тест 718 минут | - | |
Лекция 24 | Реализация функциональных языков. Eval-Apply-интерпретаторы
Реализация функциональных языков. Eval-Apply-интерпретаторы.
| - |
Лекция 25 | Реализация функциональных языков: интерпретаторы и абстрактные машины
Обработка рекурсии и ленивые вычисления в Eval-Apply модели. SECD-машина.
| - |
Лекция 26 | Реализация функциональных языков: редукция графов, потоковые реализации
Редукция графов. Эффект разделения. Пара слов о потоковых графах.
| - |
Лекция 27 | Анализ искусственных и естественных языков
Языки и грамматики. Лексический анализ. Синтаксический разбор. Специализированные утилиты.
| - |
Тест 89 минут | - | |
Лекция 28 | Метапрограммирование: Quotations
Метапрограммирование. Quotations. Примеры. DLinq технология.
| - |
Лекция 29 | Императивное ядро в функциональных языках. Монады. Computational Workflows
Императивное ядро в функциональных языках. Монады. Примеры.
Оглавление | - |
Лекция 30 | Асинхронные и параллельные вычисления
Подходы к параллельным вычислениям. Asychrnous Workflows. Примеры.
| - |
Тест 912 минут | - | |
5 часов | - |