Міністерство освіти і освіти України.
МОСКОВСЬКИЙ ДЕРЖАВНИЙ АВІАЦІЙНО-ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ ім. К.Е. ЦІОЛКОВКОГО
КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи на тему: "Розробка алгоритмів і програм виконання операцій над послідовними і пов'язаними уявленнями структур даних"
по курсу "Теорія алгоритмів та обчислювальних методи"
Керівник: Авдошин С.М.
Дата здачі: _____________
Підпис: _____________
Студент: Ліцентов Д. Б.
Група: 3ІТ-2-26
Москва
1998
1. Постановка завдання.
Дано:
Два Орграф X і Y з N вершинами (X в послідовному поданні, Y впов'язаному поданні) без кратностей. Дуги Орграф утворюють неврегульовані списки. Орграф задаються неупорядкованими спискамисуміжних вершин - номерів вершин, до яких ведуть ребра з кожної вершиниграфа.
Потрібно:
Виконати над ребрами Орграф операцію різниці (X/Y). У результатівиконання цієї операції новий Орграф Z визначається у зв'язаномуподанні, а старий Орграф X виправляється в послідовномуподанні.
Особливості подання даних:
Послідовне подання даних: одновимірний масив Array, що міститьдва цілочисельних поля I (містить номер вершини, з якої виходить дуга)і J (містить номер вершини, до якої входить дуга).
| Array [_] | | I | | J |
| Array [1] | | From | | To |
| Array [2] | | From | | To |
| ... | | From | | To |
| Array [N] | | From | | To |
N - кількість дуг в Орграф X.
Пов'язане подання даних: одновимірний масив Spisok покажчиків наструктуру index, що представляє собою елемент списку, а що містить поле:цілочисельне index (містить номер вершини, до якої входить дуга) і Next
- Покажчик на структуру Spisok, яке вказує на наступний елемент списку
| Spisok [_ | NEXT | | inde | next | | inde | next | | Inde | Next |
|] | | | X | | | x | | | x | |
| Spisok [1 | | | To | | | ... | | | To | NULL |
|] | | | | | | | | | | |
| ... | | | To | | | ... | | | To | NULL |
| Spisok [N | | | To | | | ... | | | To | NULL |
|] | | | | | | | | | | |
N - кількість вершин у графі Y, Z.
2. Зовнішнє опис програми.
Введення інформації про неорієнтовані графах відбувається з файлу, форматякого повинен бути наступним:
N
X11 X12 ... X1k1 0
X21 X22 ... X2k2 0
...
XN1 XN2 ... XNkN 0
Y11 Y12 ... Y1k1 0
Y21 Y22 ... Y2k2 0
...
YN1 YN2 ... YNkN 0де N - число вершин у графах
Xij - номер чергової вершини суміжній i у графі X (i = 1 .. N, j = 1 .. ki)
Yij - номер чергової вершини суміжній i в графі Y (i = 1 .. N, j = 1 .. ki)
Якщо з якоїсь вершини не виходить жодного ребра, то для неї у вихіднихданих задаємо тільки нуль (наприклад '0 '- вершина 2 ізольована). Такимчином, для кожного графа повинно вводиться в цілому N нулів.
Формат друку результатів роботи програми представлений в такому форматі:
Дани неорієнтовані графи X і Y без кратностей.
Для кожного графа задаємо номера вершини едомської даної.
Граф X (в ЕОМ в послідовному поданні):
1: X11 X12 ... X1k1
2: X21 X22 ... X2k2
...
N: XN1 XN2 ... XNkN
Граф Y (в ЕОМ у зв'язаному поданні):
1: Y11 Y12 ... Y1k1
2: Y21 Y22 ... Y2k2
...
N: YN1 YN2 ... YNkN
Над графами виконується операція різниці двома способамиз отриманням нового графа Z (у зв'язаному поданні):
1: Z11 1, Z12 ... Z1k1
2: Z21 Z22 ... Z2k2
...
N: ZN1 ZN2 ... ZNkN
І виправленням старого графа X (в послідовному поданні):
1: X11 X12 ... X1k1
2: X21 X22 ... X2k2
...
N: XN1 XN2 ... XNkN
Кількість вершин, кол-во дуг графа X, к-ть дуг графа Y і кількість часу, витраченого на обчислення різниці X і Y:
N MX MY Tде T - кількість часу, витраченого на обчислення різниці X і Y
Zij - номер чергової вершини суміжній i в графі Z (i = 1 .. N, j = 1 .. ki)
MX - кількість дуг у графі X
MY - кількість дуг у графі Y
Метод рішення:
Принцип рішення заснований на методі повного перебору, що звичайно не кращийваріант, але все-таки краще, ніж нічого.
Аномалії вихідних даних і реакція програми на них:
1. брак пам'яті при розподіл: висновок повідомлення на екран і завершення роботи програми;
2. невірний формат файлу: висновок повідомлення на екран і завершення роботи програми;
Вхідні дані
Вхідними даними для моєї роботи є початкове число вершинграфа, що у міру роботи програми збільшитися на 30 верші. Це числоне може перевищувати значення 80 вершин, тому що в процесі роботипрограми число збільшується на 30 і ставати 110 - це «критичний»число виходить з розрахунку 110 (216/3. Це відбувається тому, щостандартний тип int не може вмістити в себе більш ніж 216. Мені жпотрібно для нормально роботи програми, щоб тип вміщував в себе потроєноюкількість вершин неорієнтованого графа. Звичайно, це всього лишенаближення, але з урахуванням того, що графи генеруються випадково можливістьнабору 33000 невелике і, отже, припустимо.
Вхідний файл генерується кожен раз новий.
Графи для розрахунку мультиплікативний констант генеруються випадковимчином, використовуючи датчик випадкових чисел, це-то й накладає обмеженняна кількість вершин. Справа в тому, що при роботі з генератором випадковихчисел предпостітельно іоспользовать цілий тип даних - так говорив товариш
Подбельський В.В.
Оцінка тимчасової складності.
Катки відомості про тимчасової складності.
Якість алгоритму оцінюється як точність рішення і ефективністьалгоритму, яка визначається тим часом, який витрачається длярішення задачі і необхідним обсягом пам'яті машини.
Тимчасова складність алгоритму є залежність від кількостівиконуваних елементарних операцій як функція розмірності задачі. Тимчасоваскладність алгоритму А позначається.
Розмірність завдання - це сукупність параметрів, що визначають мірувихідних даних. Тимчасова оцінка алгоритму буває двох типів:
1. апріорна - асимптотична оцінка складності
2. апосторіорная - оцінка складності алгоритму з точністю до мультиплікативний констант, зроблених для конкретної машини.
Саме асимптотична оцінка алгоритму визначає в результаті розмірністьзавдання, яке можна вирішити за допомогою ЕОМ. Якщо алгоритм обробляєвхідні дані розміру N за час CN2, де С - деяка постійна, токажуть, що тимчасова складність цього алгоритму є. Вірнішеговорити, що позитивна і нульова функція є, якщоіснує така постійна С, що для всіх негативних значень N.
Обчислення тимчасової складності.
Для того, щоб перевірити правильність тимчасової оцінки алгоритму,треба знати апріорну оцінку складності.
Перевірка обчислювальної складності алгоритму зводитися доекспериментального порівнянні двох або більше алгоритмів, які вирішують одну і тусаме завдання. При цьому виникають дві головні проблеми: вибір вхідних даних іпереведення результатів експерименту в графіки кривих складності.
При прогоні програми ми отримуємо значення функції, які можназобразити на графіку як функцію f (NX, NY, NZ). Дані точки показуютьхарактер кривої. Для апроксимації цієї хмари точок у своєї курсовоїроботі я використовував метод найменших квадратів.
Аналіз за методом найменших квадратів полягає у визначенніпараметрів кривої, що описують зв'язок між деякими числом N пар значень
Xi, Yi (в даному випадку n і t відповідно), забезпечуючи при цьомунайменшу середньоквадратичне похибка. Графічно це завдання можнапредставити таким чином - в хмарі точок Xi, Yi площині XY (дивисямалюнок) потрібно провести пряму так, щоб величина всіх відхиленьвідповідала умові:
N
F =
K = 1
Де
У моєму випадку T (NX, NY, NZ) = O (NX * (NY + NZ) =>
T (NX, NY, NZ) = C1 * NX * (NY + NZ) + C2 * (NY + NZ) + C3 * (NY) + C4 * (NZ)
Отже для мого прикладу ми отримаємо:
Для того щоб одержати значення функції на K-том експерименті, ми засікаємозначення часу перед викликом функції, яка реалізує алгоритм, вставимооператор виду:
TikTak = clock ();
Де функція clock () дає час з точністю до декількох мілісекунд (вмові С + + вона описана в заголовки time.h). Після виконанняпроцедури, реалізує алгоритм, ми знаходимо різницю часу
TikTak = cloc () - TikTak;
Після всіх проведених маніпуляцій потрібно прирівняти до нуля всі приватніпохідні. Це буде виглядати, у загальному вигляді, приблизно так:
Після розкриття дужок і заміни T (n) = T (n) = (c, ((n)) = отримаємо
Покладемо Аij = (ti, tj) і B = (ti, TikTak) => ми отримали систему рівнянь AX = B,де Х = С. Формування в матриці стовпці А і стовпців У записується дужелегко використовуючи будь-який алгоритмічну мову. Після заповнення матриці їїзалишається вирішити і вивести вирішення цього завдання. Рішення проводитисяметодом Жордана.
Апріорна тимчасова оцінка процедур.
Процедура виведення графа на екран у послідовному поданні:
Void prin3 (Array * X, int N1, int N)
X - граф в связаное поданні
N - кількість вершин графа.
N1 - кількість дуг у графі Х
O (N, N1) = N * N1
Процедура виведення графа на екран у связаное поданні:
Void print3 (Spisok ** X, int N)
X - граф в связаное поданні
N - кількість дуг у графі.
O (N) = N
Процедура обчислення різниці графів з повертає значеннямпослідовного графа:
Array * RaznostZ (int n, int & n1, Array * X, Spisok ** Y, Array * Z)
N - кількість дуг графа
N1 - кількість вершин у графі Х
X - грав у послідовному поданні
Y - грав у связаное поданні
Z - грав у послідовному поданні
O (N, N1 ) = N1 * N * k = N1 * N2
N2 - кількість вершин у графі Y
Процедура обчислення різниці графів з повертає значеннямпослідовного графа:
Spisok * RaznostY (int n, int & n1, Array * X, Spisok ** Y)
N - кількість дуг графа
N1 - кількість вершин у графі Х < p> X - грав у послідовному поданні
Y - грав у связаное поданні
O (N, N1) = N1 * N * (k + l) = N1 * (N3 + N2)
N2 - кількість вершин у графі Y
N3 - кількість вершин у графі Z - повертається.
Процедура введення графів в послідовному поданні:
Spisok ** ReadFileY (Spisok ** Y, char * st)
St - покажчик на рядок з іменем файла з якого буде відбуватисявведення
Y - грав у связаное поданні
O (N, N1) = N + N2
N2 - кількість вершин у графі Y
Процедура введення графів в послідовному поданні:
Array * ReadFileY (Array * X, char * st)
St - покажчик на рядок з іменем файла з якого буде відбуватисявведення
X - грав у послідовному поданні
O (N, N1) = N2
N2 - кількість вершин у графі X
Текст програми.
# Include
# Include
# Include
# Include
# Include
# Include
///////////////////////////////////////// ///////////////////////////////////< br>///////////////////////////struct Spisok// Пов'язане подання графа
(Int index;// Содержвтельная "осередок"
Spisok * next;// Следуюцая "дуга"
);
////////////////////////////////////////////////// //////////////////////////< br>///////////////////////////struct Array// Послідовне подання графа
(Int I;// з якої вершини int J;// в якусь вершину
);
////////////////////////////////////////////////// //////////////////////////< br>///////////////////////////
inline double fun1 (double N_X, double N_Y, double N_Z) (return < br>N_X * (N_Y + N_Z );}
inline double fun2 (double N_X, double N_Y, double N_Z) (return N_X + N_Y;)
inline double fun3 (double N_X, double N_Y, double N_Z) (return N_X;)
inline double fun4 (double N_X, double N_Y, double N_Z) (return N_Y;)
inline double fun5 (double N_X, double N_Y, double N_Z) (return N_Z;)
inline double fun6 (double N_X, double N_Y, double N_Z) (return 1;)
////////////////////////////////////////////////// //////////////////////////< br>///////////////////////////const int N = 6, M = N 1;
double A [N] [M];double B [N] [M];
typedef double (* MENU1) (double, double, double);
MENU1 MyMenu [6] = (fun1, fun2, fun3, fun4, fun5, fun6);
////////////////////////////////////////////////// //////////////////////////< br>/// /int gordanA (int n, int m)
(Int i, j, k, ir; double s, c; for (j = 0; j fabs (s)) s =
A [ir = i] [j]; if (s == 0) return -1; for (k = j + 1; k A [i] [j]; A [n - 1] [k] = c;
)
)return 0;
)
////////////////////////////////////////////////// //////////////////////////< br>///long double Stp (int a, int n)
(long double c, bi;int k;c = 1;k = n;bi = a;while (k> 0) (if (k% 2 == 1) c *= bi; bi *= bi; k/= 2;
)return c;
)
////////////////////////////////////////////////// //////////////////////////< br>///////////////////////////void CursorOff (void)
(asm (mov ah, 1 mov ch, 0x20 int 0x10
)
)
////////////////////////////////////////////////// //////////////////////////< br>///////////////////////////< br>Spisok ** GenSeY (int Mas_y, int & Counter)
(Counter = 0;
Spisok ** Y = new Spisok * [Mas_y]; for (int i = 0; i Spisok * beg = NULL, * end = NULL; for (int j = 0; j Pro [m] = k; m + +; if ((beg == NULL) & & (end == NULL)) (end = new (Spisok); if (end == NULL) (cout next = new (Spisok); if (end == NULL) (cout index = k;
Counter ++;
)
)
Y [i] = beg; delete [] Pro;
) return Y;
)
////////////////////////////////////////////////// //////////////////////////< br>////< br>Array * GenSeX (int Mas_y, int & Counter)
(Counter = 0;
Array * X = new Array [Mas_y * Mas_y]; if (X == NULL) (cout
