Задачи и алгоритмы дискретной математики

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

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

учреждение высшего профессионального образования 

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

(ФГБОУ ВПО «КубГТУ»)

 

Кафедра    Информационных систем и программирования

Факультет    Компьютерных технологий и автоматизированных систем

 

 

 

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

 

 

По дисциплине « Дискретная математика»             

На тему «Задачи и алгоритмы дискретной математики».

 

Выполнила студентка группы    12-КБ-ПИ1       Бедросова Ольга Давидовна

Допущен(а) к защите:

Руководитель работы __________________________________Е.А.Симоненко

                                                           (подпись, дата, расшифровка подписи)

Защищён _____________________         Оценка________________________

(дата)

 

Члены комиссии ______________________________________Е.А.Симоненко

______________________________________________________А.Г.Волик

_____________________________________________________Ю.С.Носова

(подпись, дата, расшифровка подписи)

 

 

 

 

 

 

 

 

 

 

 

 

 

Краснодар

2013

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

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

учреждение высшего профессионального образования 

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

(ФГБОУ ВПО «КубГТУ»)

 

Кафедра    Информационных систем и программирования

Факультет    Компьютерных технологий и автоматизированных систем

 

 

УТВЕРЖДАЮ

Зав. кафедрой     Видовский Л.А.

___________________________

(дата, подпись, расшифровка подписи)

 

 

ЗАДАНИЕ

на курсовую работу

Студентке Бедросовой Ольге Давидовне группы  12-КБ-ПИ1

факультета     Компьютерных технологий и автоматизированных систем

специальности                 230700 Прикладная информатика

Тема работы  Задачи и алгоритмы дискретной математики.

 

Содержание задания: Изучить темы «Генерация подмножеств» и «Понятие дерева Штейнера и алгоритмы его нахождения», провести исследования алгоритмов работы с этими объектами, составить программы, которые демонстрируют указанные алгоритмы.

Объём курсовой работы:

а) пояснительная записка  стр. 14;

Рекомендуемая литература: Седжвик «Алгоритмы на С++», Скиена С. «Алгоритмы. Руководство по разработке», Окулов С.М. «Дискретная математика. Теория и практика решения задач по информатике»

Срок выполнения курсовой:          с 25 сентября 2013г.  по 28 декабря 2013г.

Срок защиты:                               с 25 сентября 2013г.  по 28 декабря 2013г.

Дата выдачи задания:                     с 25 сентября 2013г.  по 28 декабря 2013г.

Дата сдачи работы на кафедру: с 25 сентября 2013г.  по 28 декабря 2013г.

Руководитель работы ________________________________Е.А.Симоненко

(подпись)

Задание принял студент _______________________________О.Д. Бедросова

(подпись)

 
РЕФЕРАТ

 

Стр. 14, табл. 1 , рис.  0, библ.  3.

ГЕНЕРАЦИЯ ПОДМНОЖЕСТВ, АЛГОРИТМ,  ГРАФЫ, ДЕРЕВО ШТЕЙНЕРА

В данной курсовой работе рассмотрены вопросы решения по задачам и алгоритмам дискретной математики. Были рассмотрены такие темы как: «Генерация подмножеств» и «Понятие дерева Штейнера и алгоритмы его нахождения».

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

Основными моментами проведённого исследования были:

• исследования алгоритмов работы с этими объектами;
• изучение генерации подмножеств;
• изучение понятия дерева Штейнера;

Проделанная работа даст представление о способах решения приведенных задач и  их наглядной реализации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

 

 

 

 

 

1 Генерация подмножеств

 

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

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

           Генерация подмножеств множества  может пригодиться, допустим, в логике  игры, когда из набора персонажей  необходимо выбрать случайную  их группу. Допустим, имеется множество M = {1, 2, 3}. Все подмножества множества M (их совокупность называют булеаном) следующие:

{}

{1}

{2}

{3}

{1, 2}

{1, 3}

{2, 3}

{1, 2, 3}

Первым в списке идет пустое множество, которое является подмножеством любого множества. Последний — исходное множество (множество является подмножеством самого себя).

          Существует величина мощность множества, характеризующая количество элементов множества. Так вот, количество подмножеств множества можно вычислить по формуле 2^n, где n — мощность множества. У множества M количество подмножеств равно 2^3 = 8

          Программно сгенерировать все  подмножества множества, на самом  деле, очень просто. Например, можно  воспользоваться Кодом Грея.

 Код Грея для n бит может быть рекурсивно построен на основе кода для n–1 бит путём переворачивания списка бит (то есть записыванием кодов в обратном порядке), конкатенации исходного и перевёрнутого списков, дописывания нулей в начало каждого кода в исходном списке и единиц — в начало кодов в перевёрнутом списке. Так, для генерации списка для n = 3 бит на основании кодов для двух бит необходимо выполнить следующие шаги:

Коды для n = 2 бит:	00, 01, 11, 10
Перевёрнутый список кодов:		10, 11, 01, 00
Объединённый список:	00, 01, 11, 10	10, 11, 01, 00
К начальному списку дописаны нули:	000, 001, 011, 010	10, 11, 01, 00
К перевёрнутому списку дописаны единицы:	000, 001, 011, 010	110, 111, 101, 100

        

Но есть способ еще проще, в основе которого лежит бинарный или двоичный код. Рассмотрим числа в диапазоне 0..2^n-1 в двоичной системе счисления с разрядностью n (увеличив при необходимости незначащими нулями):

