Програмна реалізація розфарбування графів
Граф як сукупність об’єктів з вказаними зв’язками між ними. Матриця суміжності як спосіб його представлення. Постановка задач про розфарбування графів, алгоритм вирішення її методом неявного перебору. Розробка програмної реалізації цього процесу.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | контрольная работа |
Язык | украинский |
Дата добавления | 30.05.2013 |
Размер файла | 509,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
21
Размещено на http://www.allbest.ru/
Вступ
В даній курсовій роботі розглядаються задачі з ледь не повсякденного життя, які зводяться в теорії графів до знаходження хроматичного числа планарних графів та їх оптимального розфарбування.
Вирішення данної проблеми має як теоретичне так і практичне значення, наприклад: для розфарбування політичної карти світу не обійтись і без розфарбування планарних графів (кожен материк відповідає окремому планарному графу, а столиця країни - вершина) що ми розглянемо в пункті 2.4.. Ця тема є досить актуальною і використовуеться як на виробництві, плануванні міста, так і в школах - для складання розкладу занять.
Метою данної роботи є розгляд проблем та задач, що зводяться до знаходження оптимального розфарбування, а отже і хроматичне число; розробка алгоритму, що знаходить оптимальне розфарбування графу та його практичне застосування.
1. Теоретична частина
граф розфарбування програмний
1.1 Основні поняття
Граф - сукупність об'єктів з вказаними зв'язками між ними.
Об'єкти - вершини графу, а зв'язки - дуги та ребра графу. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра. Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини -- це статті, а дуги (орієнтовані ребра) -- посилання на інші статті.
Граф що містить тільки ребра - називається неорієнтованим, а той що містить тільки дуги - орієнтовний, всі ж інші - мішані.
Граф (геометричний граф) -- це фігура на площині, яка складається з непорожньої скінченної множини точок (вершин) і скінченної множини орієнтованих чи не орієнтованих ліній (ребер), що з'єднують деякі пари вершин.Планарний граф -- граф, який може бути зображений на площині без перетину ребер. Хроматичне число графа G -- мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається ч(G).
Петля - дуга чи ребро що сполучає вершину саму із собою.
Якщо пара вершин сполучена кількома ребрами чи дугами одного напрямку то такі ребра чи дуги називають кратними ( || )
Тип графу |
Ребра |
Кратні ребра |
|
Простий граф |
Неорієнтовні |
Ні |
|
Мультиграф |
Неорієнтовні |
Так |
|
Оріентовний граф |
Орієнтовні |
Ні |
|
Орієнтовний мультигаф |
Оріентовні |
Так |
Матриця суміжності - один із способів представлення графа у вигляді матриці. Матриця суміжності графа G зі скінченною кількістю вершин (пронумерованих від 1 до n) - квадратна матриця А розмірності n, в якій значення елемента рівне числу ребер що сполучає i-ву та j-ву вершини.
Размещено на http://www.allbest.ru/
21
Размещено на http://www.allbest.ru/
Мал.1
Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі
Мамтриця інцидемнтності -- одна з форм представлення графа, в якій вказуються зв'язок між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки -- вершинам. Ненульове значення у клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцедентність).
Кожна комірка матриці може набувати трьох значень:
1: якщо ребро виходить з і входить у ;
-1: якщо ребро входить у і виходить з ;
0: якщо між і немає ребра.
Список суміжності - це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною.
Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.
1.2 Постановка задач про розфарбування графів
Задача про розфарбування карти
Знайти оптимальне розфарбування (а отже і хроматичне число) даного планарного графа що відповідає політичній карті світу. Відповідний задачі граф можна побудувати прямо на карті: в середині кожної країни відмітити вершину, яка цю країну представляє («столицю»), а ребро між сусідніми країнами провести через проміжок спільного кордону. Зрозуміло що таким чином ми отримали плоский граф.
Задача про розфарбування карти
Знайти хроматичне число.
Легко придумати карту, для якої трьох кольорів буде недостатньо. Приклад такої карти приведено на мал. 2. Не важко зрозуміти, що цій карті відповідає граф, хроматичне число якого рівне 4.
Мал. 2
Спроби придумати карту, для якої недостатньо і чотирьох кольорів, довгий час не приводили до успіху. Тому й дійсно виникла наступна гіпотеза.
Гіпотеза про чотири кольори
Хроматичне число любого планарного графа не перевищує 4.
Теорема Хівуда
Хроматичне число будь-якого планарного графа не перевищує 5.
Для доведення нам знадобиться
Лема про вершину степеня <5
В любому звичайному плоскому графі знайдеться вершина, степінь якої не перевищує 5.
Доведення. Достатньо показати, що потрібна вершина знайдеться в одній з компонент звязності заданого графа G. Отже, можнa вважати, що граф G звязний. Припустимо і . По відповідності про кількість ребер з теореми Ейлера про плоскі графи
Оскільки сума n доданків менше 6n, хоча б одне з додаваних менше 6 (тобто не більше 5 так як степінь вершини -- натуральне число). Отже, існує вершина v графа G така, що ??(??)?5.
Нехай G -- планарний граф. Можно вважати, що граф G э звичайним (петлі і кратні ребра не впливають на хроматичне число) і плоским (оскільки хроматичне число не змінюється при ізоморфізмі). Припустимо і будемо доводити індукцією по n. База індукції очевидна: якщо звичайний граф G містить одну вершину, то .
Крок індукції. Нехай n>1. Виберемо в графі G вершину v степеня ? 5 (така вершина існує за тільки-що деведеню лемою). Розглянемо граф G --v. В ньому n --1 вершина, а отже, по умові індукції існує правильне розфарбування f графа G --v не більше ніж 5 кольорами.
Якщо для розфарбування вершин, суміжних з v, використано менше 5 кольорів, то розфарбування f можна доповнити до правильного розфарбування графа G не більш як 5 кольорами, розфарбувавши вершину v «не зайнятим» кольором. Тому далі можна вважати, що для розфарбування вершин, суміжних з v, використані всі 5 кольорів. В даному випадку з v суміжні рівно 5 вершин, позначимо їх , , , , . У порядку слідування за годинниковою стрілкою відносно v (див. мал.3).
Так як ми розглядаємо G як плоский граф, тобто як фігуру на площині, ми маємо право користуватись геометричними міркуваннями.
Мал.3
Будемо вважати, що ,…,. Позначимо через підграф графа G, породжений усіма вершинами u , що
. В нашому випадку, граф містить вершини і . Розглянемо 2 випадки.
Випадок 1: вершини і лежать в різних компонентах звязності графа . Нехай К -- компоента звязності в , що містить вершину .
Перепозначимо f на K, перефарбувавши вершини кольору 1 в 3-й, і навпаки. Нова функція f теж буде правильним розфарбуванням графа G -- v. Дійсно, «нові» вершини кольору 1 не суміжні ні між собою (оскільки і раніше мали один колір) ні зі старими вершинами кольору 1 (знаходяться в різних компонентах графа ). Теж саме справедливо і для вершин кольору 3, а для вершин інших кольорів нічого не змінилось.
Отже, ми побудували правильне 5-розфарбування графа G -- v, при якому ні одна з вершин, суміжних з v в графі G, не має кольору 1 (в результаті перефарбування вершина поміняла колір на 3, а вершини , , , зберегли колір). Отже, можна зафарбувати вершину v в колір 1, отримуючи правильне 5-розфарбування графа G, що і вимагалось.
Випадок 2: Вершини і лежать в одній і тій самій компоненті звязності графа . Отже, у графі G існує простий (,) ланцюг, усі вершини якої мають кольори 1 і 3. Додавши до цього ланцюга ребра (,) і (,), отримаємо простий цикл C (виділений на мал.4 червоним), обмежуючий частину площини, яка містить рівно одну з вершин і . Розглянемо підграф графа G, породжений усіма вершинами кольорів 2 та 4. В даному випадку, містить вершини і .
Мал. 4
Припустимо, що вершини і лежать в одній компоненті звязності графа . Тоді їх можна поеднати ланцюгом, що проходить тільки через вершини графа . З геометричної точки зору, цей ланцюг - лінія, що поєднує точки і , і вона повинна перетнути цикл C як замкнуту лінію, оскільки одна з точок , знаходиться всередині, а інша - поза областю, обмеженої циклом С. Оскільки граф G плоский, спільна точка ланцюга і цикла може бути лише вершина графа. Але в циклі С немає жодної вершини кольору 2 або 4, ми дійшли протиріччя.
Звідси слідує і лежать в різних компонентах звязності графа . Аналогічно випадку 1, перефарбуємо компоненту звязності цього графа, що містить вершину , помінявши кольори 2 і 4 місцями.
Отримане при цьому розфарбування буде правильним 5-розфарбуванням графа G -- v, при цьому серед суміжних з v вершин не буде вершини кольору 2. Розфарбувавши v в колір 2, отримаємо правильне 5-розфарбування графа G.
Теорема доведена.
Теорема про чотири кольори
Теорема Хівуда була доведена в 1890 р. Понизити верхню планку для хроматичного числа будь-якого планарного графа з 5 до 4, тобто підтвердити гіпотезу про чотири кольори, не вдавалось ще майже 90 років. В 1969 р. задача була зведена до розгляду кінцевого, але досить великого числа коннкретних випадків, пізніше їх число було скорочено до «всього лиш» 1482. Нарешті, в 1976 р. К.Аппель і В.Хейкен за допомогою компьютерної програми розібрали всі ці конкретні випадкии (витративши на це приблизно 2000 годин роботи потужного на той час комп`ютера). В результаті вони довели наступну теорему.
Теорема про чотири кольори
Хроматичне число будь-якого планарного графа не перевищує 4.
Доведення цієї теореми стало першим випадком «комп`ютерного» вирішення важкої і давно стоявшої суто математичної проблеми. Повторити доведення К.Аппеля і В.Хейкена в рамках данного курсу неможливо, тому приводимо її без доведення.
1.3 Алгоритми розв`язання задач розфарбування графів
Алгоритм розфарбування графу методом неявного перебору
Робота алгоритму поділяється на дві фази.
Під час першої будується початкова допустима розфарбування графа за наступним правилом: перша вершина фарбується в перший колір, а далі для кожної вершини вибирається мінімальний за номером колір, такий щоб ніяка із суміжних з даною раніше забарвлених вершин не мала цього кольору.
Під час другої фази, якщо це можливо, виходить кращe розфарбування, що використовує менше число кольорів. На першому кроці другої фази відшукується перша за номером вершина, пофарбована у колір, від якого ми хочемо позбутися. І з неї здійснюється так званий крок повернення, а саме - в множині вершин, суміжних з даною, з меншим, ніж у неї, номером знаходимо максимальну (вона була пофарбована пізніше за інших, нехай це x-а вершина) і намагаємося перефарбувати її в інший допустимий колір з номером більшим за її власний, але меншим номера " зайвого " кольору. Якщо це вдається, то далі за правилом першої фази перефарбовуються наступні вершини з (х +1)-ої до кінця. Якщо жодна з них не потребують кольору, від якого ми позбавляємося, отже ми досягли оптимальніше розфарбування з меншою кількістю кольорів і зупиняемося або починаемо роботу по алгоритму з початку.
А якщо якась вершина зажадає - здійснимо крок повернення з неї. У ситуації, коли та сама х-а вершина не може бути перефарбована в інший допустимий колір - відразу ж робимо крок повернення з неї. Алгоритм завершує роботу, якщо на кроці повернення досягається перша вершина.
Як видно, під час такого перебору вершин здійснюється рух по дереву пошуку в глибину. Незважаючи на те, що алгоритм переборний, він анітрохи не гірше інших відомих методів і цілком ефективний.
1.4 Деякі задачі що зводяться до задачі розфарбування графів
Задача скаладання розкладу
Для вирішення цієї задачі потрібно знайти хроматичне число і оптимальне розфарбування графа. Потрібно прочитати кілька лекцій декільком групам студентів. Деякі з лекцій не можуть читатися одночасно - наприклад, тому, що їх читає один і той же лектор, або їх треба читати одній і тієї же групи студентів, або вони повинні проходити в одному і тому ж комп'ютерному класі. Потрібно скласти розклад так, щоб читання всіх лекцій зайняло мінімально можливий час (як «одиниці часу» в даній задачі природно розглядати одну пару). Перекладемо це завдання на мову графів. Побудуємо граф G, в якому вершини відповідають лекціям та дві різні вершини суміжні тоді і тільки тоді, коли відповідні лекції не можуть читатися одночасно. Очевидно, що будь-яка правильне розфарбування графа G визначає допустимий розклад (якщо при цьому розфарбовуванні використано k кольорів, то для всякого i = 1, 2, ...,k вершини, розфарбовані i-м кольором, дають список лекцій, які треба читати на i-й парі). І навпаки, будь-який допустимий розклад визначає правильне розфарбування графа G. Таким чином, складання оптимального розкладу зводиться до знаходження оптимального розфарбування побудованого нами графа.
Розглянемо приклад завдання на складання розкладу. У студентських групах КН-101 і КН-102 треба провести заняття з алгебри, дискретної математики, математичного аналізу та історії України (по одному заняттю по кожному предмету). Заняття по кожному предмету проводяться з кожною групою окремо. Заняття з алгебри та з дискретної математики веде викладач X, з математичного аналізу - викладач Y, з історії Росії - викладач Z. Знайти мінімальне число пар, в які можна «укласти» всі заняття, і скласти відповідний розклад.
Рішення. Побудуємо граф з вершинами А1, А2, Д1, Д2, Ml, М2, І1 і І2 (літера відповідає предмету, а цифра - номеру групи). З'єднаємо ребрами вершини, що відповідають парам, які не можна проводити одночасно. Отримаємо граф, зображений на мал. 5 ліворуч. Вершини А1, А2, Д1 і Д2 цього графа породжують в цьому графі підграф, ізоморфний графу . Отже, хроматичне число нашого графа не менше 4. На мал. 5 праворуч вказана правильне розфарбування нашого графа в 4 кольори. Отже, хроматичне число графа дорівнює 4, тобто всі заняття можна провести за 4 пари. Відповідний розклад вказано в таблиці.
Мал. 5
КН-101 |
КН-102 |
||
1 пара |
Алгебра |
Математичний аналіз |
|
2 пара |
Математичний аналіз |
Алгебра |
|
3 пара |
Історія України |
Дискретна математика |
|
4 пара |
Дискретна математика |
Історія України |
Задача розподілу обладнання
Друге завдання, яке ми розглянемо, - завдання розподілу обладнання. Є деяка кількість робіт і механізмів для їх здійснення. Для виконання кожної роботи потрібно один і той самий час. При цьому жоднен з механізмів не може бути зайнятий одночасно більше ніж в одній роботі. Потрібно розподілити механізми так, щоб загальний час виконання робіт було мінімально можливим.
Для перекладу цього завдання на мову теорії графів розглянемо граф G, вершинами якого є роботи, причому дві різні вершини суміжні тоді і тільки тоді, коли для виконання відповідних робіт потрібно хоча б один загальний механізм. При правильному розфарбовуванні цього графа вершини, розфарбовані одним і тим же кольором, відповідають роботам, які можна проводити одночасно. Тому завдання зводиться до знаходження оптимального розфарбування графа G. Розглянемо приклад. На підприємстві планується виконати 8 робіт ,,…,. Для виконання цих робіт необхідні механізми ,,…,. Використання механізмів для кожної з робіт визначається наступною таблицею:
Механізм |
Робота |
||||||||
+ |
+ |
+ |
+ |
||||||
+ |
+ |
||||||||
+ |
+ |
+ |
|||||||
+ |
+ |
+ |
+ |
||||||
+ |
+ |
+ |
|||||||
+ |
+ |
+ |
Жоден із механізмів не може бути використаний одночасно на двох роботах. Виконання кожної роботи займає 1 годину. Як розподілити механізми так, щоб сумарний час виконання всіх робіт був мінімальним і який цей час?
Рішення. Розглянемо граф G, вершинами якого є плановані роботи ,,…,, а ребра з'єднують роботи, в яких бере участь хоча б один загальний механізм (і які, з цієї причини, не можна проводити одночасно). Цей граф зображений на мал. 6. Вершини ,,, породжують підграф графа G ізоморфний . Отже, .
Цифри в дужках на мал. 6 вказують правильну розмальовку графа G в 4 кольори. Отже, . Таким чином, всі роботи можна виконати за 4 години. Для цього, відповідно до знайденого розфарбування графа G, треба в 1-у годину виконувати роботи і , у 2-й - роботи і , в 3-й - роботи і , в 4-й - роботи і .
Мал. 6
2. Практична частина
Задання графу матрицею суміжності:
Uses crt;
Type MS=array[1..10,1..10]of Integer;
Var
a:MS; n,i,j:Integer;
Begin
ClrScr;
Write('Введіть кількість вершин: ');
Readln(n);
Writeln('Введіть матрицю суміжності: ');
For i:=1 to n do
Begin
For j:=1 to n do
Begin
GoToXY(j*2,i+3);
Write(' ');
Read(a[i,j]);
end;
Writeln;
end;
Задання графу списком суміжності:
Type GList = array [1..10] of record
Count: Integer;
List: array[1..10] of Integer;
end;
CList=array[1..10] of Byte;
Var Graph: GList; Color:Clist;
2.1 Програмна реалізація алгоритму розфарбування графів
Procedure GetColor;
Begin
For i:=1 to n do
Color[i]:=1;
For i:=2 to n do
begin
j:=1;
While (j<=Graph[i].Count)and(Graph[i].List[j]<i) do
Begin
If Color[i]=Color[Graph[i].List[j]] Then
Begin
Color[i]:=Color[i]+1;
j:=1;
end
Else
j:=j+1;
end;
end;
end;
2.2 Контрольні приклади
Повний код програми:
Program algorytmGraf;
Uses crt;
Type GList=array[1..10] of record
Count:Integer;
List:array[1..10] of Byte;
end;
CList=array[1..10] of Byte;
Var Graph:GList; Color:CList; i,j,n:Byte; G:File of GList; s:string;
Procedure GetColor;
Begin
For i:=1 to n do
Color[i]:=1;
For i:=2 to n do
begin
j:=1;
While (j<=Graph[i].Count)and(Graph[i].List[j]<i) do
Begin
If Color[i]=Color[Graph[i].List[j]] Then
Begin
Color[i]:=Color[i]+1;
j:=1;
end
Else
j:=j+1;
end;
end;
end;
Procedure Vvid_K;
Begin
Write('Введіть кількість вершин: ');
Readln(n);
For i:=1 to n do
Begin
Write('Введіть кількість вершин суміжних з ',i,'-ю: ');
Readln(Graph[i].Count);
Writeln('Введіть номери вершин суміжних з ',i,'-ю:');
For j:=1 to Graph[i].Count do
Begin
Write(j,'-а вершина: ');
Readln(Graph[i].List[j]);
end;
end;
Writeln('Зберегти введений граф у файл? [Y/N]');
Case ReadKey of
'Y','y':Begin
Write('Введіть назву файлу: ');
Readln(s);
Assign(G,s);
Rewrite(G);
Write(G,Graph);
Close(G);
end;
'N','n':Begin
end;
end;
end;
Procedure Vuvid;
Begin
For i:=1 to n do
begin
TextColor(Color[i]);
Write(i,': ');
For j:=1 to Graph[i].Count do
Begin
TextColor(Color[Graph[i].List[j]]);
Write(Graph[i].List[j],' - ');
end;
Writeln;
end;
Readkey;
end;
BEGIN
Repeat
TextColor(15);
ClrScr;
Writeln('1. Завантажити граф з файлу');
Writeln('2. Ввести новий граф з клавіатури');
Writeln('3. Знайти оптимальне розфарбування');
Writeln('4. Вихід з програми');
Case ReadKey of
'1':Begin
Write(' Введіть назву файлу: ');
Readln(s);
Assign(G,s);
Reset(G);
Read(G,Graph);
end;
'2':Vvid_K;
'3':Begin
GetColor;
Vuvid;
end;
'4',#27:Begin
Break;
Close(G);
end;
end;
Until False;
end.
Мал.7
Якщо ввести в програму планарний граф з мал.7
Програма виведе нам наступний результат:
Висновок
В ході виконання даної курсової роботи було розглянуто та роз'яснено багато прикладів застосування деяких аспектів теорії графів, а саме - розфарбування графів. Був написаний код програми на мові Turbo Pascal що для введеного з клавіатури або завантаженого з файлу графа знаходить оптимальне розфарбування вершин.
Наведені приклади задач які розв'язуються розфарбуванням графу побудованого з їх умов, у часних випадках, для кожного за своєю логікою.
Список використаної літератури
граф розфарбування програмний
1. Верников Б.М., Шур А.М. «Алгебра і дискретна математика» 2004 р.(324с)
2. Спекторський І.Я. «Дискретна математика» 2004 р.(220c)
3. Березина Л.Ю. «Графы и их применение: Пособие для учителей» 1979р.
Размещено на Allbest.ru
...Подобные документы
Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
курсовая работа [335,6 K], добавлен 15.06.2015Загальне значення графу. Алгоритми обходу графів. Матриця суміжності і список суміжності. Граф як структура даних. Використання двовимірного масиву чисел. Додавання нового зв'язку між заданою парою існуючих вершин, нової вершини разом з зв'язками.
отчет по практике [132,7 K], добавлен 29.06.2012Формулювання умови задачі в термінах теорії графів. Метод вирішення задачі й алгоритм написання програми на мові C++. Розробка інструкції користувача, розрахунок контрольних прикладів й аналіз результатів. Приклади практичного застосування програми.
курсовая работа [526,2 K], добавлен 31.01.2014Визначення та способи представлення графів. Основні алгоритми на графах. Побудова мінімального остового дерева. Алгоритми Прима та Дейкстри. Модель Флойда-Уоршалла. Огляд можливостей мови програмування. Опис функцій програмної моделі, інтерфейс програми.
дипломная работа [563,7 K], добавлен 03.08.2014Створення алгоритму програмної моделі розкладу в учбовому закладі для ефективного вирішення завдань автоматичного складання розкладу, шляхом підбору найбільш оптимальних варіантів. Шляхи реалізації розробленого алгоритму в середовищі Mathemetica 5.0.
дипломная работа [5,0 M], добавлен 25.10.2012Поняття черги в програмуванні, основні операції з чергою і їх реалізація. Опис алгоритму й специфікація програми. Розробка додатку з використанням задачі Ларсона по опису зв'язного неорієнтованого графа. Алгоритм розв’язку і результати виконання програми.
курсовая работа [1,1 M], добавлен 14.09.2012Програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Загальні відомості про графи. Особливості роботи в середовищі. Опис структури програми та програмних засобів. Схема програмної реалізації алгоритму Дейкстри.
курсовая работа [676,7 K], добавлен 20.03.2011Програмна робота з графами: операції їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Основи пошуку в графі в різних напрямках. Розбиття множини вершин на класи еквівалентності за відношенням зв'язності графу.
лабораторная работа [8,3 K], добавлен 11.05.2011Розробка і обґрунтування технічного завдання, вимоги до програмної реалізації та користувача. Можливі варіанти зміни та вдосконалення програми. Початок загального алгоритму вирішення задачі. Структурні зв’язки між функціями програми, її тестування.
курсовая работа [1,8 M], добавлен 14.03.2013Відомі підходи до реалізації потокового шифрування даних. Регістр зсуву з оберненими зв’язками. Комбінуючий та фільтруючий генератор. Потоковий шифр Alpha1. Розробка структурної схеми алгоритму шифрування Alpha1. Розробка блоку керування пристрою.
курсовая работа [185,6 K], добавлен 09.04.2013Огляд суті гри "Доміно", характеристика її існуючих програмних реалізацій. Розробка евристичного алгоритму для розв’язання ігрової ситуації "Доміно". Програмна реалізація алгоритму мовою програмування високого рівня C#. Отладка оціночної функції.
курсовая работа [1,4 M], добавлен 14.05.2012Поняття про сайт, його основні функції, класифікація, програмна розробка та створення сайтів у візуальних редакторах. Програмна реалізація додатку. Розробка адмін-панелі. Вимоги щодо відстані між бічними поверхнями відеотерміналів. Охорона праці.
дипломная работа [2,1 M], добавлен 18.11.2014Редагування за допомогою текстового редактора NotePad вхідного файлу даних. Програмна реалізація основного алгоритму з використанням засобів об'єктно-орієнтованого програмування. Об’ява та опис класів і об'єктів. Розробка допоміжних програмних засобів.
курсовая работа [69,4 K], добавлен 14.03.2013Розробка структурної схеми. Опис основних елементів мікропроцесора. Вибір підходящої структури процесорного елемента та його опис. Реалізація пристрою управління. Розробка мікропрограми та загальний алгоритм виконання процесором команди SBR Rm, B.
контрольная работа [83,6 K], добавлен 04.06.2009Вибір мови програмування, історія Delphi. Граф як множина точок та способи їх з’єднання. Типи матриць, за допомогою яких детально описується орієнтований граф. Дескриптори, користування API функціями. Історія головоломки про Кенігсберзькі мости.
курсовая работа [2,0 M], добавлен 14.09.2012Розробка програми для реалізації системи, що забезпечує автоматичне управління та моделювання зміни музичних програм на радіостанції з використанням засобів Microsoft Visual. Програмна реалізація інтерфейсу та процесу моделювання роботи системи.
курсовая работа [1,7 M], добавлен 08.01.2012Дослідження етапів розробки програмної реалізації криптографічного алгоритму RC5. Опис об'єкту, що потребує захисту: операційне середовище, тип програмного забезпечення. Блок-схема алгоритму функціонування програми криптозахисту. Листінг тесту програми.
курсовая работа [4,4 M], добавлен 28.10.2010Основні концепції компонентної розробки прикладних задач: com/dcom, Java Beans, corba, .net. Розробка стратегії гри для кожної категорії учасників, компонентів. Програмна реалізація спроектованої системи, обґрунтування вибору використовуваних засобів.
курсовая работа [1,0 M], добавлен 11.11.2014Алгоритм покриття за методом "мінімальній стовпець - максимальний рядок". Підпрограми основного алгоритму. Розробка програми сортування методом простих включень (бульбашковим методом). Словесний опис алгоритму, його контрольний приклад та ефективність.
курсовая работа [36,4 K], добавлен 06.03.2013Характеристика середовища програмування Microsoft Visual C++ та бібліотеки класів MFC. Знаходження коефіцієнтів при невідомих за допомогою методу найменших квадратів. Створення програми для вирішення задачі обраним методом, її алгоритм та інтерфейс.
курсовая работа [434,8 K], добавлен 20.01.2014