ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
Тихоокеанский государственный университет
Утверждаю Проректор по учебной работе ______________ “_____” ________________200_ г. |
Программа дисциплины
по кафедре Автоматика и системотехника
Программирование
Утверждена научно-методическим советом университета для направлений
подготовки (специальностей) в области автоматики и управления,
информатики и вычислительной техники
для специальностей 220201.65 - "Управление и информатика
в технических системах" и 230201.65 - "Информационные системы
и технологии"
Хабаровск 2007 г
Программа разработана в соответствии с требованиями государственного образовательного стандарта, предъявляемыми к минимуму содержания дисциплины и в соответствии с примерной программой дисциплины, утвержденной департаментом образовательных программ и стандартов профессионального образования с учетом особенностей региона и условий организации учебного процесса Тихоокеанского государственного технического университета.
Программу составила:
Епанешникова . тех. наук,
доцент кафедры
Автоматика и системотехника
Программа рассмотрена и утверждена на заседании кафедры протокол № ______ от «____»__________________ 200__г | |
Завкафедрой__________«__»______ 200_г | ________________ |
Подпись дата | Ф. И.О. |
Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию протокол № ______ от «____»_____________ 200__г | |
Председатель УМК ______«__»_______ 200__г | _________________ |
Подпись дата | Ф. И.О. |
Директор института ______«__»_______ 200__г | __________________ |
(декан факультета) Подпись дата | Ф. И.О. |
Цели и задачи изучаемой дисциплины
Целью курса является изучение основных программных методов и алгоритмов, ознакомление с их принципами работы и получение навыков их использования при создании программ.
Требования к уровню освоения содержания дисциплины
В результате изучения дисциплины студент должен иметь представление об основных методах и алгоритмах, используемых в программировании.
Знать:
- основные типы данных, сложные структуры данных
- основные алгоритмы, используемые в программировании
- способы конструирования программ
- особенности применения различных методов и алгоритмов при решении задач.
Объём дисциплины и виды учебной работы
Таблица 1 – объем дисциплины и виды учебной работы
Наименование | По учебным планам основной траектории обучения | |
С максимальной трудоемкостью (ИС) | С минимальной трудоемкостью (УИТС) | |
Общая трудоёмкость дисциплины | ||
по ГОС | 102 | 130 |
по УП | 153 | 136 |
Изучается в семестрах | 2 | 2 |
Вид итогового контроля по семестрам | ||
зачет | 2 | 2 |
экзамен | 2 | 2 |
Курсовой проект (КП) | ||
Курсовая работа (КР) | ||
Вид итогового контроля самостоятельной работы без отчетностей расчетно-графические работы (РГР) | 2 | 2 |
Реферат (РФ) | ||
Домашние задания (ДЗ) | ||
Аудиторные занятия: | ||
всего | 68 | 68 |
В том числе: лекции (Л) | 34 | 34 |
Лабораторные работы (ЛР) | 34 | 34 |
Практические занятия (ПЗ) | ||
Самостоятельная работа | ||
общий объем часов (С2) | 85 | 68 |
В том числе на подготовку к лекциям | 17 | 17 |
на подготовку к лабораторным работам | 17 | 17 |
на подготовку к практическим занятиям | ||
на выполнение КП | ||
на выполнение КР | ||
На выполнение РГР | 51 | 34 |
на написание РФ | ||
на выполнение ДЗ | ||
на экзаменационную сессию |
Содержание дисциплины
Таблица 2 – Разделы дисциплины и виды занятий и работ
№ | Раздел дисциплины | Л | ЛР | ПЗ | КП (КР) | РГР | ДЗ | РФ | С2 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1. | Основные виды и этапы программирования | * | * | ||||||
2. | Типизация и структуризация программных данных Статические и динамические данные. Динамические массивы как параметры функций | * | * | * | |||||
3. | Методы и средства объектно-ориентиро-ванного программирования | * | * | * | |||||
4. | Абстрактные типы данных и типы данных, определяемые пользователем. Классы | * | * | * | |||||
5. | Виды программных алгоритмов | * | * | * | |||||
6. | Сортировка и поиск | * | * | * | |||||
7. | Сложные структуры данных | * | * | * | |||||
8. | Потоки ввода-вывода | * | * | * | |||||
9. | Эвристика. Способы конструирования программ | * | * |
Краткое содержание лекционного курса
1. Основные виды и этапы программирования
Анализ задачи, определение программы, разработка, кодирование, тестирование.
2. Типизация и структуризация программных данных Статические и динамические данные. Динамические массивы как параметры функций
Различие статических и динамических данных. Динамическое выделение памяти. Создание и удаление динамических массивов. Динамические массивы в качестве параметров функций.
3. Методы и средства объектно-ориентированного программирования
Структурное и модульное программирование. Понятие объектно-ориентированного программирования. Этапы объектно-ориентированного программирования: анализ, проектирование
4. Абстрактные типы данных и типы данных, определяемые пользователем. Классы
Объединения. Структуры. Понятие класса. Классы и объекты. Характеристики объектов: абстракция, инкапсуляция, модульность, иерархия. Статическое и динамические создание объектов. Наследование, виды наследования. Полиморфизм, использование виртуальных функций. Перегрузка функций и операторов.
5. Виды программных алгоритмов
Рекурсия, итерация, ветвление, повторение.
6. Сортировка и поиск
Функции-шаблоны (параметризованные функции). Основные принципы сортировки. Сравнительный анализ основных методов сортировки. Методы сортировки: пузырьковая сортировка, метод отбора, метод вставки, метод Шелла, быстрая сортировка. Основные методы поиска: метод последовательного поиска и метод бинарного поиска.
7. Сложные структуры данных
Классы-шаблоны (параметризованные классы). Контейнерные классы. Ограниченный (защищенный) массив. Списки, виды списков. Стеки и очереди: на основе использования динамического массива и на основе списка. Дерево. Бинарное дерево. Алгоритмы обработки бинарных деревьев.
8. Потоки ввода-вывода
Потоковые классы, сравнение ввода-вывода в С и С++. Форматирование потоков ввода-вывода. Манипуляторы потока: встроенные, создание собственных. Файловые потоки: класс fstream, некоторые особенности файловых потоков. Буферизуемые потоки. Перегрузка потоковых операций.
9. Эвристика. Способы конструирования программ
Эвристические способы разработки программ.
Лабораторный практикум
Таблица 3 – Лабораторный практикум и его взаимосвязь с содержанием лекционного курса
№ п/п | № раздела | Наименование лабораторной работы |
1 | 2 | Статические и динамические данные. Динамические массивы как параметры функций |
2 | 2, 4 | Структуры |
3 | 2, 3, 4 | Классы. Наследование |
4 | 2, 3, 4 | Классы. Виртуальные функции. Дружественные функции. Перегрузка операторов |
5 | 5, 6 | Методы сортировки |
6 | 2, 3, 7 | Сложные структуры данных. Очереди, стеки, списки, деревья |
7 | 1, 8 | Работа с файлами. Файловые потоки ввода-вывода. |
краткие характеристики лабораторных работ по программированию
Динамическое выделение памяти. Динамические массивы как параметры функций
Задание: Написать программу, согласно варианту, в которой должно быть использовано динамическое выделение памяти.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода размерности массива и элементов массива. В обработчике нажатия кнопки создается динамический массив заданной размерности, заполняется введенными пользователем числами. Затем вызывается функция, предназначенная для выполнения действий, указанных в задании (суммирование, вычисление среднего арифметического и т. д.). Функция должна получать в качестве параметров размерность массива и указатель на массив, и возвращать результат. Результат должен быть выведен на окне программы.
Оснастка: ЭВМ.
Время выполнения работы – 4 часа.
Работа со структурами
Задание: Написать программу согласно варианту, в которой должна быть описана структура, созданы переменные (объекты) и динамические массивы типа данной структуры.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода необходимых по варианту данных (количество объектов, цвет и т. д.). Создается структура, описывающая характеристики объекта (координаты, цвет). В обработчике нажатия кнопки создается динамический массив объектов структуры. В обработчиках движения и нажатия кнопок мыши осуществляется заполнение элементов массива объектов структур. Затем вызывается функция, предназначенная для рисования на окне введенных пользователем объектов. Функция должна получать в качестве параметров размерность массива и указатель на массив объектов структур. Результат работы – выведенные на окне программы объекты.
Оснастка: ЭВМ.
Время выполнения работы – 4 часа
Классы. наследование
Задание: Написать программу согласно варианту, в которой должна быть разработана иерархия классов, созданы объекты и динамические массивы объектов или указателей на объекты данных классов.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода необходимых по варианту данных. Создается класс согласно заданию, описывающий характеристики объекта. В обработчике нажатия кнопки создается динамический массив объектов класса. Действия над объектами класса согласно варианту реализуются в отдельных функциях, в которые в качестве параметров передаются объекты классов. Результат работы – нарисованные в окне программы объекты.
Оснастка: ЭВМ.
Время выполнения работы – 6 часов
Классы. Виртуальные функции. Дружественные функции. Перегрузка операторов
Задание: Написать программу согласно варианту, в которой должен быть разработан класс (или иерархия классов), содержащий дружественные функции (виртуальные функции, функции перегрузки операторов), созданы объекты и динамические массивы объектов или указателей на объекты данных классов.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода необходимых по варианту данных. Создается класс согласно заданию, описывающий характеристики объекта. В обработчике нажатия кнопки создается динамический массив объектов класса. Действия над объектами класса согласно варианту реализуются в отдельных функциях, в которые в качестве параметров передаются объекты классов. Результат работы – нарисованные в окне программы объекты, либо результат выполнения перегруженных операций над созданными в программе типами данных.
Оснастка: ЭВМ.
Время выполнения работы – 6 часов
Методы сортировки
Задание: Написать программу, согласно варианту, в которой должно быть использовано динамическое выделение памяти для массива и выполнена сортировка данного массива указанным методом.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода размерности массива и элементов массива. В обработчике нажатия кнопки создается динамический массив заданной размерности, заполняется введенными пользователем числами. Затем вызывается функция, предназначенная для выполнения сортировки методом, указанным в задании (пузырьковым, отбора, вставки, Шелла, быстрой). Функция должна получать в качестве параметров размерность массива и указатель на массив. Результат – отсортированный массив - должен быть выведен на окне программы.
Оснастка: ЭВМ.
Время выполнения работы – 4 часа
Сложные структуры данных. Очереди, стеки, списки, деревья
Задание: Написать программу согласно варианту, в которой должен быть описан класс стека, очереди, списка или дерева, созданы переменные (объекты) этого класса и использованы для решения какой-либо задачи.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода необходимых по варианту данных. Описать класс требуемой структуры данных. Создать объект класса, вызвать функцию и решить с его помощью указанную в варианте задачу. Вывести результат на окно программы.
Оснастка: ЭВМ.
Время выполнения работы – 8 часов
Работа с файлами. Файловые потоки ввода-вывода.
Задание: Написать программу, согласно варианту, в которой осуществляются указанные действия с файлом с помощью потоков ввода-вывода.
Исполнение: В среде разработки C++ Builder создать окно, предусмотреть возможность ввода необходимых данных (имя файла и т. д.). В обработчике нажатия кнопки осуществляется открытие и чтение выбранного файла. Затем вызывается функция, предназначенная для выполнения обработки данного файла. Результат (согласно заданию) выводится на окне программы.
Оснастка: ЭВМ.
Время выполнения работы – 4 часа
Расчетно-графическая работа
Расчетно-графические работы выполняются в рамках учебно-исследовательской работы кафедры.
Целью выполнения расчетно-графической работы является практическое применение полученных знаний и навыков по программированию для выполнения самостоятельного проекта, представляющего собой законченное приложение, предназначенное для решения каких-либо практических задач.
Задача. Разработать и отладить приложение для Windows, предназначенное для решения какой-либо задачи, используя теоретические сведения и практические навыки, полученные при изучении курса.
Содержание. Расчетно-графическая работа должна содержать: программу, написанную в среде разработки C++ Builder, пояснительную записку, включающую около 15 листов, текст программы и примеры ее выполнения.
Основная тематика расчетно-графической работы
Расчетно-графическая работа должна выполняться с использованием материалов курса «Программирование».
1. Разработка и использование синтаксического анализатора.
2. Сравнение быстродействия алгоритмов сортировки.
3. Разработка и практическое использование сложных структур данных.
4. Обработка текста (шифрование и сжатие).
5. Построение и расчет схем.
6. Работа с трехмерной графикой.
7. Сбор и обработка информации.
8. Библиотека для отображения графической информации (построение и обработка графиков)
9. Работа с сигнальными графами
Время выполнения расчетно-графической работы – 17-34 часа.
Контроль знаний студентов
Вопросы входного контроля
1. Понятия "метод" и "алгоритм".
2. Виды алгоритмов.
3. Структурное и модульное программирование.
4. Методы сортировки.
5. Методы поиска.
6. Понятия рекурсии, итерации.
7. Статические и динамические данные.
Текущий контроль проходит в виде защиты лабораторных работ.
Вопросы для выходного контроля
1. Основные виды, этапы проектирования.
2. Жизненный цикл программ.
3. Структурное и модульное программирование.
4. Типизация и структуризация программных данных.
5. Статические данные.
6. Динамические данные, структуры данных.
7. Абстрактные типы данных.
8. Типы данных, определяемые пользователем.
9. Классы.
10. Списки.
11. Деревья.
12. Сети.
13. Методы сортировки и поиска.
14. Объектно-ориентированное программирование, его суть.
15. Потоки ввода-вывода.
16. Файловые потоки ввода-вывода.
Вопросы для тестирования (образцы)
Вариант № 1
Какой из перечисленных методов сортировки самый быстрый?a) Пузырьковая
b) Отбор
c) Вставка
d) Метод Шелла
Какая из структур данных позволяет осуществлять наиболее быстрый поиск элемента?a) Бинарное дерево
b) Стек
c) Очередь
d) Односвязный список
Какой из вариантов создания и удаления одномерного динамического массива правильный?a) int *a;
a=new *double [n];
delete a;
b) int **a;
a=new double [n];
delete [ ] a;
c) int *a;
a=new int [n];
delete [ ] a;
d) int **a;
a=new *int [n];
delete *a;
Какая из структур данных основана на принципе LIFO (последним вошел – первым вышел)?a) Очередь
b) Стек
c) Двусвязный список
d) Односвязный список
К каким разделам класса не будет иметь доступ дружественная функция?a) public
b) protected
c) private, public
d) будут доступны все разделы
Функция-шаблон определяется с помощью ключевого словаa) template
b) typedef
c) class
d) struct
Какой из приведенных примеров работы с указателем на функции (функтором) правилен?a) double *function(int a);
void f1(double ms);
function=f1;
b) double (*function)(double a);
double f1(double mas);
function=f1;
c) void (*function)(int a);
void f1(double mas);
function=&f1;
d) void (*function)(double a, int n);
void f1(double mas);
function=f1;
Какой наибольший уровень доступа к разделам базового класса будет у элементов производного класса, созданного с типом наследования protected?
a) public
b) private
c) protected
d) Нет доступа
Какой тип доступа к элементам класса будет по умолчанию?a) public
b) protected
c) private
d) protected и public
Размерность какого из перечисленных типов данных не может изменяться в ходе выполнения программы?a) Статический массив
b) Список
c) Динамический массив
Контроль самостоятельной работы студентов-заочников
Контроль самостоятельной работы студентов-заочников проводится по результатам выполнения контрольных работ.
Тематика контрольных работ
1. Обработка файлов
- Использование файловых потоков ввода-вывода
- Динамическое выделение памяти для обрабатываемых данных
- Использование методов шифрования или сжатия данных
2. Разработка и использование сложных структур данных
- Использование стека для преобразования систем счисления
- Использование списка для хранения данных
3. Построение и обработка графов
- Построение графа
- Обработка графов с использованием сложных структур данных
4. Сравнение быстродействия алгоритмов сортировки
- Создание и заполнение динамического массива
- Сравнение времени работы различных алгоритмов сортировки
- Вывод результатов в виде таблицы и графика
5. Синтаксический анализатор (парсер). Применить для ввода выражения и решения какой-либо задачи вычислительной математики
- Разработка синтаксического анализатора на основе любого принципа
- Разработка функций, реализующих численные методы
- Решение задач.
Учебно-методическое обеспечение дисциплины
Методические указания
\\ TS 2003 \ Common \ Student_ \ Kurs1 \ Progr\
Рекомендуемая литература
Основная литература
1. Г. Шилдт. Теория и практика С++: Пер. с англ. - СПб.: BHV - Санкт-Петербург, 19с.
УДК 681.3.06
2. Форд У. Структуры данных в С++: Пер. с англ. - М.: ЗАО "Издательство БИНОМ", 19с.
УДК 004.422 ББК 32.973 Т58
3. Пратт Т., Языки программирования: разработка и реализация / Под общей ред. А. Матросова. – СПб.: Питер, 2002. – 688 с.
УДК 681.3.06 ББК 32.973-018.1 П70
4. Программирование на С++: Учебное пособие/ , , ; Под ред. проф. . – СПб.: КОРОНА принт, 1999. – 256 с.
ББК 32.81
Дополнительная литература
1. Уолнем К. Объектно-ориентированное программирование на языке Borland C++/ Пер. с англ. - Мн.: ООО "Попурри", 19с.
2. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows/Пер. с англ. – СПб.: Питер, М.: Издательско-торговый дом «Русская редакция», 2001. – 752 с.
УДК 004.43 ББК 32.973.26-018 Р558
Материально-техническое обеспечение дисциплины
Для проведения лабораторных работ по дисциплине «Программирование» необходимы ЭВМ с операционной системой MS Windows и средой программирования C++ Builder 5 или 6.
Методические рекомендации
по организации изучения дисциплины
На основании программы кафедры разрабатываются рабочие учебные программы дисциплины с учетом фактического числа часов, отведенных на ее изучение. В рабочих программах предусматривается изучение тех тем, которые являются необходимыми для практического использования полученных навыков и определяются профилем подготовки каждого направления (специальности) дипломированных специалистов. Исходя из этого, в рабочей программе отдельные разделы программы могут быть либо усилены, либо сокращены или опущены.
Лабораторный практикум и практические занятия должны быть нацелены на практическое изучение основных программных структур данных, типов алгоритмов, принципов программирования, основных методов проектирования и разработки программных продуктов.
Самостоятельная работа студентов должна обеспечить выработку навыков самостоятельного творческого подхода к решению научно - исследовательских и технологических задач, дополнительную проработку основных положений дисциплины, приобретение навыков работы с научно-технической литературой.
Базовым для дисциплины «Программирование» является курс информатики.
Знания и навыки, полученные при изучении данного курса «Программирование», широко применяются студентами при изучении курсов по специальным технологиям и другим дисциплинам.
Программа рассчитана на 136 часов.
Программа составлена в соответствии с государственными образовательными стандартами высшего профессионального образования по направлениям подготовки (специальностям) в области техники и технологии.
Словарь терминов и персоналий
Основными терминами являются следующие:
· Дерево – нелинейная структура данных, в которой все узлы происходят от единственного начального узла, называемого корнем.
· Динамические данные – данные, память для которых выделяется программно при необходимости и должна программно освобождаться по завершении работы.
· Инкапсуляция – подход, при котором пользователь может манипулировать с объектами только с помощью определенных операций.
· Класс – пользовательский тип данных, объединяющий в себе данные и функции (методы), необходимые для их обработки (принцип инкапсуляции).
· Контейнерные классы - классы, предназначенные для хранения определенным образом организованных данных (стеки, очереди, деревья, списки и т. д.).
· Модульное программирование – подход к разработке программ, при котором программа делится на некоторое количество компонентов, называемых модулями, либо по функциональному признаку, либо по признаку используемых данных.
· Наследование – возможность создания новых классов на основе существующих. Свойства и методы базового класса могут наследоваться и перегружаться, могут быть добавлены новые свойства и методы.
· Объектно-ориентированное программирование – подход, при котором объектам реального мира ставятся в соответствие программные объекты, описывающие свойства и методы в рамках моделируемой предметной области.
· Очередь – структура данных, реализованная по принципу FIFO, то есть первый введенный в нее элемент будет извлечен первым.
· Полиморфизм – способность родственных классов обрабатывать одинаковые запросы в соответствии со своим типом.
· Рекурсия – решение задачи с помощью разбиения ее на меньшие подзадачи, решаемые с помощью одного и того же алгоритма. Алгоритм определен рекурсивно, если это определение состоит из одного или нескольких условий останова и шага рекурсии, в котором текущее значение в алгоритме определяется в терминах предыдущего значения.
· Семантика языка программирования определяет смысловые значения различных синтаксических конструкций.
· Синтаксис языка программирования определяет то, как выглядит программа на этом языке. Определить синтаксические правила – значит объяснить, как пишутся операторы, объявления и другие языковые конструкции.
· Сортировка – процесс упорядочения однотипных данных по возрастанию или убыванию.
· Список – структура данных, состоящая из упорядоченной последовательности структур данных.
· Стек - структура данных, реализованная по принципу LIFO, то есть последний введенный в нее элемент будет извлечен первым.
· Структура – тип данных, определяемый пользователем и включающий в себя данные различных типов, а также функции.
· Структурное программирование – методология разработки программ, включающая:
1) иерархическую разработку программных структур, использующую только простые формы управления (композицию, ветвление, повторение);
2) представление иерархической структуры программы непосредственно в ее тексте, использующее «структурированные» операторы управления;
3) текст программы, в котором последовательность появления операторов должна соответствовать последовательности их выполнения;
4) использование групп операторов, предназначенных для вычисления одной цели.
Использование данных принципов позволяет легче понимать, отлаживать и модифицировать программу.
