Математическая постановка решаемой задачи

Введение

Перед выполнением задания, которое выдает преподаватель, студент должен овладеть знаниями по «Дискретной математике», навыками работы в операционной системе Windows, в текстовом редакторе Word, в среде программирования Turbo Pascal.

Для контроля подготовленности студента к выполнению работы приведен перечень контрольных вопросов.

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

 

Задания для курсовой работы

1. Создайте программную реализацию алгоритм Тэрри для нахождения компонент связности графа.

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

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

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

5. Создать программную реализацию алгоритма нахождения остовного дерева графа.

6. Создать программную реализацию нахождения минимального расстояния в нагруженном графе.

7. Создать программную реализацию нахождения максимального расстояния в нагруженном орграфе.

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

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

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

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

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

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

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

15. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа в глубину.

16. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа по ширине.

Реализовать:

17. Алгоритм Тэрри нахождения пути в графе из заданной вершины x в заданную вершину y.

18. Алгоритм Тэрри нахождения компонент связности графа.

19. Алгоритм Фронта волны нахождения минимального пути в графе из заданной вершины x в заданную вершину y.

20. Алгоритм Фронта волны нахождения минимального пути в ориентированном графе из заданной вершины x в заданную вершину y.

21. Алгоритм нахождения остовного дерева графа.

22. Алгоритм нахождения минимального остовного дерева в графе.

23. Алгоритм обхода графа в ширину.

24. Алгоритм обхода графа в глубину.

25. Алгоритм нахождения компонент связности графа.

26. Алгоритм расчета числовых характеристик графа.

27. Алгоритм расчета степеней вершин графа.

28. Алгоритм расчета полустепеней исхода и захода графа.

 

 

Структура курсовой работы

 

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

Объем пояснительной записки составляет, как правило, 10 страниц машинописного текста.

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

· титульный лист;

· задание на выполнение работы;

· реферат;

· содержание;

· введение;

· основную часть;

· заключение;

· список использованных источников;

· приложения.

 

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

 

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

4.3 Общие правила оформления конструкторской документации

 

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

Пояснительная записка должна быть отпечатана четким, разборчивым шрифтом на листах белой бумаги форматом А4(210х297) ГОСТ 2.301 - 68 с рамкой по формам 5 и 5а ГОСТ 2.106-68. Основную надпись первого и следующих листов следует заполнять в соответствии с ГОСТ 2.104 - 68 по формам 2 и 2а.

Расстояния от края листа до рамки в соответствии с ГОСТ 2.201-80 должны быть:

· левое - 20 мм;

· правое, верхнее и нижнее - 5 мм;

· от рамки до текста:

· левое - 5 мм;

· правое - 3 мм;

· верхнее и нижнее - 10 мм.

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

 

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

 

1. Новиков, Ф.А. Дискретная математика для программистов [Текст]/ Ф.А.Новиков. – СПб: Питер, 2007. – 304 с.

2. Горбатов, В.А. Фундаментальные основы дискретной математики. Информационная математика [Текст]. – М.: Наука. Физматлит, 2000. – 544 с.

3. Иванилова, Т.Н. Дискретная математика. Сборник заданий с примерами решений [Текст]./ О.В.Крайченкова - Красноярск: СибГТУ, -2000. –50 с.

4. Кук Д. Компьютерная математика [Текст]./ Бейз Г – Москва: Наука, 1992.

5. Кузнецов О П. Дискретная математика для инженера.[Текст]./.. Адельсон-Вельский Г. М. - Изд.2, перераб. и доп.— М.: 1988. — 408 с.

6. Логинов В.В. Введение в дискретную математику.[Текст] – Калуга, 1998.

7. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях.[Текст] - М.: Логос, 2000. - 240 с

8. Нефедов В.Н. Курс дискретной математики.[Текст]./., Осипова В.А -М.: МАИ, 1992.

9. СТП 3.4.204 – 01. Требования к оформлению графических документов. – Взамен СТП СТИ-18–90; Введ. 15.02.01. –Красноярск: СибГТУ, 2001.

10. СТП 3.4.204 – 01. Требования к оформлению текстовых документов. – Взамен СТП 17 – 98; Введ. 1.04.01. – Красноярск: СибГТУ, 2001.

Приложение A(справочное) Образец выполнения текстовой части курсовой работы с примером выполнения расчетов

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

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

Кафедра системотехники

 

 

ЗАДАНИЕ

Содержание

 

 

Реферат…………………………………………………………………………..5

 

Введение…………………………………………………………………………6

 

1 Деревья в теории графов. Минимальное остовное дерево……………7

 

2 Решение задачи..………………………………………………………...…….7

 

2.1 Входная и выходная информация…………………………………..7

 

2.2 Схема алгоритма....................................................................................7

 

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

 

2.4 Протокол контрольного расчета…………………………………...8

 

3 Инструкция по работе с программой…………………………………….10

 

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

 

Список использованных источников………………………………………12

 

 

Реферат

 

Расчетно-графическая работа представляет собой решение задачи по расчету минимального остовного дерева. Расчет выполнен с помощью языка программирования Pascal 6.0 на ПК PENTIUM166.

Пояснительная записка включает в 10 страниц текста, 2 распечатки экрана, схему алгоритма, 3 использованных литературных источника.

Ключевые слова: граф, дерево, минимальное остовное дерево.

Цель работы – овладение навыками работы с алгоритмом построения минимального остовного дерева.

Метод исследования – теория графов, алгоритмизация, язык программирования Pascal.

Данная программа позволяет:

1) определить способ задания графа;

2) ввести граф, используя матрицу смежности;

3) рассчитать минимальное остовное дерево;

4) провести тестирование алгоритма.

Введение

