НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
«УТВЕРЖДАЮ»
Декан АВТФ
д. т.н., проф.
______________________
31 августа 2005 г.
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
«ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ»
Основная образовательная программа: | Направление 230100 – «Информатика и вычислительная техника» (бакалавриат) Направление 654600 – «Информатика и вычислительная техника» (инженерная подготовка) |
Специализация: | 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем» |
Факультет: | автоматики и вычислительной техники (очная форма обучения) |
Курс: | 3 |
Семестр: | 5 |
Лекции: | 51 час |
Лабораторные занятия: | 17 часов |
Курсовой проект: | 5 семестр |
Самостоятельная работа: | 72 часа |
Экзамен: | 5 семестр |
Государственный экзамен: | 8 семестр |
Всего: | 140 часов |
Новосибирск
2005 г.
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования (ГОСВПО) по направлению 230– «Информатика и вычислительная техника».
Регистрационный номер и дата утверждения ГОСВПО по направлению 230– «Информатика и вычислительная техника»: 35 тех/бак, 13 марта 2000 г. (224 тех/дс, 27 марта 2000 г.)
Индекс дисциплины в ГОСВПО ‑ СД.00 (СД.02)
Компонент – национально-региональный (вузовский)
Цикл СД – Специальные дисциплины
Учебный план по направлению 230100 – «Информатика и вычислительная техника», специализация 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем» (набор 2001 г. и последующие)
Рабочая программа обсуждена на заседании кафедры вычислительной техники 31 августа 2005 г., протокол №7.
Программу разработала
ст. преп. кафедры ВТ
Зав. кафедрой ВТ,
ответственный за основную
образовательную программу
по направлениям
230100 и д. т.н., проф.
1. ВНЕШНИЕ ТРЕБОВАНИЯ
Квалификационные требования ГОСВПО по направлению 230100 – «Информатика и вычислительная техника»:
1.3.5. Квалификационные требования
Для компетентного и ответственного решения профессиональных задач бакалавр:
- готов участвовать во всех фазах проектирования и разработки объектов профессиональной деятельности;
- готов участвовать в разработке всех видов документации на программные, аппаратные и программно-аппаратные комплексы;
- способен использовать современные методы, средства и технологии разработки объектов профессиональной деятельности;
- готов участвовать в проведении научных исследований и выполнении технических разработок в своей профессиональной области;
- способен изучать специальную литературу и другую научно-техническую информацию, достижения отечественной и зарубежной науки и техники в области своей профессиональной деятельности;
- взаимодействует со специалистами смежного профиля при разработке методов, средств и технологий применения объектов профессиональной деятельности в научных исследованиях и проектно-конструкторской деятельности, в управлении технологическими, экономическими, социальными системами и в гуманитарных областях деятельности человека;
- готов к кооперации с коллегами и работе в коллективе при разработке объектов профессиональной деятельности;
- умеет на научной основе организовать свой труд, владеет современными информационными технологиями, применяемыми в сфере его профессиональной деятельности;
- способен в условиях развития науки и изменяющейся социальной практики к переоценке накопленного опыта, анализу своих возможностей, умеет приобретать новые знания, используя современные информационные образовательные технологии;
- методически и психологически готов к изменению вида и характера своей профессиональной деятельности, работе над междисциплинарными проектами.
Бакалавр должен знать:
- методические и нормативные материалы по проектированию и разработке объектов профессиональной деятельности;
- технологию проектирования и разработки объектов профессиональной деятельности;
- перспективы и тенденции развития информационных технологий;
- технические характеристики и экономические показатели лучших отечественных и зарубежных образцов объектов профессиональной деятельности;
- порядок, методы и средства защиты интеллектуальной собственности;
- методы анализа качества объектов профессиональной деятельности;
- современные средства вычислительной техники, коммуникаций и связи;
- основные требования к организации труда при проектировании объектов профессиональной деятельности;
- правила, методы и средства подготовки технической документации;
- основы экономики, организации труда, организации производства и научных исследований;
- основы трудового законодательства;
- правила и нормы охраны труда.
Требования ГОСВПО к обязательному минимуму содержания по направлению 654600 – «Информатика и вычислительная техника»:
Индекс | Наименование дисциплины и ее основные разделы | Часы |
СД.02 | Функциональное и логическое программирование: рекурсивные функции и лямбда-исчисление А. Черча; программирование в функциональных обозначениях; функциональные языки; строго функциональный язык; приемы программирования; представление и интерпретация функциональных программ; отладка программ; конкретные реализации языков функционального программирования; соответствие между функциональными и императивными программами; применения функционального программирования; логическая программа: основные конструкции, операционная и декларативная семантика, интерпретация, корректность; программирование баз данных; рекурсивное программирование; вычислительная модель; анализ структуры термов; металогические предикаты; внелогические предикаты; недетерминированное программирование; неполные структуры данных; программирование второго порядка; методы поиска; обработка нечетких данных; Constraint–Пролог: операционная семантика; применение логического программирования в задачах искусственного интеллекта. | 140 |
2. ОСОБЕННОСТИ (ПРИНЦИПЫ) ПОСТРОЕНИЯ ДИСЦИПЛИНЫ
В основу дисциплины «Функциональное и логическое программирование» положены следующие принципы:
- дисциплина входит в число дисциплин, включенных в учебный план на основании Государственного образовательного стандарта высшего профессионального образования по направлению 230– «Информатика и вычислительная техника»;
- основной целью дисциплины является формирование и закрепление системного подхода при разработке программ с применением языков логического и функционального программирования, в дисциплине рассматриваются средства и методы создания таких программ;
- ядро дисциплины составляют средства и приемы создания программ с использованием языков логического и функционального программирования;
- для успешного изучения дисциплины студенту необходимо знать основы математической логики;
- в дисциплине выделены две родственные составляющие: логическое программирование и функциональное программирование, соответственно рассматриваются средства и методы создания программ для каждой составляющей;
- в дисциплине закрепляются такие общепредметные умения, как выбор язык программирования для решения поставленной задачи, выбор способа представления исходных данных и выбор метода решения поставленной задачи;
- дисциплина имеет практическую часть (лабораторные работы ‑ 17 часов и курсовое проектирование ‑ 5 семестр). Студенты применяют теоретические знания для создания программ с использованием логического и функционального стилей программирования. Задания для лабораторных занятий и курсового проектирования имеют проблемный характер, наиболее типичный для задач, решаемых методами и средствами логического и функционального стилей программирования;
- для проведения лабораторных занятий и курсового проектирования используются методические указания;
- оценка знаний и умений студентов проводится с помощью экзамена в 5 семестре и государственного экзамена в 8 семестре, экзаменационные вопросы охватывают основные проблемы дисциплины.
3. ЦЕЛИ учебной дисциплины
После изучения дисциплины студент будет
№ цели | Содержание цели |
иметь представление: | |
1 | о множестве задач, решаемых с применением логического и функционального подходов к программированию, и о методах их решения с использованием языков логического и функционального программирования, о разделах дисциплины «Функциональное и логическое программирование», ее структуре; |
2 | о месте и роли, о состоянии развития современных логических и функциональных языков, о проблемах и направлениях развития этого раздела программирования; |
3 | о различиях в подходах к решению задач логического и функционального программирования, о вопросах представления данных для решения задач логического и функционального программирования, о приемах разработки программ с применением языков логического и функционального программирования; |
4 | о проблемах и направлениях развития современных программных средств логического и функционального программирования, об основных методах и средствах автоматизации проектирования, используемых в программных средствах; |
5 | об основах построения сложных программ. |
знать: | |
6 | объект дисциплины (системы разработки программ с использованием языков логического и функционального программирования), предмет дисциплины (методы программирования с использованием языков логического и функционального программирования), задачи дисциплины (разработка программ с применением языков логического и функционального программирования); |
7 | проблематику дисциплины «Функциональное и логическое программирование» и ее основные разделы; |
8 | базовые понятия и определения, используемые в логическом и функциональном программировании; |
9 | методы и уровни представления данных, способы обработки и хранения данных; |
10 | основы технологии программирования в программных средствах, используемых в современных языках логического и функционального программирования. |
уметь: | |
11 | ориентироваться в современных языках логического и функционального программирования, их возможностях; |
12 | обосновать выбор языка (языка логического или функционального программирования) для решения конкретных задач; |
13 | обосновать выбор представление данных для решения поставленной задачи; |
14 | обосновать выбор методов обработки данных для решения поставленной задачи; |
15 | разрабатывать и тестировать программы с применением программных средств, используемых в современных языках логического или функционального программирования; |
16 | использовать специальную литературу в изучаемой предметной области. |
4. СОДЕРЖАНИЕ И Структура УЧЕБНОЙ ДИСЦИПЛИНЫ
Содержание учебной дисциплины:
Ссылки на цели | Часы | Темы лекционных занятий |
1, 2, 3, 11 | 2 | Функциональное и логическое программирование как научная дисциплина. Структура дисциплины. Ее связь с другими дисциплинами учебного плана. Особенности предмета дисциплины. Понятие декларативного программирования. Логическая программа: основные конструкции, операционная и декларативная семантика, интерпретация, корректность. |
1, 2, 3, 11 | 2 | Общие сведения о языках логического программирования. Constraint–Пролог: операционная семантика. Области применения языка логического программирования PROLOG. Основные элементы языка. Предикаты. Арность предикатов. Металогические предикаты. Внелогические предикаты; Предложения: факты и правила. Переменные. Анонимные переменные. Оформление комментариев. Запросы. Цели. |
7, 8, 9, 10 | 2 | Простые объекты данных. Согласование целевых утверждений. Сопоставление и унификация. Равенство и предикат равенства. Основные секции программы. Основные стандартные домены. Объявление нестандартных доменов. Детерминизм. |
7, 8, 9, 10 | 2 | Методы поиска. Недетерминированное программирование. Обработка нечетких данных. Основные принципы поиска с возвратом. Поиск всех решений. Стандартный предикат fail. Прерывание поиска с возвратом – отсечение (стандартный предикат!). Способы использования отсечения. «Зеленое» и «красное» отсечения. |
7, 8, 9, 10 | 2 | Использование поиска с возвратом в детерминированных предложениях. Отладка программ. Стандартные предикаты ввода и вывода. Арифметические вычисления. |
7, 8, 9, 10 | 2 | Составные объекты данных. Функторы. Многоуровневые составные объекты данных. Вычислительная модель; анализ структуры термов. Объявление составных объектов данных. Использование предиката равенства для унификации составных объектов. |
7, 8, 9, 10 | 2 | Рекурсивное программирование. Достоинства и недостатки рекурсии. Хвостовая рекурсия. Способы задания хвостовой рекурсии. |
7, 8, 9, 10 | 2 | Рекурсивные структуры данных – списки. Объявление списков. Составные списки. Голова и хвост списка. Примеры работы со списками. |
7, 8, 9, 10 | 2 | Рекурсивные структуры данных – деревья. Объявление деревьев. Упорядоченные и неупорядоченные деревья. Бинарные поисковые деревья. Способы обхода дерева. Создание дерева. Создание дерева с сохранением упорядоченности. |
7, 8, 9, 10 | 2 | Программирование баз данных Динамические базы данных. Программная секция базы данных. Объявление динамической базы данных. Добавление и удаление фактов в динамическую базу данных во время выполнения программы. Сохранение фактов в файле во время выполнения программы. Загрузка фактов из файла во время выполнения программы. |
7, 8, 9, 10 | 2 | Обработка строк. Стандартные предикаты для работы со строками. Анализ потока параметров. Контроль потока параметров. |
7, 8, 9, 10 | 2 | Файлы. Работа с текстовыми и бинарными файлами. Открытие и закрытие файлов. Стандартные предикаты для работы с файлами. |
7, 8, 9, 10 | 2 | Стандартный предикат not. Контроль конца файла. Расширение динамической базы данных с помощью файлов. Работа с фактами динамической базы данных, как с термами. Работа с клавиатурой. Чтение и распознавание клавиш. |
7, 8, 9, 10 | 2 | Составные структуры данных – графы. Представление графов. Действия с графами. Ориентированные и неориентированные графы. Поиск ациклического пути в графе. |
7, 8, 9, 10 | 2 | Действия с графами. Поиск Гамильтонова пути в графе. Построение остовного дерева графа. |
5 | 2 | Стиль программирования на языке PROLOG. Язык PROLOG с процедурной точки зрения. Представление фактов и правил в виде процедур. Использование правил для организации ветвления. Отсечение как оператор безусловного перехода. |
5 | 2 | Модульное программирование. Проекты. Примеры использования языка логического программирования PROLOG для решения задач искусственного интеллекта. Неполные структуры данных. Программирование второго порядка. |
1, 2, 3, 11 | 2 | Общие сведения о языках функционального программирования. Соответствие между функциональными и императивными программами. Функциональные языки, строго функциональный язык. Конкретные реализации языков функционального программирования. Области применения языка функционального программирования LISP. Основы языка: рекурсивные функции и лямбда-исчисление А. Черча. |
7, 8, 9, 10 | 2 | Основные особенности языка LISP. Элементарные понятия. Символьные выражения: атомы и списки. Функции. Инфиксная и префиксная нотация. Программирование в функциональных обозначениях. |
7, 8, 9, 10 | 2 | Приемы программирования; представление и интерпретация функциональных программ. Базовые функции. Предикаты. Псевдофункции. Определение функций. Задание параметров функции в лямбда-списке. Передача параметров и область их действия. Отладка программ. |
7, 8, 9, 10 | 2 | Вычисления в языке LISP. Управляющие структуры языка LISP. Работа с контекстом. |
7, 8, 9, 10 | 2 | Предложения. Локальное присваивание. Последовательное исполнение. Ветвление вычислений. Условное предложение. |
7, 8, 9, 10 | 2 | Циклические вычисления. Внутреннее представление списков. Вычисления, изменяющие и не изменяющие структуру выражений. Свойства символа. |
7, 8, 9, 10 | 2 | Простая рекурсия. Рекурсия по значению. Рекурсия по аргументу. Параллельная рекурсия. Взаимная рекурсия. |
7, 8, 9, 10 | 2 | Рекурсия более высокого порядка. Функциональные аргументы. Функциональное значение функции. Применяющие функционалы. Отображающие функционалы. Массивы. Макросы. |
4, 11, 12 | 1 | Обзор основных вопросов, рассмотренных в дисциплине. Перспективы дальнейшего развития теории и практики функционального и логического программирования, применения функционального программирования, применение логического программирования в задачах искусственного интеллекта. |
Ссылки на цели | Часы | Темы лабораторных занятий | Учебная деятельность |
13, 14, 15, 16 | 4 | Знакомство с основами языка логического программирования PROLOG. | - изучает возможности программной оболочки; - использует способы представления данных в виде фактов и правил вывода для записи программы на языке PROLOG; - используя возможности, предоставляемые программной оболочкой, проверяет правильность работы созданной программы; - оформляет результаты работы программы; - оценивает полученные результаты. |
13, 14, 15, 16 | 4 | Разработка программ, использующих для нахождения решений рекурсию и поиск с возвратом. | - использует способы представления данных в виде фактов и правил вывода для записи программы на языке PROLOG; - проверяет правильность работы созданной программы; - исследует различия в двух методах нахождения решений: рекурсии и поиске с возвратом; - оформляет результаты работы программы; - оценивает полученные результаты. |
13, 14, 15, 16 | 4 | Разработка программ для работы с рекурсивными структурами данных (списками и деревьями) | - использует способы представления данных в виде фактов и правил вывода для записи программы на языке PROLOG; - проверяет правильность работы созданной программы; - исследует методы работы с рекурсивными структурами данных (списками и деревьями); - оформляет результаты работы программы; - оценивает полученные результаты. |
13, 14, 15, 16 | 4 | Знакомство с основами языка функционального программирования LISP. | - использует способы представления данных в виде функций для записи программы на языке LISP; - проверяет правильность работы созданной программы; - оформляет результаты работы программы; - оценивает полученные результаты. |
Структура учебной дисциплины:
5. УЧЕБНАЯ ДЕЯТЕЛЬНОСТЬ
В течение семестра студентами выполняется курсовой проект. В рамках курсового проекта студентам предлагается реализовать программу с использованием языка логического или функционального программирования, в ходе курсового проектирования студенты разрабатывают программу на языке логического или функционального программирования, проверяют правильность работы программы, оценивают полученные результаты, оформляют пояснительную записку.
Цель курсового проектирования – обобщить и структурировать знания, полученные в рамках дисциплины «Функциональное и логическое программирование», научить студентов разрабатывать и отлаживать программы с использованием языков логического или функционального программирования.
Образец задания:
Разработать программу для работы с бинарными упорядоченными деревьями. Реализовать следующие функции: создание дерева, загрузку дерева из файла, сохранение дерева в файле, добавление вершины с сохранением упорядоченности, удаление вершины, все виды обхода дерева, просмотр дерева в традиционном представлении (корень вверху, листьевые вершины внизу.)
Требования к оформлению пояснительной записки:
Пояснительная записка к курсовому проекту должна содержать: титульный лист, задание на курсовой проект, назначение программного продукта, описание данных, описание методов решения, описание разработанного программного продукта, описание пользовательского интерфейса, список использованной литературы и/или адресов www, приложение – исходные тексты с комментариями.
6. ПРАВИЛА АТТЕСТАЦИИ СТУДЕНТОВ ПО УЧЕБНОЙ ДИСЦИПЛИНЕ
По окончании учебной дисциплины проводится устный экзамен. Экзаменационный билет включает два теоретических вопроса и одну практическую задачу.
Для получения оценки «отлично» требуется правильно (75-100%) ответить на теоретические вопросы экзаменационного билета и дополнительные вопросы, правильно решить практическую задачу.
Для получения оценки «хорошо» требуется правильно (50-75%) ответить на теоретические вопросы экзаменационного билета и дополнительные вопросы, правильно решить практическую задачу.
Для получения оценки «удовлетворительно» требуется правильно (не менее 50%) ответить на теоретические вопросы экзаменационного билета и дополнительные вопросы, правильно решить практическую задачу.
7. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
Основная литература:
1. Адаменко А. Н., Кучуков программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003. – 992 С.
2. Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: Мир, 1990. – 560 С.
3. Ин Ц., Соломон Д. Использование Турбо-Пролога. – М.: Мир, 1993. – 608 С.
4. Клоксин У., Меллиш Д. Программирование на языке Пролог. – М.: Мир, 1987. – 336 С.
5. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. – М.: Мир, 1990. – 235 С.
6. Доорс Дж. и др., Рейблейн А. Р., Вадера С. Пролог ‑ язык программирования будущего. – М.: ФиС, 1990. – 144 С.
7. Стобо Дж. Язык программирования Пролог. – М.: Мир, 1993. – 368 С.
8. Хювёнен Э., Сеппянен Й. Мир Лиспа. ‑ М.: Мир, 1990. – 447 С.
9. Хендерсон П. Функциональное программирование: применение и реализация. ‑ М.: Мир, 1983. – 349 С.
Дополнительная литература:
10. Новицкая логического и функционального программирования (учебное пособие). – http://ermak. cs. *****/flp/
11. Сырецкий . Часть III. Основы логического программирования на PDC Prolog (учебное пособие). – Новосибирск: НГТУ, 1994. – 93 С.
12. Малпас Дж. Реляционный язык Пролог и его применение. – М.: Наука, 1990. – 463 С.
13. Янсон А. Турбо-Пролог в сжатом изложении. – М.: Мир, 1991. – 94 С.
14. Маурер У. Введение в программирование на языке ЛИСП. – М.: Мир, 1978. – 104 С.
8. КОНТРОЛИРУЮЩИЕ МАТЕРИАЛЫ ДЛЯ АТТЕСТАЦИИ СТУДЕНТОВ ПО ДИСЦИПЛИНЕ
Список экзаменационных вопросов:
1. Сравнительная характеристика декларативных и процедурных языков программирования. Языки PROLOG и LISP как языки декларативного и функционального программирования. Основные отличия, области применения.
2. Предикаты. Предложения: факты и правила.
3. Запросы (цели). Переменные.
4. Основные секции программы.
5. Основные стандартные домены.
6. Сопоставление и унификация. Предикат равенства.
7. Основные принципы поиска с возвратом.
8. Управление поиском решений (предикат fail).
9. Управление поиском решений (предикат!).
10. Управление поиском решений (динамическое отсечение).
11. Детерминизм.
12. Анализ и контроль потока параметров.
13. Простые объекты данных. Составные объекты данных.
14. Многоуровневые составные объекты данных.
15. Аргументы множественных типов.
16. Предикат repeat.
17. Рекурсия.
18. Хвостовая рекурсия.
19. Деревья: объявление и обход.
20. Списки: объявление и примеры работы.
21. Составные списки: объявление и примеры работы.
22. Динамические базы данных: объявление и использование.
23. Динамические базы данных: загрузка и сохранение фактов.
24. Динамические базы данных: добавление и удаление фактов.
25. Стандартные предикаты ввода и вывода.
26. Работа со строками.
27. Работа с файлами: чтение и запись.
28. Графы: представление графов.
29. Графы: действия над графами.
30. Обработка ошибок и исключительных ситуаций.
31. Основы языка LISP. Лямбда-выражение и лямбда-вызов.
32. Символьные выражения: атомы и списки.
33. Функции, определение функций. Параметры функции: передача и область действия.
34. Базовые функции. Списки: работа со списками.
35. Управляющие структуры.
36. Структуроразрушающие функции.
37. Внутреннее представление списков. Точечная пара.
38. Свойства символа. Действия со списком свойств символа.
39. Простая рекурсия. Рекурсия по значению и рекурсия по аргументу.
40. Параллельная рекурсия. Взаимная рекурсия.
41. Рекурсия более высокого порядка
42. Применяющие функционалы.
43. Отображающие функционалы.
44. Ассоциативные списки.
Примеры экзаменационных задач:
1. Написать программу для вычисления xn только с помощью умножения (построить дерево целей).
2. Написать программу для циклического сдвига списка на n элементов влево (построить дерево целей).
3. Имеется база данных, содержащая факты numbers(n1, n2), где n1 и n2 – целые числа. Написать программу для удаления всех фактов, где n1=n2.
4. Написать программу для перевода списка чисел, записанных с использованием римских цифр, в список чисел, записанных с использованием арабских цифр. Использовать факты вида trans(“I”, 1).
5. Написать программу для нахождения числа вершин с положительными значениями в дереве целых (построить дерево целей).
