Методические указания по выполнению курсовой работы по дисциплине "Информатика" для студентов направления 500200 "Автоматизация и управление" специальностей 210500 "Системы управления летательными аппаратами"

Вид материала

Содержание

Работа со структурами данных
Список нормативной документации

Подобный материал:

Федеральное агентство по образованию

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

профессионального образования

Тульский государственный университет

Кафедра "Системы автоматического управления"

Методические указания

по выполнению курсовой работы

по дисциплине "Информатика"

для студентов направления 500200 "Автоматизация и управление"

специальностей 210500 "Системы управления летательными аппаратами"

0718900 "Мехатроника"

очной формы обучения

Тула 2005

Разработали: А.С. Илюхин, канд. техн. наук, доцент

Н.С. Илюхина, канд. техн. наук, доцент

Введение

Курсовая работа по дисциплине "Информатика" является самостоятельной работой студента, цель которой - закрепление и углубление знаний по дисциплине и получению практических навыков по разработке программ для обработки данных структурированного типа.

Студент при выполнении курсовой работы изучает дополнительные разделы теории программирования, изучает принципы построения структур данных и основные методы работы с ними.

Цель и задачи выполнения курсового проекта

2.1. Цель курсового проекта - развить у студента способность самостоятельно решать задачи, связанные с разработкой программ для обработки больших массивов информации.

2.2. Основные задачи курсового проекта.

- закрепление, углубление и обобщение знаний, полученных студентом в

процессе изучения дисциплины "Информатика";

- изучение дополнительных материалов, связанных с разработкой алгоритмов сортировки и поиска;

- дальнейшее формирование практических навыков по программированию;

- изучение правил оформления работы в виде отчета в соответствии с требованиями.

Основные требования к курсовому проекту

3.1.Тематика работы.

Курсовая работа посвящена разработке программ для сортировки и поиска при представлении данных в виде массивов и динамических структур данных: односвязных и двусвязных списков и деревьев.

Исходные данные к курсовому проекту.

Программа должна выполнять сортировку данных смешанного типа, одной из следующих структур:

№ варианта структуры, №№ полей
1. "Список студентов".
Поле №1	Поле №2	Поле №3	Поле №4
Фамилия имя и отчество	Дата рождения	Год рождения	Средний балл
2. "Расписание движения транспорта".
Пункт отправления	Пункт прибытия	Время отправления	Номер рейса.
3. "Ведомость учета товаров"
Наименование товара	Количество товара на складе	Цена за единицу веса	Срок реализации

Исходная информация должна быть записана в текстовом файле в виде построчного списка, каждая строка которого должна соответствовать одному из вариантов структур. Файл исходных данных должен содержать 6 – 8 строк.

Каждый элемент информационной структуры (элемент массива или поле INFO узла списка или дерева) должен быть описан как тип данных "Запись", причем элементы каждого столбца списка должны быт представлены отдельным полем записи.

Сортировка массивов должна быть выполнена с помощью одного из следующих методов:

№ варианта	Метод
1	Сортировка с разделениями
2	Пирамидальная сортировка
3	"Быстрая" сортировка Хоора

Сортировка с использованием динамических структур должна быть выполнена с помощью одного из следующих методов:

№ варианта	Тип динамической структуры
1	Односвязный список
2	Двусвязный список
3	Бинарное дерево

Вариант задания выбирается из таблицы вариантов по номеру студента в списке группы.

Таблица вариантов задания

№ варианта	№ варианта структуры данных	Ключ сортировки (№ поля записи)	№ варианта метода сортировки массивов	№ варианта динамической структуры
1	1	1	1	1
2	1	1	1	2
3	1	1	2	2
4	1	2	1	3
5	1	3	2	3
6	2	1	3	1
7	2	2	2	1
8	2	3	3	2
9	2	4	1	2
10	3	1	3	3
11	3	2	1	1
12	3	3	1	2
13	1	4	1	3
14	2	1	1	1
15	2	2	2	2
16	1	1	3	3
17	3	3	3	3
18	3	1	1	1
19	3	2	2	2
20	3	1	3	1
21	1	3	1	3
22	2	1	1	1
23	3	3	3	1
24	2	3	3	2
25	2	3	1	1
26	3	2	1	3

3.3. Задание на курсовой проект.

Разработать программу в системе программирования Турбо-Паскаль 7.0, выполняющую следующие действия.

В режиме диалога задавать вид представления обрабатываемых данных:: массив или динамическая структура.
В зависимости от вида представления выполнять сортировку одним из методов, указанных в таблице вариантов.
Чтение данных из внешнего файла.
Вывод исходных данных и результатов на дисплей.

Требования к структуре программы.

Программа должна состоять из главной программы, модуля сортировки массивов и модуля сортировки с использованием динамической структуры.

Главная программа должна выполнять обращение к одному из модулей.

Модуль сортировки массивов должен содержать процедуры чтения данных из внешнего файла, процедуру сортировки и процедуру вывода исходных данных и результатов на дисплей.

