Рабочая программа дисциплины Б.1.2.13.1 "Функциональное программирование"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

УТВЕРЖДАЮ Декан ФВТ _______________ «_____» ___________________ 2015 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Б.1.2.13.1 ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Направление подготовки: 020303 "Математическое обеспечение и администрирование информационных систем"

Профиль: «Администрирование информационных систем»

Квалификация (степень) выпускника бакалавр

Форма обучения очная

Пенза, 2015

1. Цели освоения дисциплины

Целью освоения дисциплины является формирование у студентов общих теоретических основ функционального стиля программирования и практических навыков разработки программного обеспечения с использованием функционального языка Haskell.

2. Место дисциплины в структуре ООП

2.1. Дисциплина входит в вариативную часть (дисциплины по выбору студента) профессионального цикла образовательной программы.

2.2. Минимальные требования к «входным» знаниям, необходимым для успешного усвоении данной дисциплины ‑ удовлетворительное усвоение программ по следующим дисциплинам бакалавриата:

- «Программирование»;

- «Информатика»;

- «Информационные технологии в профессиональной деятельности»;

- «Математическая логика»;

- «Структуры и алгоритмы компьютерной обработки данных»;

- «Объектно-ориентированное программирование».

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

Коды компетенции	Наименование компетенции	Структурные элементы компетенции (в результате освоения дисциплины обучающийся должен знать, уметь, владеть)
1	2	3
ОПК-2	Способность применять в профессиональной деятельности знания математических основ информатики	- иметь представление о лямбда-исчислении как теоретической основе функциональных языков; - знать основные положения и теоремы лямбда-исчисления; - знать основные положения комбинаторной логики; - иметь представление о функциональном программировании как об альтернативном и одном из перспективных направлений развития информатики; - уметь применять на практике стандартные стратегии редукции лямбда-выражений; - иметь опыт редукции сложных лямбда-выражений; - иметь представление о методах представления основных программных конструкций в терминах лямбда-выражений;
ОПК-7	Способность использовать знания основных концептуальных положений функционального, логического, объектно-ориентированного и визуального направлений программирования, методов, способов и средств разработки программ в рамках этих направлений	- знать основные особенности функционального подхода к разработке программного обеспечения; - знать основные особенности программирования при помощи функций и при помощи процедур; - уметь решать задачи администрирования информационных систем с применением пакетов для создания функциональных программ; - иметь опыт разработки функциональных программ на языке Haskell; - уметь разрабатывать абстрактные типы данных средствами функционального языка Haskell; - иметь опыт проведения сравнительного анализа императивных и функциональных программ; - иметь представление о концепции отложенных вычислений; - иметь представление о реализации принципов наследования, полиморфизма и инкапсуляции в функциональном языке Haskell; - иметь опыт реализации императивных принципов в функциональных языках с использованием механизма монад.
ПК-4	Способность к выбору архитектуры и комплексирования современных компьютеров, систем, комплексов и сетей системного администрирования	- знать роль и место функциональных языков программирования в индустрии проектирования программных систем; - знать историю развития функциональных языков программирования; - знать основные свойства и особенности строго функционального языка; - уметь использовать функциональные методы при проектировании прикладного программного обеспечения вычислительной техники; - иметь опыт использования инструментальных средств для создания ПО на базе функциональных методов программирования; - знать особенности представления и интерпретации функциональных программ.
ПК-6	Способность формировать суждения о проблемах современной информатики, ее категорий и связей с другими научными дисциплинами	- знать сущность и методы функционального подхода к параллелизму; - знать методы применения функций высших порядков в программировании; - знать основные виды редукций лямбда-исчисления; - иметь опыт проведения сравнительного анализа императивных и функциональных программ; - иметь опыт разработки и отладки функционального ПО в среде WinHUGS; - иметь представление об эффективной и ленивой моделях вычислений; - знать объектно-ориентированные принципы разработки ПО; - знать объектно-ориентированные свойства функционального языка Haskell;

4. Структура и содержание дисциплины (модуля) «Функциональное программирование»

4.1. Структура дисциплины (модуля)

Общая трудоемкость дисциплины составляет 5 зачетных единицы, 180 часа.

№ п/п	Наименование разделов и тем дисциплины (модуля)	Семестр	Недели семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)	Формы текущего контроля успеваемости (по неделям семестра)
Аудиторная работа	Самостоятельная работа
Всего	Лекция	Практические занятия	Лабораторные занятия	Всего	Подготовка к аудиторным занятиям	Реферат, эссе и др.	Курсовая работа (проект)	Подготовка к экзамену	Собеседование	Коллоквиум	Проверка тестов	Проверка контрольн. работ	Проверка реферата	Проверка эссе и иных творческих работ	курсовая работа (проект)
1.	Раздел 1. Введение. Чисто функциональное программирование.	5	1-4	16	8		8	8	4			4
1.1.	Тема 1.1 Поколения языков программирования. Функционально-логические языки программирования.	5	1-2	4	2		2	4	2			2
1.2	Тема 1.2 Методы функционального программирования.	5	3-4	12	6		6	4	2			2
2.	Раздел 2. Математические основы функционального программирования.	5	5-11	22	14		8	24	11			13
2.1.	Тема 2.1. Лямбда-исчисление.	5	5-9	16	10		6	15	7			8
2.2	Тема 2.2 Комбинаторная логика.	5	10-11	6	4		2	9	4			5
3	Раздел 3. Функциональный язык Haskell	5	12-18	52	14		38	54	26			28
3.1	Тема 3.1 Синтаксис языка и типы данных. Объектно-ориентированные свойства языка Haskell.	5	12-16	36	10		26	30	14			16
3.2	Тема 3.2 Императивные возможности в функциональных языках.	5	17-18	16	4		12	24	12			12
	Курсовая работа (проект)
	Подготовка зачету							4	4
	Общая трудоемкость, в часах			90	36		54	90	45			45	Промежуточная аттестация
Форма	Семестр
Зачет	5
Экзамен	5

4.2. Содержание дисциплины (модуля)

4.2.1 Содержание лекционного курса

Раздел 1. Введение. Чисто функциональное программирование.

Тема 1.1 Поколения языков программирования. Функционально-логические языки программирования.

Введение в курс «Функциональное программирование», цели и задачи. Поколения и классификация языков программирования. Сравнительные характеристики императивного и функционального стилей. Классификация функционально-логических языков. Программирование при помощи функций. Программирование при помощи процедур. Понятие побочного эффекта.

Тема 1.2 Методы функционального программирования.

Символьные данные и S-выражения. Базовые функции работы с S-выражениями. Реализация предикатов в функциональном программировании. Организация повторяющихся вычислений. Примеры применения рекурсивных функций на различных задачах обработки списков. Функциональные иерархии и проблемы их построения. Организация модульности функциональной программы. Накапливающие параметры с примерами применения. Локальные определения и рекурсивные локальные определения. Функции высших порядков. Объекты первого класса. Примеры реализации модульных программ с использованием объектов первого класса.

Раздел 2. Математические основы функционального программирования.

Тема 2.1 Лямбда-исчисление.

Возникновение и назначение лямбда-исчисления. Понятия аппликации и абстракции. Замкнутые выражения. Правила преобразования лямбда-выражений. Ромбическое свойство системы редукций. Теорема Чёрча-Россера и ее следствие. Аппликативный и нормальный порядки редукции, их сравнительный анализ и примеры применения. Теорема Карри. Проблема конфликта имен и слабая заголовочная нормальная форма.

Тема 2.2 Комбинаторная логика.

Возникновение и назначение комбинаторной логики. Бестиповая комбинаторная логика. Комбинаторы Шейнфинкеля. Набор комбинаторов Карри. Одноместная функция (комбинатор) и аппликация. Базисные комбинаторные характеристики. Представление основных объектов при помощи комбинаторной нотации.

Раздел 3. Функциональный язык Haskell

Тема 3.1 Синтаксис языка и типы данных. Объектно-ориентированные свойства языка Haskell.

