Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «тюменский государственный университет» Институт математики и компьютерных наук Кафедра программного обеспечения

1.2. Теоретические основы функционального программирования. Лямда-исчисление А.Черча. Языки функционального программирования. Теоретические основы функционального программирования. Рекурсивные функции и лямбда-исчисление А. Черча. Программирование в функциональных обозначениях. Понятие строго функционального языка. Представление и интерпретация функциональных программ. Примеры языков функционального программирования. 2.1. Основные понятия функционального программирования. Основные понятия функционального программирования. Основы языка Лисп. Символы, константы, атомы, логические значения. Базовые функции. Основные понятия функционального программирования: атом, список, символьное выражение, функция. Базовые функции языка ЛИСП. Селекторы, конструкторы и предикатные функции. 2.2. Определение функции в программе. Передача параметров в Лиспе. Определение функции в программе. Лямбда-выражение и лямбда-вызов. Функция определения функции. Список аргументов. Сопоставление формальных и фактических параметров при оценивании лямбда-вызова. 2.3. Управляющие структуры. Управляющие структуры. Классификация управляющих структур. Структуры следования, разветвления и повторения. 3.1. Рекурсивный стиль программирования. Рекурсивный стиль программирования. Основы теории рекурсивных функций. Средства и приемы построения рекурсивных программ. Сравнение рекурсивного и итеративного подхода к реализации алгоритмов. 3.2. Функционалы. Функционалы. Понятие функционала. Применяющие и отображающие функционалы. Организация циклических вычислений с применением функционалов. Примеры решения задач. 3.3. Средства ввода и вывода. Ввод и вывод. Организация работы с файлами. Основные функции ввода/вывода информации. Макросы чтения. Заключение. Перспективы развития языков функционального программирования. Планы семинарских занятий. 1. Изучение среды разработки muLisp. Общие принципы работы интерпретатора. 2. Применение селекторов для операций над списками. 3. Применение функции Quote. 4. Применение арифметических функций List. 5. Написание простейших функций. 6. Реализация сортировки с помощью рекурсивных функций. 7. Практическое применение инструментов ввода-вывода. Темы лабораторных работ. Тема 1.2 .Разработка программ в декларативном стиле в процедурном языке программирования. Тема 2.2 . Лямбда-выражение и специальная форма DEFUN. Простые и условные формы. Рекурсивное определение функции. Алгоритм сортировки слиянием на языке Lisp. Тема 2.3. Алгоритм «быстрой» сортировки на языке Haskell. Передача параметров и область их действия. Примерная тематика курсовых работ (не запланированы). 9. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля). Задания для домашних работ: Функции для работы с числами Реализовать функции тремя способами: с использованием только функции IF; с использованием функций IF и RETURN-FROM; с использованием только функции COND. Функции для реализации: (Max a b) – определение максимального из двух чисел; (Fact N) – расчёт факториала числа; (Fib N) – определение числа Фибоначчи по его номеру в последовательности: −10 −9 −8 −7 −6 −5 −4 −3 −2 −1 −55 34 −21 13 −8 5 −3 2 −1 1 0 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 5 8 13 21 34 55 (Pow a n) – расчёт степени в целых числах. (Discriminant a b c) – определение дискриминанта квадратного уравнения с коэффициентами a, b и c. При реализации следует использовать функцию (Pow a n). (Root a b c n) – определение корня квадратного уравнения с коэффициентами a, b и c, где n – номер корня (n = 1 для x1, n = 2 для x2). При реализации следует использовать функцию (Discriminant a b c). (BiRoot a b c n) – определение корня биквадратного уравнения. Аналогична функции (Root a b c n), n может принимать значения 1, 2, 3, 4. При реализации следует использовать функцию (Root a b c n). Допускается использовать рекурсивный вызов функции. Функции должны обрабатывать возможные некорректные значения аргументов, возвращая NIL. Вспомогательные функции: (INTEGERP N) – проверяет, является ли параметр N целым числом. (SQRT N) – извлекает квадратный корень из числа N. Функции для работы со списками Реализовать функции для работы со списками: (Len L) – определение длины списка (учитываются элементы первого уровня): (Len '(1 (2 (3 4)) 5)) = 3. (Append1 L1 L2) – слияние двух списков аналогично стандартной функции APPEND (при реализации следует использовать стандартную функцию CONS). (Duplet L) – создание списка с дублируемыми элементами списка L: (Duplet '(1 2 3)) = (1 1 2 2 3 3). (Reverse L) – создание списка с элементами L, следующими в обратном порядке: (Reverse '(1 2 3)) = (3 2 1). (Mirror L) – создание списка с элементами L, следующими сначала в прямом, а затем – в обратном порядке: (Mirror '(1 2 3)) = (1 2 3 3 2 1) (SumList L) – определение суммы элементов списка, являющихся числами: (SumList '(1 (2 3) 4 5.6)) = 10.6. (SumEvenList L) – определение суммы элементов списка, являющихся целыми чётными числами: (SumEvenList '(1 (2 3) 4 5.6)) = 4. (FloatList L) – создание из элементов списка L с произвольными уровнями вложенности одноуровнего списка: (FloatList '(1 (2 (3)) (4))) = (1 2 3 4). Вспомогательные функции: (NUMBERP N) – проверяет, является ли параметр N числом. (INTEGERP N) – проверяет, является ли параметр N целым числом. (EVENP N) – проверяет, является ли целое число N чётным. (ATOM A) – проверяет, является ли параметр A атомом. Функции для работы с множествами Реализовать функции для работы с множествами: (Member1 E L) – проверка принадлежности параметра E списку L: (Len '(3 4) '(1 (2 (3 4)) 5)) = T. (DelRep1 L) – создание списка с элементами L без повторений: (DelRep1 '(1 1 2 3 4 2 5 3)) = (1 2 3 4 5). (Union1 L1 L2) – создание множества, объединяющего в себе элементы списков L1 и L2: (Union '(1 2 3 1) '(2 3 4 4)) = (1 2 3 4). (Intersection1 L1 L2) – создание множества, содержащего элементы, которые встречаются и в L2, и в L1: (Inersection1 '(1 2 3 1) '(2 3 4 4)) = (2 3). (Difference1 L1 L2) – создание множества, содержащего элементы списка L1, не встречающиеся в списке L2: (Difference1 '(1 2 3 1) '(2 3 4 4)) = (1). (Subset1 L1 L2) – проверка принадлежности всех элементов множества L1 множеству L2: (Subset1 '(3 2 4) '(2 3 4 4)) = T. (Decart L1 L2) – создание списка, представляющего декартово произведение множеств, получаемых из списков L1 и L2: (Decart '(1 2 3 1) '(2 3 4 4)) = ((1 2) (1 3) (1 4) (2 2) (2 3) (2 4) (3 2) (3 3) (3 4)). При помощи созданных функций реализовать функции (S1 L1 L2 L3), (S2 L1 L2 L3), ..., (S6 L1 L2 L3), формирующие из своих списков-параметров множества, представленные кругами Эйлера: Все функции должны работать со списками любого уровня вложенности. Вспомогательные функции: (ATOM A) – проверяет, является ли параметр A атомом. (LISTP L) – проверяет, является ли параметр L списком. Функции для работы с деревьями Реализовать функции для работы с бинарными деревьями поиска: 1. (Infix Tree) – возвращает список элементов дерева Tree в порядке инфиксного обхода: (Infix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = (1 3 4 5 6 7 11 13 15). 2. (Prefix Tree) – возвращает список элементов дерева Tree в порядке префиксного обхода: (Prefix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = (5 3 1 4 7 6 13 11 15). 3. (Postfix Tree) – возвращает список элементов дерева Tree в порядке постфиксного обхода: (Postfix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = (1 4 3 6 11 15 13 7 5). 4. (SearchEl E Tree) – проверяет наличие в дереве Tree элемента E: (SearchEl 11 '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = T. 5. (AddEl E Tree) – добавляет в бинарное дерево поиска Tree элемент E: (AddEl 2 '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = ( ((NIL 1 (NIL 2 NIL)) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) ). 6. (DelEl E Tree) – удаляет из бинарного дерева поиска Tree элемент E: (DelEl 3 '( ((NIL 1 NIL) 4 NIL) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) )) = ( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL))) ). Задания для контрольных работ: 1. Задан числовой ряд (номер варианта по списку). Требуется написать программу, которая определяет сумму ряда c точностью eps > 0. Точность достигнута, если очередное слагаемое по модулю меньше eps (все последующие слагаемые после него не учитывать). № Формула ряда № Формула ряда 1. 7. 2. 8. 3. 9. 4. 10. 5. 11. 6. 12. 2. Дан список вещественных чисел. Написать программу, которая: выводит список разностей, в котором на месте соответствующего числа исходного списка стоит разность его и следующего за ним числа исходного списка (последнее число остается без изменений); выводит список, в котором на месте соответствующего числа исходного списка стоит частное от деления его на следующее за ним число исходного списка (последнее число остается без изменений); выводит список, в котором на месте соответствующего числа исходного списка стоит 0, если оно меньше 3.14, и 1 – в противном случае. При этом возвращаемый список должен быть симметричен списку-результату относительно его последнего элемента (например, (0 1 1 0 0 0 0 1 1 0) для (0 1 1 0 0) ); выводит список, в котором на месте соответствующего числа исходного списка стоит сумма следующих за ним чисел исходного списка; выводит список, в котором на месте соответствующего числа исходного списка стоит максимальное из следующих за ним чисел исходного списка; выводит список, в котором на месте соответствующего числа исходного списка стоит частное от деления единицы на сумму квадратов двух следующих за ним чисел исходного списка (предпоследнее число будет давать единицу, деленную на квадрат последнего числа исходного списка, а последнее – ноль); выводит список, в котором на месте соответствующего числа исходного списка стоит его куб, если оно отрицательное, и его квадрат – в противном случае; выводит список, в котором на месте соответствующего числа исходного списка стоит оно же само, если количество следующих за ним чисел исходного списка четно, и противоположное ему по знаку число – в противном случае; выводит список, в котором на месте соответствующего числа исходного списка стоит оно же само, если оно равно следующему за ним числу исходного списка, и 0 – в противном случае; выводит список, в котором на месте соответствующего числа исходного списка стоит сумма двух предшествующих ему чисел исходного списка; выводит в обратном порядке список отрицательных чисел исходного списка, каждое из которых умножено на следующее за ним число исходного списка; выводит список отличных от нуля чисел исходного списка. При этом каждый элемент в возвращаемом списке повторяется два раза (например, (1 1 2 2 3 3) ). 3. Комбинаторная задача. Алфавит языка содержит n букв. Написать программу, которая определяет количество слов, которые можно составить из k букв этого алфавита при условии, что буквы в словах не повторяются. Алфавит языка содержит n букв. Написать программу, которая определяет количество слов, которые можно составить из k букв этого алфавита при условии, что буквы в словах могут повторяться. К театральной кассе направляются n человек. Написать программу, которая определяет, сколько различных вариантов очереди могут образовать эти люди. Требуется из n кандидатов избрать комиссию, состоящую из k человек. Написать программу, которая определяет количество различных возможных вариантов формирования данной комиссии. На потоке некоторой специальности изучается n дисциплин. Написать программу, которая определяет количество возможных вариантов расписания на субботу, если известно, что в этот день недели должно преподаваться k различных дисциплин. Юноша решил подарить девушке букет из k цветов. В оранжерее имеются n наименований различных цветов. Написать программу, которая определяет количество возможных вариантов составить букет. Имеется слово, состоящее из n различных символов некоторого алфавита. Написать программу, которая определяет, сколько различных слов может быть образовано из k символов данного слова. Позывные радиостанции должны начинаться с некоторого определенного символа из алфавита, в котором n символов. Написать программу, которая определяет, скольким радиостанциям можно присвоить различные позывные длиной k символов, если известно, что символы в позывных могут повторяться. В научное сообщество входят n человек. Написать программу, которая определяет, сколько существует возможных вариантов назначить его представителей на k должностей, если известно, что один человек может занимать только одну должность. По результатам спортивных состязаний получилось, что никакие двое из n участвовавших в них спортсменов не набрали одинаковое количество очков. Написать программу, которая определяет количество возможных вариантов размещения этих спортсменов в турнирной таблице. Известно, что длина номеров определенного вида составляет n символов. Некоторый рассеянный человек постоянно забывает последние k символов нужного ему номера данного вида в том случае, если эти символы различны. Написать программу, которая поможет ему определить максимальное количество комбинаций символов, которые потребуется перебрать, чтобы получить забытый номер. В научное сообщество входят n человек. Написать программу, которая определяет, сколько существует возможных вариантов отправить k его представителей на конференцию.

Похожие:

	Федеральное государственное бюджетное образовательное учреждение... Кафедра иностранных языков и межкультурной профессиональной коммуникации экономико-правовых направлений		Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Оказанных услуг г. Саранск «31» марта 2013г Федеральное государственное... Федеральное государственное бюджетное учреждение науки институт космических исследований российской академии наук		Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Тюменский государственный университет Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Федеральное государственное бюджетное образовательное учреждение...
	Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Федеральное государственное бюджетное образовательное учреждение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Тюменский государственный университет «утверждаю»: Проректор по учебной работе Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Тюменский государственный университет «утверждаю»: Проректор по учебной работе Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Тюменский государственный университет «утверждаю»: Проректор по учебной работе Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Тюменский государственный университет «утверждаю»: Проректор по учебной работе Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования