Государственное образовательное учреждение высшего профессионального
образования Московской области
«Международный университет природы, общества и человека «Дубна»
(университет «Дубна»)
УТВЕРЖДАЮ
проректор по учебной работе
С.В. Моржухина «_»_20 г.
ПРОГРАММА ДИСЦИПЛИНЫ
ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ
по направлению (специальности) 230105 65 — Программное обеспечение вычислительной техники и автоматизированных систем Форма обучения: очная Уровень подготовки: специалист Курс (семестр): 3(6) г. Дубна, 2010 г.Программа дисциплины «Функциональное и логическое программирование» по специальности 23105.65 «Программное обеспечение вычислительной техники и автоматизированных систем»: : Учебная программа. Автор: ст. преп. Ростовцев В.А.. Дубна:
Университет «Дубна», 2010г.
Автор программы:
ФИО, Ростовцев Виталий Александрович_ (подпись) Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и учебным планом по направлению подготовки (специальности) Программное обеспечение вычислительной техники и автоматизированных систем (указывается номер ОКСО, код и наименование направления подготовки (специальности)) Программа рассмотрена на заседании кафедры (название кафедры) Протокол заседания № _ от «» 200 г.
Заведующий кафедрой /_ / (ученое звание) (подпись) (фамилия, имя, отчество)
СОГЛАСОВАНО
заведующий выпускающей кафедрой1 /_ / (ученое звание) (подпись) (фамилия, имя, отчество) «» _ 20 г.Рецензент: _ (ученая степень, ученое звание, Ф.И.О., место работы, должность)
ОДОБРЕНО
декан факультета (директор института, филиала) _ // (ученое звание, степень) (подпись) (ФИО) «» _ 20 г.Руководитель библиотечной системы _ /_/ (подпись) (ФИО) 1. Выписка из ГОС ВПО Рабочая программа дисциплины «Функциональное и логическое программирование» является специальной дисциплиной для специальности 23105. «Программное обеспечение вычислительной техники и автоматизированных систем)», квалификация – специалист Индекс Наименование дисциплины и основные разделы Всего часов СД.02 Функциональное и логическое программирование Рекурсивные функции и лямбда-исчисление А.Черча;
программирование в функциональных обозначениях; функциональные языки; строго функциональный язык; приемы программирования;
представление и интерпретация функциональных программ; отладка программ; конкретные реализации языков функционального программирования; соответствие между функциональными и императивными программами; применения функционального Логическая программа: основные конструкции, операционная и декларативная семантика, интерпретация, корректность;
программирование баз данных; рекурсивное программирование;
вычислительная модель; анализ структуры термов; металогические предикаты; внелогические предикаты; недетерминированное программирование; неполные структуры данных; программирование второго порядка; методы поиска; обработка нечетких данных;
Constraint–Пролог: операционная семантика; применение логического программирования в задачах искусственного интеллекта.
Общий объём курса, согласно учебному графику на 2010-2011 учебный год – часов. Из них: лекции – 34 часа, семинарские занятия – 34 часа, самостоятельная работа – 72 час.
Сдача экзамена в 6-ом семестре.
Важность подготовки человека к быстрому восприятию и обработке больших объемов информации ведет к необходимости обучения современными средствами, методами и технологиями. В настоящее время возросла необходимость не просто освоения и накопления информации, а обучения такой технологии работы с информацией, которая позволяет извлекать информацию из различных источников, представлять ее в понятном виде и эффективно использовать в принятии решений.
В наши дни информация коснулась всех сторон общественной жизни, ее результаты отслеживаются практически в любой сфере человеческой деятельности.
Мощный информационный поток связан с появлением и внедрением передовых компьютерных информационных технологий. Профессиональная подготовка современного специалиста включает в себя обязательное изучение информационных технологий, овладение навыками работы с информацией.
В проектировани, разработке и реализации программного обспечения наряду с императивны стилем программирования широко используется также декларативный стиль, базирующийся на логическом основании логики высказываний и предикатов (язык Пролог), а также на логике лямбда-исчисления (язык Лисп). Возможности языков декларативного стиля позволяют решать различные задачи, возникающи в искусственном интеллекте, в том числе и задачи системного анализа и управления.
Перечень курсов, на которых базируется дисциплина Дисциплина «Функциональное и логическое программирование» базируется на дисциплинах: «Информатика» (1 и 2 семестры), «Дискретная математика» (3 семестр), «Математическая логика» (4 семестр), «Теория и технология программирования» (3 и семестры).
формы работы студентов:
- семинарские (практические) занятия, - выполнение самостоятельных работ по функциональному и логическому программированию.
виды контроля;
- Проверка выполнения практических самостоятельных заданий, методика формирования результирующей оценки;
- Оценивается знание материала в соответствии с программой курса.
- При формировании результирующей оценки учитывается посещаемость и активность студентов во время лекций и практических занятий, степень выполнения самостоятельных заданий.
(3) Требования к уровню освоения содержания дисциплины.
В процессе освоения содержания дисциплины студент должен приобрести:
Исходный уровень знаний студентов включает основы информатики, алгоритмы принятия решений, методы дискретной математики. Студенты должны владеть офисноинформационными технологиями и навыками программирования.
Полученные в ходе изучения дисциплины знания, студенты смогут применить в процессе разработки совокупности средств, способов и методов человеческой деятельности, направленных на создание и применение:
программного обеспечения вычислительной техники и автоматизированных систем обработки информации и управления;
систем автоматизированного проектирования;
4) Объем дисциплины и виды учебной работы (зачет, экзамен) (5)Содержание программы функциональных и императивных языков.
логического программирования.
исчислении предикатов. Язык пролог.
Заключение. Искусственный интеллект и 3.2. Содержание разделов дисциплины 1. Предмет и задачи курса. Связь с другими дисциплинами учебного плана.
Исторические предпосылки и развитие ФЛП. Языки ФЛП: лисп, пролог и др. Язык лисп и работы Дж. Маккарти. Системы искусственного интеллекта, компьютерной алгебры, экспертные системы. Обоснование "нетрадиционной" архитектуры ЭВМ, реализация лисп-машин и пролог-машин.
2. Программирование с помощью функций и процедур. Элементарные примеры.
Рекурсивные функции и -исчисление Черча. Строго функциональный язык.
Элементарные понятия. Символьные данные, динамические структуры, списки. Sвыражения. Представление данных и программ в виде S-выражений.
3. Строго функциональный язык. Базовые функции: конструкторы и селекторы, предикаты. Арифметика. Рекурсивные функции: разбор случаев, рекурсивные определения, выбор подфункций. Примеры обработки списков. Граничные условия и способы использования рекурсии. Предикаты "принадлежит" и "присоединить". Примеры программ с рекурсивными определениями.
4. Простые функциональные программы. Приемы программирования.
Накапливающие параметры. -выражения и определение функций. Локальные определения. Свободные и связные переменные. Функционалы - функции высших порядков. Пример простой функциональной программы - аналитическое дифференцирование.
5. Представление и интерпретация программ. Абстрактная и конкретная формы программы. Связывание значений и переменных. Понятие среды вычисления и замыкания. Интерпретатор инструментального лиспа: функции apply и eval.
Интерпретация переменных и констант, элементарных функций и предикатов, условных операторов, локальных определений.
6. Понятие о соответствии между функциональными и императивными программами.
Описание семантики императивного языка через интерпретатор.
7. Императивные элементы языка лисп. Лисп как язык разработки систем искусственного интеллекта и систем компьютерной алгебры. Диалекты Standard Lisp и Rlisp.
8. Обзор основных понятий, методов и средств логического программирования.
9. Реализация логического вывода в исчислении предикатов. Доказательство цели.
Факты, вывод свойств из фактов. Язык пролог. Синтаксис и унификация. Рекурсия.
10. Механизм возврата в прологе. Предикат repeat. Декларативная и процедурная семантика.
11. Механизм отсечения и способы его применения. Ловушки отсечения.
12. Встроенные предикаты. Обновление базы данных пролога. Особенности ввода/вывода. Обработка файлов.
13. Моделирование пролога средствами лиспа.
14. Искусственный интеллект и языки фпл.
Заключение. Тенденции и перспективы развития языков фпл.
(6) 3.3 Семинары Семинары в курсе "Функциональное и логическое программирование" строятся на базе разработки и реализации ряда программ, иллюстрирующих основные принципы, алгоритмы и приемы функционального программирования, излагаемые в лекционном курсе.
Проводится также разбор и обсуждение некоторых более сложных в реализации программ.
Семинар 1. Введение в систему программирования Lisp. Загрузка системы. Интерфейс.
Меню, справочная информация. Цикл вычисления. Синтаксис.
Семинар 2. Списковое представление данных. S-выражения. Запись S-выражений в системе программирования Lisp. Примеры: запись арифметических формул, запись шахматной позиции. Применение примитивных функций. Реализация функций размер, част, ост, расстояние. Рекурсивные функции длина, сумма, соединить.
Семинары 3-4. Выбор подфункций. Реализация функции обратить. Функция набор преобразование списка в множество.
Семинар 5. Накапливающие параметры. Вариант функций обратить, сумма и произведение.
Семинары 6-7. Локальные определения. Варианты функции сумм-произв с использованием формы let.
Семинар 8. Программирование функций с функциональными аргументами. Синтаксис определения. Варианты функций сум-произв, набор.
Семинары 9-10. Программирование функций с функциональными результатами.
Функция комп (композиция функций).
Семинар 11. Разработка и реализация функции аналитического дифференцирования.
Семинар 12. Построение интерпретатора языка "инструментальный лисп". Функции apply и eval Семинар 13. Введение в систему Prolog. Загрузка системы. Интерфейс. Меню, справочная информация. Синтаксис.
Семинар 14. Арифметика в прологе.
Семинар 15. Операторы в прологе. Вычисление многочленов Семинар 16. Механизм возврата в прологе. Задача поиска пути в лабиринте 3.4. График выполнения самостоятельных работ студентами работы
ВЗ РК СЗ ВЗ РК ВЗ
ВЗ – выдача задания на самостоятельную работу, РК – рубежный контроль, СЗ – сдача и защита задания 7) Учебно-методическое обеспечение дисциплины Основная литература 1. Свердлов С.З. Языки программирования и методы трансляции: Учебное пособие для вузов / Свердлов Сергей Залманович. - СПб.:Питер, 2007. - 638с.: ил. + 1 CD. - (Учебное пособие). - Прил.1-8:с.436.-Лит.:с.633. - Издательская программа "300 лучших учебников для высшей школы в честь 300-летия Санкт-Петербурга". - 300.piter.com.
2. Шалимов П.Ю. Функциональное программирование: Учебное пособие/ П.Ю. Шалимов; Федеральное агентство по образованию;
Брянский государственный технический университет (БГТУ); Науч.ред. Э.А.Лагерева. – Брянск: БГТУ, 2003. – 160 с.: ил. – Предм.указ.:с.155.- Список исп.и рек.лит.:с.157.
3. Ручкин В.Н. Универсальный искусственный интеллект и экспертные системы/ Ручкин Владимир Николаевич, Фулин Владимир Андреевич. – СПб.: БХВ-Петербург, 2009. – 240с.: ил.- Лит.:с.237.
Дополнительная литература 1. Бен-Ари М. Языки программирования: Практический сравнительный анализ: Учебник по языкам программирования / Бен-Ари М.;
Пер.с англ. В.С.Штаркмана, М.Н.Яковлевой под ред. В.С.Штаркмана. - М.: Мир, 2000. - 366с.: ил. - Прил.:с.353.-Предм.указ.:с.358.
2. Пратт Т. Языки программирования: разработка и реализация / Пратт Теренс, Зелковиц Марвин В.; Под общ.ред. А.Матросова. - 4-е изд. - СПб.: Питер, 2002. - 688с.: ил. - (Классика Computer Science). - Прил.:с.564-668.-Библиогр.:с.669-674.-Алф.указ.:с.675-688.
Средства обеспечения освоения дисциплины Для проведения семинарских занятий необходимы системы программирования на языках лисп и пролог.
8) Материально-техническое обеспечение дисциплины компьютерный класс доступ в Internet возможность ssh-соединения с многопроцессорной системой в ЛИТ ОИЯИ 9) Формы контроля Перечень вопросов, выносимых на экзамен по курсу ФЛП 1. Базовые функции обработки списков.
2. Определение и вызов функций с помощью -выражений. -список, преобразование. Свободные и связанные переменные. Функция DEFUN 3. Локальные определения (форма LET).
4. Функции более высокого порядка. Функциональный аргумент, функциональное значение. Способы композиции функций.
5. Автоматическое управление памятью в Лиспе. «Сборка мусора».
6. Создайте Лисп-список, предсталяющий собой список планет Солненой системы.
7. Почему значения в Лиспе представлены указателями?
8. Определите функцию add5(n), которая увеличивает числовой параметр n на 5.
9. Определите функцию add5(n), которая увеличивает числовой параметр n на 5, используя синтаксис -определения.
10. Суперпозиция (или «композиция») функций как средство формирования более 11. Какую (двоякую) роль играет в Лиспе функция eval?
12. Возвращение функцией нескольких величин.
13. Базовые функции Лиспа.
14. Опишите три варианта предиката равенства в Лиспе.
1. Равенство в Прологе.
2. Встроенные предикаты. Предикаты взаимодействия.
3. Встроенные предикаты. Размещение данных.
4. Аппарат вычислений. Обработка списков.
5. Аппарат вычислений. Рекурсивные определения в Прологе.
6. Аппарат вычислений. Управление откатом: отсечение.
7. Аппарат вычислений. Поиск в глубину с возвратом.
8. Аппарат вычислений. Вывод и процедура отката.
9. Аппарат вычислений. Процедура унификации в Прологе.
10. Синтаксис данных (термы и основные объекты Пролога).
11. Структура программы в языке Пролог (синтаксис языка).
12. Логическая и управляющая компоненты Пролога.
13. Привести пример записи о задаче в виде хорновских дизъюнктов логики предикатов и в языке Пролог.
14. Общая характеристика языка Пролог.
Пример экзаменационного билета _ Международный университет природы, общества и человека «Дубна»
Дисциплина: Функциональное и логическое программирование Базовые функции обработки списков. Связь между функциями CAR, CDR и CONS. Соглашение о вложенных вызовах CAR и CDR. Предикаты.
2 Равенство в Прологе.
_ кафедра РИВС направление.. 230105 65 ПОВТАС
Номер по 26.03. по 02.04. по 16.04. по 14.05. с 23.05. по 28.05. 16 нед зачетная с 30.05. по 04.06. Числитель - аудиторные занятия, знаменатель - самостоятельное изучение Учебная литература Дата
Номер по 26.03. по 02.04. по 16.04. по 14.05. с 23.05. по 28.05. 16 нед зачетная с 30.05. по 04.06. Числитель - аудиторные занятия, знаменатель - самостоятельное изучение Учебная литература Дата