Базовый синтаксис языка Haskell 98. Базовые типы языка Haskell. Строгая типизация. Структуры и конструкторы данных. Синонимы типов. Понятие модуля в Haskell. Правила оформления и использования модулей. Экспорт и импорт модулей. Квалификация модуля. Ограничение доступа к экспортируемым данным. Абстрактные типы данных в Haskell. Классы типов и их экземпляры в Haskell. Полиморфизм и его виды в функциональном программировании. Наследование классов и их реализация в Haskell. Сорта типов. Создание структур с безымянными и именованными полями.

Тема 3.2 Императивные возможности в функциональных языках.

Контейнерные типы данных. Алгебраические типы данных. Монады и монадические типы. Стандартные монады модуля Prelude. Монадические классы. Императивные возможности в функциональных языках. Реализация операций ввода/вывода в Haskell. Примеры разработки приложений.

4.2.2 Перечень и содержание лабораторных занятий.

№ п/п	№ темы	Наименование лабораторных работ	Кол. ч
1	1.1	Изучение базового синтаксиса языка Haskell 98.	2
2	1.2	Разработка приложений в строго функциональном стиле. Функции высшего порядка	2
3	1.2	Построение функциональных иерархий. Решение проблемы выбора подфункций.	4
4	2.1 – 2.2	Преобразование лямбда-выражений и выражений комбинаторной логики	8
5	3.1	Создание и использование абстрактных структур данных	26
6	3.2	Императивные возможности в функциональных языках.	12

5. Образовательные технологии

5.1 При чтении лекций используется мультимедийный компьютерный проектор с последующей раздачей демонстрируемых слайдов на электронном носителе.

5.2 При выполнении лабораторных работ используется проектный подход.

5.3. В лабораторном практикуме используются индивидуальные задания, использующие информационные системы и процессы управления, приближенные к реальным ситуациям.

5.4. При подготовке к лабораторным занятиям по разделу 2.1 и 3.2 используется электронные обучающий комплекс.

6. Учебно-методическое обеспечение самостоятельной работы студентов.

Оценочные средства для текущего контроля успеваемости,

промежуточной аттестации по итогам освоения дисциплины.

6.1. План самостоятельной работы студентов

№ нед.	Тема	Вид самостоятельной работы	Задание	Рекомендуемые источники	Кол-во часов
1-2	Тема 1.1 Поколения языков программирования. Функционально-логические языки программирования.	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Изучение истории происхождения современных функциональных языков программирования	- поисковые системы Internet. - рекомендуемая литература	4
3-4	Тема 1.2 Методы функционального программирования.	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Изучение исходного кода готовых программ.	- поисковые системы Internet. - рекомендуемая литература	4
5-9	Тема 2.1 Лямбда-исчисление	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Самостоятельная работа над редукцией сложных лябда-выражений по заданию преподавателя.	- поисковые системы Internet. - рекомендуемая литература	15
10-11	Тема 2.2 Комбинаторная логика.	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Самостоятельная работа над редукцией сложных комбинаторных выражений по заданию преподавателя	- поисковые системы Internet. - рекомендуемая литература	9
12-16	Тема 3.1 Синтаксис языка и типы данных. Объектно-ориентированные свойства языка Haskell.	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Изучение основных классов типов языка Haskell, реализованных в модуле Prelude. hs (в среде WinHUGS)	- поисковые системы Internet. - рекомендуемая литература	30
17-18	Тема 3.2 Императивные возможности в функциональных языках.	Подготовка к аудиторным занятиям. Подготовка к экзамену.	Изучение основных монадических классов языка Haskell, реализованных в модуле Prelude. hs (в среде WinHUGS)	- рекомендуемая литература - методические указания к выполнению лабораторных работ	24

6.2. Методические указания по организации самостоятельной работы студентов

Планируются следующие виды самостоятельной работы (внеаудиторной) относятся:

-  подготовка к выполнению лабораторных работ,

-  оформление отчётов по лабораторным работам,

-  изучение рекомендованной литературы для сдачи лабораторных работ,

-  изучение рекомендованной литературы при подготовке к зачету.

6.3. Материалы для проведения текущего и промежуточного контроля знаний студентов

Контроль освоения компетенций