Необходимо написать о применении методов теории графов в практических задачах.

 

 

1 Деревья в теории графов. Минимальное остовное дерево

 

Напечатайте текст из учебников или лекций, далее выполните разделы в соответствии с содержанием.

Решение задачи

2.1 Входная и выходная информация

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

 

2.2 Схема алгоритма

Необходимо представить укрупненную блок-схему алгоритма

 

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

Program Di_mat;

Uses crt,graph;

const r=20;

 

var

gfx,gfy:array[1..20] of integer;

matrix: array[1..20,1..20] of integer;

fx:array[1..20] of boolean;

grline: array [1..20] of byte;

gdx,gdy,n,i,j:integer;

d: Real;

 

procedure init;

var graphdriver,graphmode,errorcode:integer;

begin

graphdriver:= detect;

initgraph(graphdriver,graphmode,'');

errorcode:=graphresult;

if errorcode <> grok then

begin

write('Error');

halt;

end;

end;

 

 

procedure DrawGraph(i:Integer);

var

s:string;

begin

circle(gfx[i],gfy[i],r);

settextstyle(1,0,1);

 

settextjustify(1,1);

str(i,s);

outtextxy(gfx[i],gfy[i]-r div 5,s);

end;

 

procedure DrawLink(i,j: Integer);

var

s:string;

begin

gdx:=gfx[j]-gfx[i];

gdy:=gfy[j]-gfy[i];

d:=sqrt(LongInt(gdx)*gdx+LongInt(gdy)*gdy);

gdx:=round(gdx*r/d);

gdy:=round(gdy*r/d);

Line(gfx[i]+gdx,gfy[i]+gdy,gfx[j]-gdx,gfy[j]-gdy);

end;

2.4 Протокол контрольного расчета

Возьмем 6 городов, а длины телефонных кабелей зададим матрицей длин дуг.

 

¥
	¥
		¥
			¥
				¥
					¥

Рисунок 1- Расположение городов с помощью матрицы

 

В результате получается граф показанный на рисунке 2.

Задание выдано ____________________

Руководитель Иванилова Т.Н.

Рисунок 2- Граф

 

Минимальное остовное дерева графа, полученное после расчетов, выглядит так:

 

Рисунок 3- Минимальное остовное дерево

 

Заключение

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

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

 

 

Введение

Перед выполнением задания, которое выдает преподаватель, студент должен овладеть знаниями по «Дискретной математике», навыками работы в операционной системе Windows, в текстовом редакторе Word, в среде программирования Turbo Pascal.

Для контроля подготовленности студента к выполнению работы приведен перечень контрольных вопросов.

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

 

Задания для курсовой работы

1. Создайте программную реализацию алгоритм Тэрри для нахождения компонент связности графа.

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

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

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

5. Создать программную реализацию алгоритма нахождения остовного дерева графа.

6. Создать программную реализацию нахождения минимального расстояния в нагруженном графе.

7. Создать программную реализацию нахождения максимального расстояния в нагруженном орграфе.

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

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

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

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

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

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

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

15. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа в глубину.

16. Создайте обучающую программу, предназначенную для студентов, изучающих алгоритм обхода графа по ширине.

Реализовать:

17. Алгоритм Тэрри нахождения пути в графе из заданной вершины x в заданную вершину y.

18. Алгоритм Тэрри нахождения компонент связности графа.

19. Алгоритм Фронта волны нахождения минимального пути в графе из заданной вершины x в заданную вершину y.

20. Алгоритм Фронта волны нахождения минимального пути в ориентированном графе из заданной вершины x в заданную вершину y.

21. Алгоритм нахождения остовного дерева графа.

22. Алгоритм нахождения минимального остовного дерева в графе.

23. Алгоритм обхода графа в ширину.

24. Алгоритм обхода графа в глубину.

25. Алгоритм нахождения компонент связности графа.

26. Алгоритм расчета числовых характеристик графа.

27. Алгоритм расчета степеней вершин графа.

28. Алгоритм расчета полустепеней исхода и захода графа.

 

 

Математическая постановка решаемой задачи

· Граф – пара множеств V и X - G = (V,X). V – множество вершин, X – множество ребер.

· Петля – ребро вида (v,v).

· Кратные рёбра – одинаковые пары в X.

· Ориентированный граф (орграф D) – граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются <u,v>.

· Степенью вершины V графа G называется число d(v) рёбер графа, инцидентных вершине v. Если d(v) = 1, тогда v – висячая вершина, если d(v) = 0, тогда v –изолированная вершина.

· Полустепенью исхода (захода) вершины v орграфа D называется d⁺(v) – число дуг, исходящих из v (δ^- (v)- число дуг, заходящих в v).

· Маршрутом для графа G (путём для орграфа D) называется последовательность v₁x₁v₂x₂v₃...x_kv_k+1.

· Цепь – незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простая цепь – цепь, в которой все вершины попарно различны.

· Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

· Длина пути – число рёбер (дуг) в маршруте (пути).

· Путь в графе называется минимальным, если он состоит из минимального количества рёбер.

· Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция – длина дуги хÎХ.

· Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.

· Матрица смежности (графа, орграфа): А = [a_ij], V = {v₁…,v_n},

X = {x₁…,x_m}

 

· Матрица инцидентности: B = [b_ij]

(орграфа D)

·

· (графа G)

 

· Матрица достижимости T = [t_ij]

· Матрица связности S = [s_ij]

(орграфа D)

· (графа G)

· Матрица длин дуг

 

· Остовное дерево графа (ОД) – любой связный подграф связного графа, содержащий все вершины и являющийся деревом.

· Минимальное остовное дерево (МОД) – остовное дерево нагруженного графа с минимальной суммой длин дуг содержащихся в нём.