Лабораторные работы Вычислительные системы
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Лабораторная работа. представления и обработка моделей графов в ПК

Цель работы:

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

- приобрести навыки разработки процедур обработки графовых моделей.

 

Задание на лабораторную работу: Разработать процедуры, выполняющие ввод и преобразование данных, описывающих граф и вывод полученного результата преобразования. Создать программу, которая, загружая данные из файла, производила бы их преобразование из исходной формы в заданную, и вывод результатов преобразования в файл. При этом на этапах ввода, преобразования и вывода данных должен осуществляться контроль корректности информации и производиться обработка ошибок. В оперативной памяти (ОП) граф должен быть представлен в битовой форме. Ограничение: максимальный размер графа – 16 вершин.

Структура разрабатываемой программы изображена на рисунке 10.

Рисунок 10 – Структурная схема программы.

Программа состоит из четырех процедур:

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

-  Процедура 1 (Пр1), предназначена для ввода описания графа из файла исходных данных и формирования модели графа в ОП;

-  Процедура 2 (Пр2), предназначена для реализации функции обработки графа и формирования результирующих данных;

-  Процедура 3 (Пр3), предназначена для вывода результирующих данных в текстовый файл.

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

Программа разрабатывается в составе бригады из двух студентов:

-  Первый определяет структуры данных для представления модели графа и результирующих данных. Разрабатывает главную процедуру и процедуру 2;

-  Второй определяет форматы представления описания графа и выходных данных. Разрабатывает процедуры 1 и 3.

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

Таблица 1 – Варианты заданий

Способ представления описания графа

Способ представления модели графа

Способ представления результирующих и выходных данных

1

МИ

МИ

МС

2

МС

МС

МИ

3

МИ

МИ

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

4

МС

МС

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

Способ представления описания графа

Способ представления модели графа

Способ представления результирующих и выходных данных

5

Список дуг

МИ

Получить список вершин, у которых число входов меньше, чем число выходов

6

Список дуг

МС

Получить список вершин, у которых число входов больше, чем число выходов

7

МИ

МИ

Список дуг

8

МС

МС

Список дуг

9

МИ

МИ

Список вершин, у которых число дуг больше заданного N

10

МС

МС

Список вершин, у которых число дуг меньше заданного N

11

Список дуг

МИ

Получить список вершин, у которых число входов равно числу выходов

12

Список дуг

МС

Получить список вершин, у которых четное число входов

В таблице 1 приняты следующие обозначения:

МС – матрица смежности;

МИ – матрица инцидентности.

4.1. Требования к выполнению лабораторной работы

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

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

·  единство данных – определение множества данных функционально-полно описывающих некоторый объект и объединение их в один класс или запись;

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

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

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

4.2. Контрольные вопросы

1.  Дать определение графа.

2.  Объяснить разницу между ориентированным и неориентированным графом.

3.  Представить граф с помощью:

а) матрицы смежности;

б) матрицы инцидентности.

4.  Привести формулу расчета объема оперативной памяти для представления графа, состоящего из n вершин и m дуг:

а) с помощью матрицы смежности;

б) с помощью матрицы инцидентности;

в) с помощью списка дуг.

4.3.  Содержание отчета

1.  Постановка задачи.

2.  Краткое описание способа решения задачи.

3.  Описание структур данных.

4.  Спецификация на процедуры и функции.

5.  Описание алгоритмов решения задачи.

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

7.  Текст программы.

8.  Результаты тестирования.

9.  Заключение (выводы).

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

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство