Задачи и алгоритмы дискретной математики
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Кубанский государственный технологический университет
(ФГБОУ ВПО «КубГТУ»)
Кафедра Информационных систем и программирования
Факультет Компьютерных технологий и автоматизированных систем
КУРСОВАЯ РАБОТА
По дисциплине « Дискретная математика»
На тему «Задачи и алгоритмы дискретной математики».
Выполнила студентка группы 12-КБ-ПИ1 Бедросова Ольга Давидовна
Допущен(а) к защите:
Руководитель работы ______________________________
Защищён _____________________ Оценка________________________
(дата)
Члены комиссии ______________________________
______________________________
______________________________
(подпись, дата, расшифровка подписи)
Краснодар
2013
Министерство образования и науки Российской
Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Кубанский государственный технологический университет
(ФГБОУ ВПО «КубГТУ»)
Кафедра Информационных систем и программирования
Факультет Компьютерных технологий и автоматизированных систем
УТВЕРЖДАЮ
Зав. кафедрой Видовский Л.А.
___________________________
(дата, подпись, расшифровка подписи)
ЗАДАНИЕ
на курсовую работу
Студентке Бедросовой Ольге Давидовне группы 12-КБ-ПИ1
факультета Компьютерных технологий и автоматизированных систем
специальности 230700 Прикладная информатика
Тема работы Задачи и алгоритмы дискретной математики.
Содержание задания: Изучить темы «Генерация подмножеств» и «Понятие дерева Штейнера и алгоритмы его нахождения», провести исследования алгоритмов работы с этими объектами, составить программы, которые демонстрируют указанные алгоритмы.
Объём курсовой работы:
а) пояснительная записка стр. 14;
Рекомендуемая литература: Седжвик «Алгоритмы на С++», Скиена С. «Алгоритмы. Руководство по разработке», Окулов С.М. «Дискретная математика. Теория и практика решения задач по информатике»
Срок выполнения курсовой: с 25 сентября 2013г. по 28 декабря 2013г.
Срок защиты:
Дата выдачи задания: с 25 сентября 2013г. по 28 декабря 2013г.
Дата сдачи работы на кафедру: с 25 сентября 2013г. по 28 декабря 2013г.
Руководитель работы ______________________________
(подпись)
Задание принял студент ______________________________
(подпись)
РЕФЕРАТ
Стр. 14, табл. 1 , рис. 0, библ. 3.
ГЕНЕРАЦИЯ ПОДМНОЖЕСТВ, АЛГОРИТМ, ГРАФЫ, ДЕРЕВО ШТЕЙНЕРА
В данной курсовой работе рассмотрены вопросы решения по задачам и алгоритмам дискретной математики. Были рассмотрены такие темы как: «Генерация подмножеств» и «Понятие дерева Штейнера и алгоритмы его нахождения».
Цель курсовой работы – реализация алгоритмов решения данных задач на одном из из языков программирования.
Основными моментами проведённого исследования были:
- исследования алгоритмов работы с этими объектами;
- изучение генерации подмножеств;
- изучение понятия дерева Штейнера;
Проделанная работа даст представление о способах решения приведенных задач и их наглядной реализации.
Содержание
Введение
В данной курсовой работе рассмотрены два вопросы. Первый из них – генерация подмножеств. Второй – дерево Штейнера и алгоритмы его построения.
В работе я рассмотрела следующие понятия: множество, генерация подмножеств, понятие минимального по включению дерева Штейнера; описание и обоснование алгоритма построения всех минимальных по включению деревьев Штейнера, как одного из алгоритмов точного решения задачи Штейнера на графе.
1 Генерация подмножеств
Множество - это совокупность объектов, рассматриваемая как одно целое. Понятие множества принимается за основное, т. е. не сводимое к другим понятиям. Объекты, составляющие данное множество, называются его элементами.
Все элементы множества
Генерация подмножеств
{}
{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 – возвращается результат работы алгоритма: множество всех деревьев Штейнера наименьшего веса
Список используемых источников
- Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд.: пер. с англ. – СПб.: БХВ-Петербург, 2011. – 720 с. Скиена «Алгоритмы».
- Окулов С.М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2008. – 422 с.
- Седжвик Р. Алгоритмы на C++. – Пер. с англ. – М.: Вильямс, 2011. – 1056 с.
Приложение А- листинг программы "Генерация подмножеств"
Исходный код на C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("введите множество");
string[] str = Console.ReadLine().Split(' ');
int b;
int j;
for (int i = 0; i < Math.Pow(2, str.Length); i++)
{
b = i;
j = 0;
Console.Write("{ ");
while (b>0)
{
if (b % 2 == 0)
{
b /= 2;
j++;
}
else
{
b /= 2;
Console.Write(str[j]+" ");
j++;
}
}
Console.WriteLine("}");
}
Console.ReadKey();
}
}
}
Приложение Б- листинг программы "Дерево Штейнера"
Исходный код на C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static void Cheng_mark(int[] mark, int l, int m)
{
if (m < l)
{
int buf = m;
m = l;
l = buf;
}
for (int i = 0; i < mark.Length; i++)
if (mark[i] == m)
mark[i] = l;
}
public static int [ , ] Ostov(int [,] matrix, int n)
{
int[,] re = new int[3, n];
int[] mark = new int[matrix.GetLength(1)];
for (int i = 0; i < matrix.GetLength(1); i++)
mark[i] = i;
int k = -1, t = matrix.GetLength(1)-1, v, kol=0;
while (k < matrix.GetLength(1) - 1)
{
v = -1;
do
{
v++;
k++;
}
while ((v <= t) && (mark[matrix[1, v] - 1] == mark[matrix[0, v] - 1]));
if (matrix[0, v] * matrix[1, v] != 0)
{
Console.WriteLine("{0} {1}", matrix[0, v], matrix[1, v]);
re[0, kol] = matrix[0, v];
re[1, kol] = matrix[1, v];
re[2, kol] = matrix[2, v];
Cheng_mark(mark, mark[matrix[0, v] - 1], mark[matrix[1, v] - 1]);
kol++;
}
}
return re;
}
static void Main(string[] args)
{
#region Ввод
Console.Write(" введите кол-во вершин ");
int n = int.Parse(Console.ReadLine());
Console.Write(" введите кол-во ребер в графе ");
int m = int.Parse(Console.ReadLine());
int[,] p = new int[3, m];
int[] metka = new int[n];
Console.WriteLine("ребро х у вес");
for (int i = 0; i < m; i++)
{
string[] str = Console.ReadLine().Split(' ');
p[0, i] = int.Parse(str[0]);
p[1, i] = int.Parse(str[1]);
p[2, i] = int.Parse(str[2]);
metka[int.Parse(str[0])-1] = 1;
metka[int.Parse(str[1])-1] = 1;
}
int kol = 0;
for (int i = 0; i < n; i++)
if (metka[i] == 0)
kol++;
int vg=n-kol;
int[,] p1 = new int[3, (n - kol) * kol + (kol*kol*(kol-1))/(2*kol)];
Console.WriteLine(" введите вес ребер ");
kol=0;
for (int i = 0; i < n; i++)
if (metka[i] == 0)
for (int j = 0; j < n; j++)
if (metka[j] == 1)
{
Console.Write("{0} {1} ", i + 1, j + 1);
p1[0, kol] = i + 1;
p1[1, kol] = j + 1;
p1[2, kol] = int.Parse(Console.ReadLine());
kol++;
}
for (int i = 0; i < n; i++)
{
if (metka[i] == 0)
{
for (int j = i + 1; j < n; j++)
if (metka[j] == 0)
{
Console.Write("{0} {1} ", i+1, j+1);
p1[0, kol] = i + 1;
p1[1, kol] = j + 1;
p1[2, kol] = int.Parse(Console.ReadLine());
kol++;
}
}
}
#endregion
#region слияние
int[,] p2 = new int[3, p.GetLength(1) + p1.GetLength(1)];
for (int i = 0; i < m; i++)
{
p2[0, i] = p[0, i];
p2[1, i] = p[1, i];
p2[2, i] = p[2, i];
}
kol = 0;
for (int i = m; i < p2.GetLength(1); i++)
{
p2[0, i] = p1[0, kol];
p2[1, i] = p1[1, kol];
p2[2, i] = p1[2, kol];
kol++;
}
Console.WriteLine();
#endregion
#region сортировка
for (int i = 0; i < p2.GetLength(1); i++)
for (int j = i; j < p2.GetLength(1); j++)
if (p2[2, i] > p2[2, j])
{
int buf = p2[0, i]; p2[0, i] = p2[0, j]; p2[0, j] = buf;
buf = p2[1, i]; p2[1, i] = p2[1, j]; p2[1, j] = buf;
buf = p2[2, i]; p2[2, i] = p2[2, j]; p2[2, j] = buf;
}
#endregion
int[,] ostov = Ostov(p2,n-1);
for (int i = 0; i < ostov.GetLength(1); i++)
if(ostov[0,i]!=0)
Console.WriteLine("{0} {1} {2}", ostov[0, i], ostov[1, i], ostov[2, i]);
Console.ReadKey();
}
}
}
- Задачи и виды аудита
- Задачи изучения и прогнозирования Российского товарного рынка
- Задачи изучения трудовых ресурсов Ступинского района
- Задачи и информационная база анализа и диагностики использования производственных основных средств
- Задачи и источники анализа финансового состояния предприятия
- Задачи и источники информации для аудита и ревизии кассы и кассовых операций
- Задачи и источники информации для аудита и ревизии расчетных операций
- Задачи выбора маршрута или сетевые задачи
- Задачи гражданского судопроизводства
- Задачи дальнейшего развития теплоснабжения
- Задачи демографической политики России
- Задачи денежно-кредитной политики РФ по стабилизации денежного обращения
- Задачи для усовершенствования АИС в страховой деятельности
- Задачи, значение, последовательность проведения анализа
