3) (Duplet L) – создание списка с дублируемыми элементами списка L: (Duplet '(=
4) (Reverse L) – создание списка с элементами L, следующими в обратном порядке: (Reverse '(=
5) (Mirror L) – создание списка с элементами L, следующими сначала в прямом, а затем – в обратном порядке: (Mirror '(=
6) (SumList L) – определение суммы элементов списка, являющихся числами: (SumList '(1= 10.6.
7) (SumEvenList L) – определение суммы элементов списка, являющихся целыми чётными числами: (SumEvenList '(1= 4.
8) (FloatList L) – создание из элементов списка L с произвольными уровнями вложенности одноуровнего списка: (FloatList '(1=
Вспомогательные функции:
(NUMBERP N) – проверяет, является ли параметр N числом.
(INTEGERP N) – проверяет, является ли параметр N целым числом.
(EVENP N) – проверяет, является ли целое число N чётным.
(ATOM A) – проверяет, является ли параметр A атомом.
3. Функции для работы с множествами
Реализовать функции для работы с множествами:
1) (Member1 E L) – проверка принадлежности параметра E списку L:
2) (Len '(3 4) '(1= T.
3) (DelRep1 L) – создание списка с элементами L без повторений:
4) (DelRep1 '() =
5) (Union1 L1 L2) – создание множества, объединяющего в себе элементы списков L1 и L2: (Union '('(=
6) (Intersection1 L1 L2) – создание множества, содержащего элементы, которые встречаются и в L2, и в L1:
7) (Inersection1 '('(=
8) (Difference1 L1 L2) – создание множества, содержащего элементы списка L1, не встречающиеся в списке L2:
9) (Difference1 '('(= (1).
10) (Subset1 L1 L2) – проверка принадлежности всех элементов множества L1 множеству L2: (Subset1 '('(= T.
11) (Decart L1 L2) – создание списка, представляющего декартово произведение множеств, получаемых из списков L1 и L2: (Decart '('(= 4)4)4)).
12) При помощи созданных функций реализовать функции (S1 L1 L2 L3), (S2 L1 L2 L3), ..., (S6 L1 L2 L3), формирующие из своих списков-параметров множества, представленные кругами Эйлера:
Все функции должны работать со списками любого уровня вложенности.
Вспомогательные функции:
(ATOM A) – проверяет, является ли параметр A атомом.
(LISTP L) – проверяет, является ли параметр L списком.
4. Функции для работы с деревьями
Реализовать функции для работы с бинарными деревьями поиска:
1) 1. (Infix Tree) – возвращает список элементов дерева Tree в порядке инфиксного обхода:
2) (Infix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL=
3) 2. (Prefix Tree) – возвращает список элементов дерева Tree в порядке префиксного обхода:
4) (Prefix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL=
5) 3. (Postfix Tree) – возвращает список элементов дерева Tree в порядке постфиксного обхода:
6) (Postfix '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL=1
7) 4. (SearchEl E Tree) – проверяет наличие в дереве Tree элемента E:
8) (SearchEl 11 '( ((NIL 1 NIL) 3 (NIL 4 NIL)) 5 ((NIL 6 NIL) 7 ((NIL 11 NIL) 13 (NIL 15 NIL= T.
9) 5. (AddEl E Tree) – добавляет в бинарное дерево поиска Tree элемент E:
10) (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))) ).
11) 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 – в противном случае;
- выводит список, в котором на месте соответствующего числа исходного списка стоит сумма двух предшествующих ему чисел исходного списка;
- выводит в обратном порядке список отрицательных чисел исходного списка, каждое из которых умножено на следующее за ним число исходного списка;
- выводит список отличных от нуля чисел исходного списка. При этом каждый элемент в возвращаемом списке повторяется два раза (например,.
3. Комбинаторная задача.
Алфавит языка содержит n букв. Написать программу, которая определяет количество слов, которые можно составить из k букв этого алфавита при условии, что буквы в словах не повторяются.
Алфавит языка содержит n букв. Написать программу, которая определяет количество слов, которые можно составить из k букв этого алфавита при условии, что буквы в словах могут повторяться.
К театральной кассе направляются n человек. Написать программу, которая определяет, сколько различных вариантов очереди могут образовать эти люди.
Требуется из n кандидатов избрать комиссию, состоящую из k человек. Написать программу, которая определяет количество различных возможных вариантов формирования данной комиссии.
На потоке некоторой специальности изучается n дисциплин. Написать программу, которая определяет количество возможных вариантов расписания на субботу, если известно, что в этот день недели должно преподаваться k различных дисциплин.
Юноша решил подарить девушке букет из k цветов. В оранжерее имеются n наименований различных цветов. Написать программу, которая определяет количество возможных вариантов составить букет.
Имеется слово, состоящее из n различных символов некоторого алфавита. Написать программу, которая определяет, сколько различных слов может быть образовано из k символов данного слова.
Позывные радиостанции должны начинаться с некоторого определенного символа из алфавита, в котором n символов. Написать программу, которая определяет, скольким радиостанциям можно присвоить различные позывные длиной k символов, если известно, что символы в позывных могут повторяться.
В научное сообщество входят n человек. Написать программу, которая определяет, сколько существует возможных вариантов назначить его представителей на k должностей, если известно, что один человек может занимать только одну должность.
По результатам спортивных состязаний получилось, что никакие двое из n участвовавших в них спортсменов не набрали одинаковое количество очков. Написать программу, которая определяет количество возможных вариантов размещения этих спортсменов в турнирной таблице.
Известно, что длина номеров определенного вида составляет n символов. Некоторый рассеянный человек постоянно забывает последние k символов нужного ему номера данного вида в том случае, если эти символы различны. Написать программу, которая поможет ему определить максимальное количество комбинаций символов, которые потребуется перебрать, чтобы получить забытый номер.
В научное сообщество входят n человек. Написать программу, которая определяет, сколько существует возможных вариантов отправить k его представителей на конференцию.
Задания для разработки программ к зачетным билетам:
1. Написать функцию, возвращающую факториал числа.
2. Написать функцию, возвращающую длину списка.
3. Написать функцию, возвращающую сумму элементов списка.
4. Написать функцию, возвращающую число последовательности Фибоначчи по его номеру.
5. Написать функцию, проверяющую принадлежность элемента списку.
6. Написать функцию, возвращающую список, обратный заданному.
7. Написать функцию, возвращающую результат объединения двух списков.
8. Написать функцию, возвращающую максимальный элемент списка.
9. Написать функцию, возвращающую степень числа.
10. Написать функцию, возвращающую элемент списка по его номеру.
Примерные темы рефератов:
1. • История формирования понятия "алгоритм".
2. • Известнейшие алгоритмы в истории математики.
3. • Проблема существования алгоритмов в математике.
4. • Средства и языки описания (представления) алгоритмов.
5. • Методы разработки алгоритмов.
6. • Формализация понятия алгоритм.
7. • Проблема алгоритмической разрешимости в математике.
8. • Основатели теории алгоритмов - Клини, Черч, Пост, Тьюринг.
9. • Основные определения и теоремы теории рекурсивных функций.
10. • Тезис Черча.
11. • Проблемы вычислимости в математической логике.
12. • Машина Поста.
13. • Машина Тьюринга.
14. • Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.
15. • Парадигма логического программирования — альтернатива процедурному и функциональному программированию.
Вопросы к зачету:
1. Основные существующие парадигмы программирования, история их возникновения и развития.
2. Отличия между императивной, логической и функциональной парадигмами программирования
3. Понятие о функциональном стиле программирования. Отличительные особенности этого стиля.
4. Понятие слабоформализуемых задач. Особенности задач искусственного интеллекта.
5. Примеры языков функционального программирования. История развития и основные отличия
6. Основные черты и особенности языка ЛИСП.
7. Лямбда-исчисление: базовые понятия и правила редукций.
8. Лямбда-исчисление: нормальная форма и ее единственность
9. Понятие об энергичном и ленивом вычислениях. "Бесконечные" структуры данных.
10. Объекты языка ЛИСП. Символы, константы, атомы, логические значения. Синтаксис определения списков и вызова функций.
11. Основные функции-селекторы языка ЛИСП. Примеры использования.
12. Основные функции-распознаватели языка ЛИСП. Примеры использования.
13. Синтаксис определения пользовательских функции в программе. Пример.
14. Управляющие структуры на примере функций с ветвлением.
15. Рекурсивные функции на примере сортировки списка.
16. Понятие функционалов. Пример с использованием функционала MAP.
10. Образовательные технологии.
Сочетание традиционных и новых образовательных технологий в ходе проведения лекций, компьютерных лабораторных работ и контрольных мероприятий (контрольных работ, промежуточного тестирования, зачета и экзамена).
Аудиторные занятия:
· лекционные и лабораторные занятия; контроль осуществляется в ходе опроса на лекциях, проверки конспектов, при сдаче заданий лабораторных работ и самостоятельной работы. В течение обучения студенты выполняют комплексы индивидуальных заданий;
· активные и интерактивные формы – проблемные вопросы на лекциях, дискуссии по результатам выполнения заданий, работа студенческих исследовательских групп.
Внеаудиторные занятия:
· самостоятельная работа (выполнение самостоятельных заданий разного типа и уровня сложности на лабораторных занятиях, подготовка к аудиторным занятиям, подготовка проектов и курсовых работ, изучение отдельных тем и вопросов учебной дисциплины в соответствии с учебно-тематическим планом, составление конспектов, выполнение индивидуальных заданий: докладов, сообщений, выполнение самостоятельных работ, подготовка ко всем видам контрольных испытаний: текущему контролю успеваемости и промежуточной аттестации);
· индивидуальные консультации.
11. Учебно-методическое и информационное обеспечение дисциплины (модуля).
11.1. Основная литература:
1. 14 занимательных эссе о языке Haskell и функциональном программировании [Электронный ресурс] / . – М.: ДМК Пресс, 2011. – 142 с. – Режим доступа:
http://*****/index. php? page=book&id=129727 (дата обращения 20.05.2013)
2. Душкин работы на языке Haskell [Электронный ресурс] / . – М.: ДМК Пресс, 2010. – 288 с. – Режим доступа: http://*****/index. php? page=book&id=86486 (дата обращения 20.05.2013)
3. Душкин программирование на языке Haskell [Электронный ресурс] / . – М.: ДМК Пресс, 2008. – 608 с. – Режим доступа: http://*****/index. php? page=book&id=86129 (дата обращения 20.05.2013)
11.2. Дополнительная литература:
1. Кауфман программирования. Концепции и принципы [Электронный ресурс] / . – М.: ДМК Пресс, 2011. – 464 с. – Режим доступа: http://*****/index. php? page=book&id=86526 (дата обращения 20.05.2013).
2. Сошников программирование на F# [Электронный ресурс] / . – М.: ДМК Пресс, 2011. – 194 с. – Режим доступа: http://*****/index. php? page=book&id=129901 (дата обращения 20.05.2013)
3. Программирование на языке Ruby [Электронный ресурс] / Х. Фултон. – М.: ДМК Пресс, 2007. – 688 с. – Режим доступа: http://*****/index. php? page=book&id=47356 (дата обращения 20.05.2013)
4. JRuby. Сборник рецептов [Электронный ресурс] / Д. Эдельсон, Г. Лю. – М.: ДМК Пресс, 2010. – 235 с. – Режим доступа: http://*****/index. php? page=book&id=86487 (дата обращения 20.05.2013).
11.3. Программное обеспечение и Интернет – ресурсы:
Интерпретаторы языков функционального и рекурсивно-логического программирования Lisp, Haskell.
12. Технические средства и материально-техническое обеспечение дисциплины (модуля).
Учебные аудитории для проведения лекционных занятий, оснащенные мультимедийным оборудованием. Компьютерные классы с установленными интерпретаторами языков функционального программирования Lisp, Haskell.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