0: 000

1: 001

2: 010

3: 011

4: 100

5: 101

6: 110

7: 111

Каждый из этих двоичных кодов можно использовать как маску подмножества, то есть, единица в i-ом бите характеризует наличие i-го элемента множества в подмножестве, ноль — отсутствие. Например:

101 = {1, 3}

Таким образом, для генерации подмножеств необходимо организовать цикл от 0 до 2^n-1, на каждой итерации представить значение счетчика в виде бинарного кода, на основе его составить подмножество.

 

 

 

 

 

 

2 Дерево Штейнера и алгоритм его построения

Связный ациклический подграф, вершины которого содержат все

терминальные вершины, называется деревом Штейнера.

Дерево Штейнера называется минимальным по включению, если

подграф, получаемый из этого дерева в результате удаления любой его вершины или любого его ребра, не является деревом Штейнера.

Алгоритм вычисления всех минимальных по включению деревьев

Штейнера

 

Обозначение	Пояснение
n	Количество вершин исходного графа G
k	Номер уровня, количество ребер подграфа, номер итерации С
fk	Семейство всех  k–реберных потенциальных кандидатов
Ck	Семейство всех k–реберных кандидатов
Lk	Семейство всех k–реберных ациклических подграфов, не содержащих компонент Штейнера

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ш

Таблица 1. Обозначения алгоритма

 

 

 

 

 

          Псевдокод алгоритма

Вход: G = (V,E,w) – связный неориентированный взвешенный граф,

w : E ! R+ — весовая функция,

T ✓ V — подмножество терминальных вершин,

S0 — одно  из минимальных по включению  деревьев Штейнера.

Выход: S – семейство всех деревьев Штейнера наименьшего веса.

1: W0 := Вес(S0);

2: S := {S0};

3: n := |V |;

4: L0 := {?};

5: k := 0;

6: Цикл пока  k<n*1 и Lk 6= ?

7: k := k + 1;

8: C

fk := {A 2 P(E)|lexmaxN_(A) 2 Lk"1};

9: Ck := {C 2 C

fk|N_(C) ✓ Lk"1};

10: Lk := ?

11: Цикл по  всем A 2 Ck

12: Если A —- ациклический, не содержащий КШ, то

13: Lk := Lk [{A};

14: end Если

15: Если A —- ациклический, содержащий КШ, то

16: W⇤ := Вес(A);

17: Если W⇤ = W0 и A /2 S, то

18: S := S [{A};

19: end Если

20: Если W⇤ < W0, то

21: S := {A};

22: W0 := W⇤;

23: end Если

24: Конец  если W⇤ < W0

25: end Если

26: Конец  если A —- ациклический, содержащий  КШ

27: end Цикл пока

28: Конец  цикла по всем A 2 Ck

29: end Цикл пока

30: Конец  цикла пока k<n*1 и Lk 6= ?

31: Возврат S;

Пояснения к псевдокоду алгоритма.

Шаг 1 – определяется вес W0 минимального по включению дерева Штейнера S0. Подграф S0 — это одно из минимальных по включению деревьев Штейнера. Метод, с помощью которого получен подграф S0, не фиксируется. Например, один из возможных способов получить S0 следующий:

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

2. К полученному  остову применить алгоритм «стрижка  Штейнера».

Шаг 2 — текущее семейство деревьев Штейнера наименьшего веса инициализируется подграфом S0.

Шаг 3 — определяется количество вершин исходного графа.

Шаг 4 — строятся все 0-рёберные подграфы. Такой подграф один: подграф, множество рёбер которого пусто.

Шаг 5 — инициализируется счётчик итераций.

Шаг 6 — условия k<n*1 и Lk 6= ? определяют условие выполнения очередной итерации, реализующей построение необходимых конструкций следующего уровня из ациклических подграфов, предшествующего уровня, не содержащих компонент Штейнера.

Шаг 7 — определяет номер следующей итерации (номер следующего уровня).

Шаг 8 — формирует C

fk - семейство k-рёберных потенциальных кандидатов, непосредственно следующих за подграфами из семейства Lk"1

Шаг 9 – из потенциальных кандидатов семейства C fk отбираются кандидаты, формирующие семейство Ck/

Шаг 10 – изначально семейство ациклических подграфов текущего уровня, не содержащих компонент Штейнера – пусто.

Шаг 11 – цикл по всем подграфам-кандидатам k-го уровня.

Шаг 13 – ациклический подграф, не содержащий компоненты Штейнера (шаг 12), добавляется в семейство Lk.

Шаг 14 – если текущий подграф A — ациклический и содержит компоненту Штейнера, то

Шаг 15 – вычислить вес подграфа A.

Шаг 16-17 – если вес текущего подграфа равен порогу W0 и подграф A не включён в семейство решений задачи, то добавить его в семейство S.

Шаг 18 – если вес текущего подграфа меньше порога W0, то

Шаг 19 – текущее подмножество дерева Штейнера наименьшего веса инициали-

зируется подграфом A.

Шаг 20 – в качестве весового порога использовать вес подграфа A.

Шаг 25 – возвращается результат работы алгоритма: множество всех деревьев Штейнера наименьшего веса

 

 

 

 

 

 

Список используемых источников

1. Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с. Скиена «Алгоритмы».
2. Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2008. – 422 с.
3. Седжвик Р. Алгоритмы на C++. – Пер. с англ. – М.: Вильямс, 2011. – 1056 с.