Спецкурс "Рекурсивные алгоритмы" (Recursive algorithms) |
Лектор: ст. преподаватель факультета ВМК МГУ Баева Наталия Валерьевна
Занятия по четвергам 18:00 – 19:45 аудитория 524
Аннотация
Спецкурс для студентов, у которых есть желание углубить знания
об использовании рекурсии в программировании. На базе функциональных языков программирования Рефал и Лисп будут изучаться различные виды рекурсии,
и обсуждаться эффективность предложенных алгоритмов.
В ходе занятий студентами пишутся самостоятельные и контрольные работы. Для допуска к экзамену нужно выполнить два обязательных практических задания. Спецкурс читается бакалаврам 1-3 курсов.
Обратите внимание! На спецкурсе обязательное посещение и обязательная сдача практических заданий. Оценка выставляется по результатам работы в семестре и письменному экзамену. Второкурсникам возможна выдача 1-2 рекомендаций на кафедру АЯ.
Программа курса
1. Базисный Рефал
1.1. Рефал и нормальные алгоритмы Маркова
1.2. Выражения и переменные
1.3. Функции и предложения
1.4. Абстрактная Рефал-машина
1.5. Правила синтаксического отождествления
2. Язык Рефал-2
2.1. Символы-литеры и составные символы
2.2. Переменные и их спецификации
2.3. Особенности синтаксического отождествления
2.4. Встроенные функции
2.5. Функции для работы с копилкой
2.6. Оформление и запуск программы
3. Решение задач на языке Рефал
3.1. Посимвольная обработка текста
3.2. Структурирование текста
3.3. Обработка структурированного текста
4. Базовый Лисп
4.1. Атомы и списки, функции, базовый набор функций
4.2. Определение функций, встроенные функции
4.3. Рекурсивные функции
4.4. S-выражения, внутреннее представление S-выражений
4.5. Лисп-программа
5. Решение задач на языке Лисп
5.1. Простая рекурсия, косвенная рекурсия
5.2. Параллельная рекурсия
5.3. Накапливающий параметр
5.4. Рекурсия более высокого порядка
Основная литература
1 Большакова Е. И., Груздева Н. В. Основы программирования на языке Рефал (учебное пособие) – М.: Издательский отдел факультета ВМК МГУ, 2009 – 93 с.
2 Большакова Е. И., Груздева Н. В. Основы программирования на языке Лисп: Учебное пособие. – М.: Издательский отдел факультета ВМК МГУ имени М.В.Ломоносова; МАКС Пресс, 2010 – 112 с.
Дополнительная литература
1 www.refal.ru Recursive functions algorithmic language
2 Сайбель П. Практическое использование Common Lisp - М.: ДМК Пресс, 2017 - 488 с.
3 Хювёнен Э., Сеппянен Й. Мир Лиспа. В 2-х т. / Пер. с финск.. — М.: Мир, 1990.