Государственное образовательное учреждение высшего профессионального

образования Московской области

«Международный университет природы, общества и человека «Дубна»

(университет «Дубна»)

УТВЕРЖДАЮ

проректор по учебной работе

С.В. Моржухина «_»_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. Числитель - аудиторные занятия, знаменатель - самостоятельное изучение Учебная литература Дата