Департамент образования города Москвы
Государственное бюджетное образовательное учреждение
высшего профессионального образования города Москвы
«Московский городской педагогический университет»
Институт математики и информатики
Кафедра информационных систем и технологий
ПРОГРАММА
«АЛГОРИТМИЗАЦИЯ И ЯЗЫКИ ПРОГРАММИРОВАНИЯ»
По направлению 230400 «Информационные системы и технологии »
Профиль подготовки «Информационные технологии в образовании»
Квалификация (степень) – «Бакалавр»
Форма обучения - очная
Курс 1
Семестр 1
Москва
2013
Программа составлена в соответствии с требованиями Федерального государственного образовательного стандарта высшего профессионального образования по направлению подготовки 230400 Информационные системы и технологии (квалификация (степень) "бакалавр")
Авторы:
доцент кафедры информационных систем и технологий Института математики и информатики, к. т.н., доцент ;
доцент кафедры информационных систем и технологий Института математики и информатики, к. т.н.
Рецензенты:
доцент кафедры информационных систем и технологий Института математики и информатики МГПУ, к. т.н., доцент Красильников кафедры информационных компьютерных технологий РХТУ им. , д. т.н., профессор
Программа одобрена на заседании кафедры информационных систем и технологий (протокол №___от «__»________2013 г.)
Заведующий кафедрой
информационных систем и технологий
1. Цели и задачи освоения дисциплины
Целью дисциплины является изучение студентами основ алгоритмизации и обучение навыкам программирования с целью решения задач на современных ЭВМ.
Основной задачей дисциплины является освоение теоретических основ алгоритмизации задач, практических приемов программирования на алгоритмических языках высокого уровня, а также основ организации вычислительного процесса в ЭВМ, включая проектирование программ. Проведение практических и лабораторных занятий базируется на требовании написания законченных программ.
2. Место дисциплины в структуре ООП
«Алгоритмизация и языки программирования» относится к профессиональному циклу Б.3, вариативная часть. Изучение данной дисциплины осуществляется одновременно с дисциплиной «Информатика».
Дисциплина «Алгоритмизация и языки программирования» является предшествующей для дисциплин «Web-технологии», «Технологии обработки информации», «Мультимедиа технологии в образовании», «Дистанционные технологии в образовании», «Информационные технологии».
3. Требования к результатам освоения дисциплины:
Процесс изучения дисциплины направлен на формирование следующих компетенций:
ПК-12, ПК-18, ПК-22, ПК-25, ПК-31, ПК-33.
В результате освоения дисциплины студент должен демонстрировать следующие результаты образования:
знать | методы структурного программирования, понятие данных |
уметь | разрабатывать и отлаживать эффективные алгоритмы и программы с использованием современных технологий программирования |
владеть | навыками программирования в современных средах |
4. Объем дисциплины и виды учебной работы
Вид учебной работы | Всего часов/ зачетных единиц | Семестры |
Аудиторные занятия (всего) | 108/3 | 1 |
В том числе: | ||
Лекции | 54 | |
Практические занятия (ПЗ) | ||
Семинары (С) | ||
Лабораторные работы (ЛР) | 54 | |
Самостоятельная работа (всего) | 108 | |
В том числе: | ||
Указываются виды самостоятельной работы | ||
подготовка к лекциям, семинарам, лабораторным работам, зачетам, экзаменам, выполнение рефератов, заданий, курсовых работ и проектов | 108 | |
Вид промежуточной аттестации (зачет, экзамен) | Экзамен | 36 |
Общая трудоемкость часы зачетные единицы | 252 | |
7 |
5. Структура и содержание дисциплины
5.1. Разделы дисциплин и виды занятий
№ п/п | Наименование раздела дисциплины | Лекции | Практические занятия | Лабораторные занятия | Семинары | СРС | Всего |
1 | Основные принципы алгоритмизации и программирования | 6 | 0 | 6 | 0 | 12 | 24 |
2 | Программирование на алгоритмическом языке | 6 | 0 | 8 | 0 | 16 | 30 |
3 | Программирование в объектно-ориентированной среде | 8 | 0 | 8 | 0 | 16 | 32 |
4 | Парадигмы функционального и логического программирования. | 6 | 0 | 6 | 0 | 12 | 24 |
5 | Математические основы логического программирования. | 6 | 0 | 6 | 0 | 12 | 24 |
6 | Язык логического программирования Пролог. | 8 | 0 | 6 | 0 | 12 | 26 |
7 | Математические основы функционального программирования. | 6 | 0 | 6 | 0 | 14 | 26 |
8 | Язык функционального программирования ЛИСП. | 8 | 0 | 8 | 0 | 14 | 30 |
Экзамен | 0 | 0 | 0 | 0 | 36 | 36 | |
Итого: | 54 | 54 | 144 | 252 |
5.2. Содержание разделов дисциплины
№ п/п | Наименование раздела дисциплины | Содержание раздела |
1 | Основные принципы алгоритмизации и программирования | Основные понятия алгоритмизации, логические основы алгоритмизации. Языки и системы программирования. Методы программирования |
2 | Программирование на алгоритмическом языке | Основные элементы языка. Операторы языка. Массивы, строки и множества. Процедуры и функции. Организация ввода и вывода данных. Работы с файлами. Записи. Библиотеки подпрограмм |
3 | Программирование в объектно-ориентированной среде | Основы объектно-ориентированного программирования. Интегрированная среда разработчика, этапы разработки приложения. Иерархия классов. Визуальное событийно-управляемое программирование. Разработка оконного приложения |
4 | Парадигмы функционального и логического программирования. | Логическое и функциональное программирование как альтернатива императивному программированию. Связь логического и функционального программирования с искусственным интеллектом. Классификация моделей представления знаний. Понятие о логической модели представления знаний. |
5 | Математические основы логического программирования. | Использование логики предикатов первого порядка в задачах искусственного интеллекта. Автоматическое доказательство теорем. Метод резолюции в исчислении предикатов. Подстановки и унификация. Хорновские дизъюнкты. Вывод пустого дизъюнкта методом резолюции. Понятие о логическом программировании. Логическая программа как модель предметной области на языке хорновских дизъюнктов. |
6 | Язык логического программирования Пролог | Основные понятия языка Пролог. Обзор версий Пролога. Интерпретаторы и компиляторы языка Пролог. Система программирования PDC Prolog. Отличия языка PDC Prolog от стандарта ANSI языка Пролог. Структура программы на языке PDC Prolog. Синтаксическая структура программы. Термы и утверждения. Синтаксис фактов, правил и запросов. Декларативная и процедурная семантика Пролог - программы. Унификация термов. Общая схема согласования целевых утверждений. Редукция цели. Дерево поиска решений. Поиск с возвратом и механизм бэктрекинга. Управление процессом выполнения Пролог-программ (управление возвратной стратегией, отсечение альтернатив). Встроенные предикаты Пролога. Программирование арифметических операций. Организация ввода/вывода в Пролог-программах. Рекурсия. Определение рекурсивных правил. Общая схема поиска решений в рекурсивной программе. Представление списков в языке Пролог. Обработка списков с помощью рекурсивных программ. |
7 | Математические основы функционального программирования. | Сравнение языков искусственного интеллекта ЛИСП и Пролог по их возможностям. Особенности языка ЛИСП. Лямбда – исчисление – основа языка ЛИСП |
8 | Язык функционального программирования ЛИСП | Сравнение языков искусственного интеллекта ЛИСП и Пролог по их возможностям. Особенности языка ЛИСП. Основные элементы языка: атомы, выражения, списки, стандартные функции. Определение функций в языке ЛИСП. Математическая логика в языке ЛИСП и предикаты. Рекурсия. Интерпретатор muLisp и работа с ним. |
5.3. Компетенции обучающегося, формируемые в процессе освоения дисциплины (модуля)
Темы, разделы (модули) дисциплины | Количество часов | Формируемые компетенции | Общее количество компетенций | |||
Основные принципы алгоритмизации и программирования | 24 | ПК-25 | ПК-33 | 3 | ||
Программирование на алгоритмическом языке | 30 | ПК-12 | ПК-22 | ПК-31 | 3 | |
Программирование в объектно-ориентированной среде | 32 | ПК-12 | ПК-18 | ПК-31 | ПК-33 | 4 |
Парадигмы функционального и логического программирования | 24 | ПК-22 | ПК-25 | 2 | ||
Математические основы логического программирования | 24 | ПК-22 | ПК-25 | 2 | ||
Язык логического программирования Пролог | 26 | ПК-12 | ПК-18 | ПК-31 | 3 | |
Математические основы функционального программирования. | 26 | ПК-22 | ПК-33 | 2 | ||
Язык функционального программирования ЛИСП | 30 | ПК-18 | ПК-25 | ПК-31 | 3 |
6. Образовательные технологии и планы групповых занятий
Занятие 1. Тема: Основные принципы алгоритмизации и программирования
Составить блок-схему алгоритмов
Составить таблицы истинности
История развития языков программирования
Методы программирования
Занятие 2. Тема: Программирование на алгоритмическом языке
Составить программу линейной структуры
Составить программу разветвленной структуры
Составить программу разветвляющейся усложненной структуры
Составить программу циклической структуры
Составить программу усложненной структуры
Составить программу с одномерными массивами
Составить программу с двумерными массивами
Использовать стандартные функций для работы с массивами
Составить программы со строковыми переменными
Составить программы с данными типа множество
Разработать усложненные программы со структурированными типами данных
Составить программы с процедурами и функциями
Использовать рекурсивные функции
Разработать программу с чтением и записью файлов разных типов
Создать библиотеки подпрограмм
Занятие 3. Тема: Программирование в объектно-ориентированной среде
Создать простой проект
Разработать многооконное приложение
Занятие 4. Тема: Простейшая программа на языке Пролог. Запросы с переменными. Установление истинности факта. Поиск ответа на запрос.
План.
1) Описать с помощью фактов 4-уровневовое генеалогическое дерево в Пролог-программе “Родственники”, включающей предикаты parent и person.
2) Написать правила, определяющие следующие отношения:
- “X является отцом Y” . “X является бабушкой Y” . “X является сестрой Y” . “X является племянником Y” . “X является племянницей Y” . “X является родителем родителя Y” . “X является прадедушкой Y” . “X является двоюродным братом Y” .
3) Отладить программу с помощью системы программирования PDC Prolog.
4) Продемонстрировать работу программы с помощью вопросов.
Занятие 5. Тема: Арифметические предикаты Пролога. Вычисление значения выражения в зависимости от условия.
План.
Написать программу на Прологе по индивидуальному заданию.2) Отладить программу с помощью системы программирования PDC Prolog.
Продемонстрировать работу программы с помощью вопросов.Занятие 6. Тема: Встроенные предикаты управления процессом выполнения запроса. Управление возвратной стратегией, предикат fail, Отсечение альтернатив, предикат cut (!). Организация циклических процессов.
План.
1) Создать базу данных “Сессия” на языке Пролог, которая содержит факты, описывающие отношения двух типов:
- lector(<фамилия>,<дисциплина>,<номер группы>,<дата экзамена> student(<фамилия>,<номер группы>,<номер зачетки>)
- Выдать на экран фамилии всех студентов, которые сдают экзамен определенного числа, дата задается следующим образом: ‘хх. хх. xxxx’. Например, ’10.01.2001’. Выдать на экран фамилии всех студентов, которые сдают экзамен определенному лектору. Выдать на экран названия дисциплин, по которым будет сдавать экзамен определенный студент. Выдать на экран фамилии преподавателей, которые принимают экзамены в данной группе. Выдать на экран фамилии всех студентов, которые учатся в данной группе. Выдать на экран названия дисциплин, по которым принимает экзамен данный преподаватель.
Занятие 7. Тема: Рекурсия. Простейшие рекурсивные программы.
План.
1) Написать программу на Прологе по индивидуальному заданию.
2) Отладить программу с помощью системы программирования PDC Prolog.
3) Продемонстрировать работу программы с помощью вопросов.
Занятие 8. Тема: Рекурсивная обработка списков. Представление и обработка множеств в Пролог - программах. Представление и обработка графов и деревьев.
План.
Написать программу на Прологе по индивидуальному заданию. Отладить программу с помощью системы программирования PDC Prolog. Продемонстрировать работу программы с помощью вопросов.Занятие 9. Тема: Создание динамических баз данных в оперативной и внешней памяти ЭВМ. Разработка программы обработки баз данных и использованием средств работы с окнами экрана для построения интерфейса пользователя.
План.
Написать программу на Прологе по индивидуальному заданию. Отладить программу с помощью системы программирования PDC Prolog. Продемонстрировать работу программы с помощью вопросов.Занятие 10. Тема: Разработка экспертной системы на языке Пролог.
План.
Написать программу на Прологе по индивидуальному заданию. Отладить программу с помощью системы программирования PDC Prolog. Продемонстрировать работу программы с помощью вопросов.Занятие 11. Тема: Освоение работы в среде muLisp. Разработка программы обработки списков на языке Лисп.
План.
Ознакомится с принципами работы в среде muLISP. Написать программу на языке ЛИСП по индивидуальному заданию. Отладить программу с помощью системы программирования muLISP. Продемонстрировать работу программы.7. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов
Примерный перечень вопросов к экзамену
Что такое логическое программирование? Особенности языка Пролог. Исчисление предикатов. Понятие n-местного предиката. Представление предиката на языке Пролог. Определение хорновского дизъюнкта. Основные элементы языка Пролог. Алфавит. Логические термы. Предложения в языке Пролог. Факты. Правила. Логическая программа как модель предметной области. Простые запросы. Синтаксис фактов в Пролог - программах. Вопросы. Подстановки и примеры. Синтаксис правил в языке Пролог. Декларативная и процедурная семантика Пролог-программ. Логические термы. Унификация термов. Общие правила. Общая схема согласования целевых утверждений. Редукция цели. Дерево поиска решения. Механизм поиска решения с возвратом. Управление поиском: использование предиката fail. Управление поиском: использование предиката cut. Структура меню интегрированной среды логического программирования PDC Prolog. Основные команды. Структура программы на языке PDC Prolog. Программные секции. Элементы программы (имена, константы, переменные, структуры). Пример простой программы. Числа в языке Пролог. Арифметические операции над ними. Операции сравнения. Стандартные математические предикаты языка Пролог. Рекурсия. Общая схема рекурсивной программы. Схема поиска решений в рекурсивной программе. Примеры рекурсивных программ. Процедура определения наибольшего общего делителя двух целых чисел и ее программа на Прологе. Процедура определения n-го члена ряда Фиббоначи и ее программа на Прологе. Рекурсивные структуры данных. Представление списка в языке Пролог. Унификация списков. Типовые предикаты для обработки списков. Конкатенация списков. Добавление элемента в начало списка. Определение длины списка. Удаление первого вхождения элемента из списка. Удаление всех вхождений элемента из списка. Процедура определения принадлежности элемента списку, первого и последнего элемента списка. Процедура обращения списка. Представление множеств в языке Пролог с помощью списков. Процедура subset, определяющая является ли множество подмножеством другого множества. Определение равенства множеств. Операции с множествами (объединение, пересечение, разность, декартово произведение) и их программы на Прологе. Основные методы сортировки списков. Пролог-программа сортировки иска методом прямого выбора. Сортировка списка методом вставки. Сортировка списка термов методом перестановки. Стандартные предикаты для работы со строками. Стандартные предикаты ввода – вывода термов и литер. Стандартные предикаты для программирования пользовательского интерфейса, организации экранных окон, управления цветом. Работа с базами данных в языке PDC Prolog. Создание динамических баз данных. Обработка строк в языке PDC Prolog. Принципы построения экспертных систем (ЭС). Использование языка Пролог для разработки ЭС. Классификация ЭС. Общая структура ЭС. Требования к системе пользовательского интерфейса ЭС. Функции механизма вывода ЭС. Представление знаний В ЭС. ЭС, базирующие на правилах. Пример ЭС. Организация база знаний в ЭС, базирующейся на логике. Пример ЭС. Этапы разработки ЭС. Рекомендации по выбору типа ЭС. Особенности языка ЛИСП. Основные элементы языка: атомы, выражения, списки, стандартные функции. Определение функций в языке ЛИСП. Математическая логика в языке ЛИСП и предикаты. Рекурсия в языке ЛИСП. Интерпретатор muLisp и работа с ним.Критерий оценки знаний на экзамене:
Отлично – студент свободно владеет материалом, умеет применять теоретические сведения к решению задач, в том числе нестандартных, имеет уверенные навыки решений примеров и задач.
Хорошо – студент свободно владеет материалом, умеет применять теоретические сведения к решению задач, имеет навыки решений примеров и задач.
Удовлетворительно – студент владеет материалом, имеет навыки решений стандартных примеров и задач.
Примерный перечень контрольных вопросов и заданий для самостоятельной работы
Составить блок-схему алгоритмов Составить таблицы истинности История развития языков программирования Методы программирования Составить программу линейной структуры Составить программу разветвленной структуры Составить программу разветвляющейся усложненной структуры Составить программу циклической структуры Составить программу усложненной структуры Составить программу с одномерными массивами Составить программу с двумерными массивами Использовать стандартные функций для работы с массивами Составить программы со строковыми переменными Составить программы с данными типа множество Разработать усложненные программы со структурированными типами данных Составить программы с процедурами и функциями Использовать рекурсивные функции Разработать программу с чтением и записью файлов разных типов Создать библиотеки подпрограмм Создать простой проект Разработать многооконное приложение8. Учебно-методическое и информационное обеспечение дисциплины (модуля):
а) основная литература
Ашарина -ориентированное программирование в С++: лекции и упражнения : учеб. пособие / . - [б. м.] : Горячая линия - Телеком, 2008. - 320 с. Подбельский С++: учеб. пособие/. – 5-е изд. – М.: Финансы и статистика, 2008. – 560 с.: ил.б) дополнительная литература
Кнут скусство программирования. Т. 1. Основные алгоритмы: Уч. пос. - М.: Издательский дом «Вильямс», 2000. — 720 с. Кнут скусство программирования. Т. 3. Сортировка и поиск: Уч. пос. - М.: Издательский дом «Вильямс», 2005.-832 с. Кнут скусство программирования. Т. 2. Получисленные алгоритмы: Уч. пос. - М.: Издательский дом «Вильямс», 2000.-832 с. Прохорова вычислительных процессов и структур. Учебное пособие. Йошкар – Ола: Мар. ГТУ, 2001.- 108 с.В процессе обучения применяются компьютерные технологии, основанные на операционных системах Windows, Linux.
г) базы данных, информационно-справочные и поисковые системы
Интернет-ресурсы (сайты образовательных учреждений, ведомств, журналов, информационно-справочные системы, электронные учебники), которые ввиду их глобального распространения становятся на сегодняшний день обязательной компонентой стандартов образования.
http://www. – Сайт по технологии программирования на С и С++.
9. Материально-техническое обеспечение дисциплины:
Интерактивное оборудование (компьютеры, мультимедийный проектор, интерактивный экран)