Модуль сортировки с использованием динамической структуры должен содержать процедуру поиска места вставки нового узла, процедуру или функцию добавления нового узла, процедуру (функцию) вывода результатов на дисплей.

При разработке процедуры поиска места вставки нового узла должна использоваться рекурсия.

3.4. Объем курсового проекта

3.4.1. Законченный курсовой проект оформляется в виде отчета,

включающего расчетно-пояснительную записку объемом 10 - 15 страниц текста на листах формата

3.4.2. Примерное распределение материала расчетно-пояснительной

записки по разделам в процентах от полного объема приведено в таблице 1 Таблица 1.

Разделы курсового проекта	Примерный объем
Введение	10 %
Описание используемых методов.	40 %
Описание алгоритмов	25 %
Описание программ	25 %

3.4.3. В расчетно-пояснительной записке к курсовой работе должны быть:

- подробное описание используемых методов;

- описание алгоритмов;

- описание программ;

- текст программы (распечатка) и распечатка файла исходных данных.

3.4.4. Пояснительная записка оформляются в соответствии с ЕСКД ГОСТ 2.105-79.

Примечание: Допускается не делать рамку на листах пояснительной записки.

3.5. Работа над курсовым проектом

Работа над курсовым проектом определяется графиком выполнения проекта.

График выполнения проекта.

Этапы выполнения проекта	Недели	Проценты
Получение задания	1 – 2	5
Подбор литературы	3 – 4	10
Разработка алгоритма	5 – 6	10
Разработка программы	7 – 8	20
Отладка программы	9 – 12	50
Защита работы	13 – 14	5

На начальном этапе студент при помощи руководителя, ведущего курсовой проект, осуществляет анализ выданного задания, производит подбор литературы. Он знакомится с известными решениями поставленной задачи в найденных литературных источниках, производит сравнительный анализ возможных вариантов решения поставленной задачи, цели и задачи, решаемые в работе. Результаты этой работы излагаются во введении.

На следующем этапе работы в общей части рассматривается выбранный вариант метода и алгоритма решения. Описание алгоритма должно пояснять структуру программы и взаимодействие всех программных единиц. Затем на основании исходных данных выданного задания разрабатывается текст программы и ее описание. Описание программы должно включать описание всех программных единиц, списков формальных параметров и других объектов программы с указанием их типов и назначения.

3.6. Защита курсовой работы.

3.6.1. Защита законченной курсовой работы проводится с демонстрацией работы программы

3.6.2. При оценке работы учитываются:

- техническая грамотность, соответствие результатов заданию, последовательность решения, лаконичность и эффективность предлагаемых алгоритмических решений;

- эрудиция студента (общая, техническая);

- качество выполненных работ (оформление, грамотность, аккуратность);

- соблюдение сроков, предусмотренных графиком выполнения проекта.

3.6.3. Учет всех параметров определяет объективность оценки защиты проекта:

- "отлично" - безукоризненная по всем пунктам защита проекта;

- "хорошо" - недостаточная эффективность решений и некоторые погрешности оформления;

- "удовлетворительно" - нечеткость изложения и некоторое несоблюдение требований по организации программы, несоблюдение графика выполнения работ;

"не удовлетворительно" – неправильная работа программы.

4. Методические указания к работе над курсовым проектом

4.1.Сортировка массивов.

Методы сортировки, рассматриваемые в данной работе являются развитием трех, так называемых "простых" методов сортировки. Алгоритмы сортировки подробно изложены в [4 ]. Данные при этом описываются как массивы с элементами типа "запись". Например, необходимо представить данные следующей структуры:

"Телефонная книга".

Фамилия	Имя	Отчество	Улица	дом	квартира	№ тел.
Иванов	Петр	Львович	Мира	7	21	351418

Для их описания можно воспользоваться следующей конструкцией:

Type stroka=record

F,I,O:strihg[20];

Street:string[40];

Block,flat:integer;

Number:srting[6];

End;

Mass=array[1..200] of stroka;

Var sort:mass;

Сортировка должна выполняться на "месте". Оценка эффективности работы программы проводится по количеству операций сравнения и обмена.

Сортировка с применением динамических структур данных.

Статические структуры данных обладали тем свойством, что под них выделяется вполне определенный размер памяти и между отдельными объектами устанавливаются связи еще на этапе компиляции и компоновки. Во время работы программы вносить изменения в выделенный размер памяти или установленные связи не удается. Порой это бывает неудобно. Например, программа работает с различным количеством целых чисел. Естественно разместить их в каком-то массиве. Размер массива должен быть определен заранее, и, если программа должна быть универсальной, при определении массива необходимо учитывать случай максимального количества таких чисел. Однако это приведет к неэффективному использованию оперативной памяти.