№ п\п	Вид контроля	Контролируемые разделы	Компетенции, компоненты которых контролируются
1	Текущий и промежуточный: собеседование при защите лаб. заданий. Итоговый: сдача зачета, сдача экзамена	Раздел 1. Введение. Чисто функциональное программирование.	ОПК-2, ОПК-7, ПК-4, ПК-6.
2	Текущий и промежуточный: собеседование при защите лаб. заданий. Итоговый: сдача зачета, сдача экзамена	Раздел 2. Математические основы функционального программирования.	ОПК-2, ОПК-7
3	Текущий и промежуточный: собеседование при защите лаб. заданий. Итоговый: сдача зачета, сдача экзамена	Раздел 3. Функциональный язык Haskell	ПК-4, ПК-6.

Контроль освоения компетенции выполняется:

-  для компетенции (ОПК-2) - путем оценки способности студента к применять в профессиональной деятельности знания математических основ информатики - при выполнении лабораторных заданий, при сдаче зачета и экзамена;

-  для компетенции (ОПК-7) – путем оценки способности студента к использовать знания основных концептуальных положений функционального, логического, объектно-ориентированного и визуального направлений программирования, методов, способов и средств разработки программ в рамках этих направлений - при выполнении лабораторных заданий, при сдаче зачета и экзамена;

-  для компетенции (ПК-4) ‑ путем оценки способности студента к выбору архитектуры и комплексирования современных компьютеров, систем, комплексов и сетей системного администрирования - при выполнении лабораторных занятий, при сдаче зачета и экзамена;

-  для компетенции (ПК-6) ‑ путем оценки способности студента формировать суждения о проблемах современной информатики, ее категорий и связей с другими научными дисциплинами - при выполнении лабораторных занятий, при сдаче зачета и экзамена.

Варианты заданий для лабораторных работ

Все задания требуют реализации и отладки соответствующего программного кода на языке Haskell в среде WinHUGS

1. Подсчитать сумму каждого n-го элемента списка.

2. Найти факториал суммы элементов целочисленного списка.

3. Найти сумму факториалов элементов целочисленного списка.

4. Удалить отрицательные элементы из целочисленного списка.

5. Выполнить инверсию списка с использованием накапливающих параметров.

6. Выполнить построчную инверсию матрицы.

7. Найти максимальный/минимальный элементы матрицы.

8. Построить список из элементов главной диагонали матрицы.

9. Найти сумму элементов второстепенной диагонали матрицы.

10. Повернуть матрицу на 90 градусов по часовой стрелке.

11. Повернуть матрицу на 90 градусов против часовой стрелки.

12. Удалить из строки повторяющиеся элементы.

13. Произвести циклический сдвиг строки на n элементов вправо.

14. Произвести циклический сдвиг строки на n элементов влево.

15 Построить частотный словарь слов из входного предложения.

16. Реализовать базовые логические операции между двумя множествами: объединение, пересечение, вычитание, обратное пересечение.

17. Найти неизвестные слова в исходном предложении. Предварительно сформировать словарь известных слов.

18. Найти самое длинное слово в предложении.

19. Упорядочить слова предложения по убыванию их длины. Предварительно удалить повторяющиеся слова.

20. Кодирование слов исходного предложения двоичным кодом.

21. Декодирование исходного двоичного кода по заранее определенным правилам, задаваемым преподавателем.

Примерный перечень вопросов для собеседования на зачете

Раздел 1.

1. Исторические предпосылки возникновения функциональной парадигмы программирования.

2. Поколения и классификация языков программирования.

3. Отличительные характеристики функционального стиля программирования.

4. Классификация функциональных языков.

5. Базовые математические понятия, лежащие в основе функционального стиля: множество, кортеж, соответствие, функция.

6. Программирование при помощи функций.

7. Символьные данные и S-выражения.

8. Списки и деревья.

9. Элементарные селекторы и конструкторы с примерами применения.

10. Элементарные предикаты и арифметика с примерами применения.

11. Рекурсивные функции. Примеры применения рекурсивных функций на различных задачах обработки списков.

12. Проблема выбора подфункций.

