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

Курский государственный технический университет

Кафедра ПО ВТ

КУРСОВАЯ РАБОТА

по дисциплине «Программирование на языке высокого уровня»

«Прикладная программа. Раскраска графа»

Выполнил:

Проверил:

Курск, 2007 г

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

1 ТЕХНИЧЕСКОЕ ЗАДАНИЕ 5

1.1 Назначение разработки 5

1.2 Основание для разработки 5

1.3 Требования к программе 5

1.3.1 Входные данные 5

1.3.2 Выходные данные 5

1.3.3 Процессы обработки 5

1.3.4 Требования пользователя 5

1.3.5 Функциональные требования 6

1.3.6 Требования к условиям эксплуатации 7

1.3.7 Требования к численности и квалификации персонала 7

1.3.8 Требования по сохранности информации 8

1.3.9 Требования по стандартизации и унификации 8

1.3.10 Требования к программной совместимости 8

1.3.11 Результирующие компоненты изделия 8

1.3.12 Этапы разработки программы 8

1.3.13 Требования к документации 9

2 ВАРИАНТ ЗАДАНИЯ 10

3 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 10

4 ЭСКИЗНЫЙ ПРОЕКТ 12

4.1 Переборный алгоритм раскраски 12

4.2 Последовательный алгоритм раскраски 13

4.3 Разработка структуры программы 14

5 ТЕХНИЧЕСКИЙ ПРОЕКТ 16

5.1 Сценарий диалога с пользователем 16

5.2 Разработка основных форматов данных 20

5.3 Детализация алгоритма раскраски графа 24

5.4 Разработка формата файла для хранения графов 26

6 РАБОЧИЙ ПРОЕКТ 29

6.1 Выбор удобочитаемых идентификаторов 29

6.2 Общая организация проекта 29

6.3 Описание модулей 30

6.3.1 Модуль uMain 30

6.3.1.1 Основные переменные, константы и типы модуля 30

6.3.1.2 Компоненты модуля 30

6.3.1.3 Процедуры модуля 32

6.3.1.4 Функции модуля 35

6.3.2 Модуль uData 35

6.3.3 Модуль uFiling 35

6.3.3.1 Основные переменные, константы и типы модуля 35

6.3.3.2 Функции модуля 35

6.3.4 Модуль uColoring 36

6.3.4.1 Основные переменные, константы и типы модуля 36

6.3.4.2 Процедуры модуля 36

6.3.4.3 Функции модуля 36

6.3.5 Модуль uInputk 36

6.3.5.1 Основные переменные, константы и типы модуля 37

6.3.5.2 Компоненты модуля 37

6.3.5.3 Процедуры модуля 37

6.3.6 Модуль uHelp 38

6.3.6.1 Основные переменные, константы и типы модуля 38

6.3.6.2 Компоненты модуля 38

6.3.6.3 Процедуры модуля 38

6.4 Отладка и тестирование программного продукта 39

6.5 Руководство пользователю 47

ПРИЛОЖЕНИЕ: Листинг программы 50

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 75

Введение

Задачи на графах являются одними из наиболее трудоемких. Для многих из них не существуют достаточно эффективных алгоритмов решения. Это объясняется комбинаторным характером процесса поиска решений и сложной логикой действий на каждом его шаге. Реализация задач данного класса на ПЭВМ позволяет повысить качество их решения за счет существенного увеличения числа анализируемых вариантов.

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

В данной курсовой работе решается одна из известных графовых задач – поиск раскраски вершин заданным числом цветов. На основе известного алгоритма последовательного сокращенного перебора вершин разрабатывается граф-схема алгоритма раскраски. Выполняется программирование граф-схемы на языке Object Pascal, реализуется графическое отображение и редактирование графов, их сохранение в файлах специального упакованного формата. Все указанные действия осуществляются в среде программирования Delphi 7.0.

1 Техническое задание

1.1 Назначение разработки

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

1.2 Основание для разработки

Данный программный продукт разрабатывается как курсовая работа по дисциплине «Программирование на языках высокого уровня».

1.3 Требования к программе

1.3.1 Входные данные

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

1.3.2 Выходные данные

К выходным данным относятся вариант раскраски графа заданным числом цветов, хроматическое число графа, сообщения о невозможности нахождения раскраски.

1.3.3 Процессы обработки

Ввод исходного графа и числа цветов, сохранение графа в файле, чтение графа из файла, нахождение раскраски, отображение раскраски.

1.3.4 Требования пользователя

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

• работа в условиях визуального (графического) режима;

• удобство и простота ввода графа (задание с помощью мыши, клавиатуры и меню);

• обеспечение автоматического контроля правильности входной информации, вводимой пользователем (контроль параметров графа, количества цветов);

• возможность сохранения и считывания сохраненных графов из файлов;

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

1.3.5 Функциональные требования

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

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

• отображение графа в виде матрицы смежности вершин. Требуется обеспечить возможность добавления ребер и их удаления через матрицу;

• граф при необходимости сохраняется в файле специального формата (формат разрабатывается в ходе выполнения курсовой работы). Допускается открытие любого файла с ранее сохраненным графом с проверкой корректности формата файла;

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

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

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

• максимальное количество вершин графа должно быть ограничено некоторой константой, зависящей от применяемого алгоритма раскраски и быстродействия используемой ЭВМ. Количество ребер не ограничивается;

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

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

1.3.6 Требования к условиям эксплуатации

• ПЭВМ класса IBM PC/AT;

• операционная система Windows 2000, XP;

• язык программирования Object Pascal;

• среда программирования Delphi 7 и выше;

• меню, сообщения и система поиска на русском языке;

• разрешение экрана не менее 800x600 точек.

1.3.7 Требования к численности и квалификации персонала

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

1.3.8 Требования по сохранности информации

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

1.3.9 Требования по стандартизации и унификации

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

1.3.10 Требования к программной совместимости

Код программы должен быть написан на стандартном языке Pascal с использованием стандартных компонент библиотеки VCL Delphi 7.0.

1.3.11 Результирующие компоненты изделия

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

1.3.12 Этапы разработки программы:

• проектирование структуры программы;

• разработка сценария диалога с пользователем;

• разработка основных алгоритмов;

• проектирование формата файлов;

• программирование алгоритмов и структур данных;

• отладка и тестирование программы;

• документирование.

1.3.13 Требования к документации

Перечень представляемых документов:

• задание на курсовую работу;

• техническое задание на разработку;

• описание структуры программы;

• описание сценария диалога с пользователем;

• схемы основных алгоритмов;

• описание форматов данных и файлов;

• контрольные примеры и результаты программы;

• листинги основных программных модулей;

• краткая эксплуатационная документация.

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

Документы по содержанию должны соответствовать ГОСТ 34.201-89, 34.602-89, 19.701-90.