Описание организации структур данных в программе.

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

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

Например, для представления в программе графа представленного на рис. 1 можно использовать списки смежности рис. 2 или список ребер рис.3.

	Рис. 1 Ориентированный граф
		Рис. 2 Список смежности графа

	Рис. 3 Список ребер графа

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

Описание алгоритма

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

 

Например, алгоритм сортировки вставками в виде блок-схемы представлен на рис.4.

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

Алгоритм сортировки вставками, состоит из 3 простых шагов:
1. Ищем в нашей последовательности данных минимальный элемент.
2. Перемещаем найденный элемент на первое место, остальные элементы сдвигаем вправо.
3. Теперь уже среди N-1 элемента ищем минимальный и проделываем такие же действия.

 

Формальное описание входных данных.

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

Формальное описание выходных данных

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

Описание сценария диалога

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

Описание процедур и функций

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

Результаты тестирования программы

В разделе «Результаты тестирования программы» приводятся наборы тестовых данных (включая эталонные результаты) и полученные на них результаты выполнения программы.

 

В заключении дается анализ результатов и делаются выводы по результатам тестирования и отладки.

Требования к функциональным характеристикам

 

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

- ввод исходных данных задачи;

- расчет параметров;

- оценка стоимости реализации алгоритма по временным и объемным параметрам;

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

- хранение результатов решения с возможностью их повторной визуализации;

- вывод результирующих данных;

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

- хранение результатов решения с возможностью их повторной визуализации.

 

 

Требования к оформлению пояснительной записки

 

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

1. Введение.

2. Содержательная постановка и описание задачи.

3. Анализ предметной области.

4. Описание организации структур данных.

5. Описание алгоритма.

6. Формальное описание входных данных.

7. Формальное описание выходных данных.

8. Описание диалога.

9. Описание процедур и функций.

10. Результаты тестирования программы.

11. Заключение.

12. Список литературы.

Кроме этого, в приложение необходимо включить:

1. Графическое описание данных.

2. Формат выходного документа.

3. Листинг программы.

В приложении приведены пример оформления титульного листа.

 

 

 

Тематика курсовых работ

 

1. Применение линейных структур данных при разработке программных приложений:

- применение стеков при разработке приложений;

- применение очередей при разработке приложений;

- применение деков при разработке приложений;

- применение иерархических списков при разработке приложений.

 

2. Применение нелинейных структур данных при разработке программных приложений:

- работа с бинарными деревьями поиска;

- работа со сбалансированными деревьями поиска;

- работа с оптимальными деревьями поиска;

- работа с B-деревьями;

- работа с крупномасштабными деревьями;

- применение бинарных деревьев при решении задачи сжатия информации (алгоритм Хаффмена).

 

3. Организация исчерпывающего поиска:

- применение рекурсии при решении задач поиска;

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

- применение метода ветвей и границ;

- применение метода динамического программирования.

 

4. Алгоритмы сортировки:

- алгоритмы внутренней сортировки (вставкой, обменом, выбором);

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

- алгоритмы внешней сортировки.

 

5. Алгоритмы решения задач на графах:

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

- алгоритмы решения задач оценки связности графов;

- алгоритмы решения задач нахождения кратчайших путей;

- алгоритмы решения задач нахождения остовных деревьев;

- алгоритмы решения задач упорядочения графов;

- алгоритмы решения задач нахождения циклов в графах.

Список рекомендуемой литературы

 

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2001.

2. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, 2001.

3. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Вильямс, 2000.

4. Кнут Д. Искусство программирования для ЭВМ. Т.1. Получисленные алгоритмы. – М.: Вильямс, 2000.

5. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М.: Вильямс, 2000.

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.

7. Баррон Г. Рекурсивные методы в программировании. – М.: Мир, 1974.

8. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.

9. Макконелл Дж. Анализ алгоритмов: Вводный курс. – М.: Техносфера, 2002.

10. Хусаинов Б. С. Структуры и алгоритмы обработки данных: Примеры на языке Си: Учебное пособие для вузов. – М.: Финансы и статистика, 2004.

 

 

Приложение. Образец формы титульного листа курсовой работы

 

 

Министерство образования РФ

 

ФГБОУ ВПО «Дагестанский государственный технический университет»

Факультет КТВТиЭ