13. Проблема модульности функциональной программы.

14. Накапливающие параметры с примерами применения.

15. Оптимизация программного кода за счет введения локальных определений.

16. Функции высших порядков.

Раздел 2.

17. История возникновения лябда-исчисления.

18. Основные типы лямбда-выражений. Понятия аппликации и абстракции.

19. Связанные и свободные переменные в лямбда-выражениях.

20. Правила преобразования лямбда-выражений.

21. Стандартные порядки редукций и ромбическое свойство системы редукций. Теорема Чёрча-Россера.

22. Аппликативный и нормальный порядки редукции, их сравнительный анализ и примеры применения. Теорема Карри.

23. Понятие слабой заголовочной нормальной формы.

25. История возникновения комбинаторной логики.

26. Комбинаторы Шейнфинкеля. Бестиповая комбинаторная логики.

27. Набор комбинаторов Карри.

28. Основные понятия комбинаторной логики: одноместная функция (комбинатор) и аппликация.

29. Базисные комбинаторные характеристики.

Раздел 3.

30. Структуры данных и их типы в функциональном языке Haskell.

31. Синонимы типов и конструкторы данных.

32. Рекурсивные типы данных. Перечислимые и бесконечные типы данных.

33. Понятие модуля в Haskell. Правила оформления и использования модулей.

34. Экспорт и импорт модулей. Квалификация модуля. Ограничение доступа к экспортируемым данным.

35. Абстрактные типы данных в Haskell.

36. Классы типов и их экземпляры в Haskell.

37. Полиморфизм и его виды в функциональном программировании.

38. Наследование классов и их реализация в Haskell. Сорта типов.

39. Создание структур с безымянными и именованными полями.

40. Понятие монады как контейнерного типа данных.

41. Стандартные монады модуля Prelude. Монадические классы.

42. Императивные возможности в функциональных языках.

43. Реализация операций ввода/вывода в Haskell.

7. Учебно-методическое и информационное обеспечение дисциплины (модуля)

7.1. Основная литература:

1. ункциональное программирование на языке Haskell, М.: ДМК-Пресс, 2015, 608 с.

2. рактика работы на языке Haskell, М.: ДМК-Пресс, 2015, 288 с.

3. емчужины проектирования алгоритмов. Функциональный подход, М.: ДМК-Пресс, 2015, 330 с.

4. Серано зучаем Haskell. Библиотека программиста, СПб.: Питер, 2015, 464 с.

5. зучай Haskell во имя добра!, М.:ДМК-Пресс, 2013, 490 с.

6. ункциональное программирование, М.: Мир, 1993, 637 с.

7. ямбда-исчисление. Его синтаксис и семантика, М.:Мир, 1985, 606 с.

7.2. Дополнительная литература:

8. 14 занимательных эссе о языке Haskell и функциональном программировании, М.: ДМК-Пресс, 2015, 222 с.

9. ункциональное и логическое программирование, М.: Academia, 2010, 320 с.

10. ункциональное и логическое программирование, М.: Бином. Лаборатория знаний, 2011, 120 с.

7.3. Интернет-ресурсы:

Материалы сайта https://www. haskell. org

Материалы сайта http://fprog. ru/

7.4 Программное обеспечение:

WinHUGS 98

8. Материально-техническое обеспечение дисциплины (модуля)

Лабораторные занятия проводятся в классе, оснащенном ПЭВМ, с операционной системой Windows 7.

Рабочая программа дисциплины «ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ» составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций ПрООП по направлению подготовки «Математическое обеспечение и администрирование информационных систем»

Программу составили:

д. т.н., профессор кафедры САПР

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры САПР

Протокол № ______________от «____» ______________ 2015 года

Зав. кафедрой САПР

Программа одобрена методической комиссией ФВТ

Протокол № ______от «____» ______________ 2015 года

Председатель методической комиссии ФВТ

Сведения о переутверждении программы на очередной учебный год и регистрации изменений

Учебный год	Решение кафедры (№ протокола, дата, подпись зав. кафедрой)	Внесенные изменения	Номера листов (страниц)
заменен- ных	новых	аннулиро-ванных