В языке Паскаль есть возможность по ходу выполнения программы выделять и освобождать необходимую память для размещения в ней различных данных. Таким образом можно организовывать динамические, т. е. изменяющие размеры, структуры данных. Оперативная память при этом используется наиболее эффективным образом. Такая возможность связана с наличием в языке особых типов данных - указателей. Область оперативной памяти, где можно выделять отдельные участки для размещения данных и освобождать их, будем называть динамической областью памяти или динамической памятью. Указатель в Тurbo-Pascal дает адрес объекта определенного типа, называемого базовым типом.

Работа со структурами данных

Возможность выделения и освобождения области памяти позволяет создавать структуры данных с переменным числом элементов - динамические структуры. Чаще всего используют т. н. связанные структуры, когда среди элементов устанавливается некоторая иерархия, например наподобие списков или генеалогического дерева. Среди таких структур наибольшее распространение в различных практических приложениях получили линейные структуры (списки) и структуры-деревья (более подробно о разнообразии структур см., например,

[5]. В связных структурах обычно используются однотипные элементы. Каждый элемент имеет две различные части:

• информационную часть - та часть, которая содержит всю информацию о том или ином объекте (например если это структура целых чисел, то значение конкретного числа);

• ссылку на соседний элемент (соседние элементы) в конкретной иерархии элементов (например, если структура является списком, то ссылка на элемент, стоящий в списке непосредственно за данным элементом, а может быть, и на предыдущий элемент).

Наиболее удобно для фиксации такой информации использовать тип-запись. Пример. Тип элемента структуры, содержащего символьную информацию в виде строки.

Type

Ppoint=elem; {указатель на элемент)

Elem =Е1ет = record

Info : string[80];

Link :Ppoint;

End; (тип элемента структуры)

Приведенная выше структура может быть использована для создания односвязного линейного списка. Двусвязный список и бинарное дерево имеют два адресных поля, поэтому могут быть представлены следующим образом.

Type

Ppoint=elem; {указатель на элемент)

Elem =Е1ет = record

Info : string[80];

Left,Right :Ppoint;

End; (тип элемента структуры)

При работе с динамическими структурами данных выполняются следующие основные операции;

добавление элемента структуры;

исключение элемента структуры;

поиск элементов структуры по какому-то признаку.

Сортировка с использованием динамических структур представляет собой создание упорядоченной структуры с последующим выводом в файл или на экран и состоит из операций поиска места включения элемента и включение нового элемента. При этом структура должна остаться упорядоченной.

Оформление расчетно-пояснительной записки осуществляется на белой бумаге формата А4 в соответствии с ГОСТ 2.106-68 ЕСКД "Текстовые документы" (1-11-78**); ГОСТ2.105-79 ЕСКД "Основные требования к текстовым документам" и других нормативных документов, указанных в прилагаемом списке нормативно-конструкторской документации.

СПИСОК НОРМАТИВНОЙ ДОКУМЕНТАЦИИ

Стандарты ЕСКД по правилам выполнения чертежей и схем и на условные графические обозначения.

Общие правила выполнения некоторых документов.

1. ГОСТ 2.102-68. ЕСКД Виды и комплекты конструкторской документации;

2. ГОСТ 2.104-68. ЕСКД Основные надписи(1-1-73)*) ;

3. ГОСТ 2.105-79. ЕСКД Основные требования к текстовым документам;

ГОСТ 2.106-68. ЕСКД Текстовые документы;

Библиографический список.

1. Э.И. Кузнецов, Г.Д. Фролов, Элементы информатики, издательство "Высшая школа", Москва, 1989 г.

2. Н.И. Вьюкова, В.А. Галатенко, А.Б. Ходулев, Систематический подход к программированию, издательство "Наука", Главная редакция физико-математической литературы, Москва, 1988 г.

3. О.Н. Перминов, Программирование на языке ПАСКАЛЬ, издательство "Радио и связь", Москва, 1988 г.

4. Б. Карниган, Ф. Плоджер, Инструментальные средства программирования на языке Паскаль, перевод с английского, "Радио и связь",

Москва, 1985 г.

5. Н. Вирт, Алгоритмы + структуры данных = программы, перевод с английского, издательство "Мир", Москва, 1985 г.

6. В.Э. Фигурнов, IBM PC для пользователя, издательство "Финансы и статистика", Москва, 1993 г.

7. Г. Кушниренко, Г.В. Лебедев, Программирование для математиков, издательство "Наука", ГРФМЛ, Москва, 1988 г.

Приложение 1.

Образец титульного листа курсового проекта.

Федеральное агентство по образованию

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

профессионального образования

Тульский государственный университет

Кафедра "Системы автоматического управления"

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине

" Информатика"

на тему: _______________________________________

(тема курсовой работы)

Разработал студент гр._____________________

Консультировал: (Ф.И.О. преподавателя)

Тула 2005 г.

2-й лист

З А Д А Н И Е

на курсовой проект по дисциплине " Информатика"

Исходные данные

Вариант структуры элемента информации

Вариант ключа сортировки

Вариант метода сортировки массивов

Вариант динамической структуры

Blog

Содержание

Работа со структурами данных