Разработка алгоритмів і програм операцій над послідовними і пов'язаними уявленнями структур данных

МІНІСТЕРСТВО СПІЛЬНОГО І ПРОФЕСІЙНОГО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦИИ.

МОСКОВСЬКИЙ ДЕРЖАВНИЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНІВЕРСИТЕТ їм. К.Э. ЦИОЛКОВКОГО.

КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ.

ПОЯСНЮВАЛЬНА ЗАПИСКА.

до курсової роботи тему: «Розробка алгоритмів і програм операцій над послідовними і пов’язаними уявленнями структур данных».

за курсом «Теорія алгоритмів і обчислювальних методы».

Руководитель: Авдошин С.М.

Дата здачі: _____________.

Подпись: _____________.

Студент: Лицентов Д.Б.

Група: 3ИТ-2−26.

Москва.

1. Постановка задачи.

Дано: Два орграфа X і Y з N вершинами (XX ст послідовному поданні, 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 — номер черговий вершини суміжною і в графі X (і = 1. N, j=1.ki).

Yij — номер черговий вершини суміжною і в графі 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 — номер черговий вершини суміжною і в графі Z (i = 1. N, j=1.ki).

MX — у дуг в графі X.

MY — у дуг в графі Y.

Метод рішення: Принцип рішення грунтується на методі повного перебору, що, звичайно не найкращий варіант, але, ніж ничего.

Аномалии вихідних даних, і реакція програми ними: 1. нестача пам’яті при розподіл: висновок повідомлення на екран також завершення роботи програми; 2. зрадливий формат файла: висновок повідомлення на екран також завершення роботи программы;

Вхідні данные.

Вхідними для моєї роботи є підставою початкова число вершин графа, які з мері роботи програми збільшитися на 30 верши. Ця кількість неспроможна перевершувати значення 80 вершин, позаяк у процесі роботи програми число поповнюється 30 і ставати 110 — це «критичне» число виходить з розрахунку 110(216/3. Це тому, що стандартний тип int неспроможна вмістити у собі більш як 216. Мені ж від потрібно нормально роботи програми, щоб тип вміщував у собі утроенное кількість вершин неориентированного графа. Звісно, це лише наближення, але з урахуванням те, що графи генеруються випадково можливість набору 33 000 невелике і, отже, допустимо.

Вхідний файл генерується щоразу новый.

Графи до розрахунку мультипликативных констант генеруються випадковим чином, використовуючи датчик випадкових чисел, саме це й накладає певні обмеження кількості вершин. Річ у тім, що з працювати з генератором випадкових чисел предпостительно иоспользовать цілий тип даних — так говорив товариш Подбельский В.В.

Оцінка тимчасової сложности.

Каткие інформацію про тимчасової сложности.

Якість алгоритму оцінюється як точність рішення і ефективність алгоритму, що визначається тим часом, яке витрачається для виконання завдання необхідним обсягом пам’яті машины.

Тимчасова складність алгоритму є залежність кількості виконуваних елементарних операцій як функція розмірності завдання. Тимчасова складність алгоритму, А позначається [pic].

Розмірність завдання — це сукупність параметрів, визначальних міру вихідних даних. Тимчасова оцінка алгоритму буває двох типов:

1. завжди апріорна — асимптотическая оцінка складності [pic].

2. апосториорная — оцінка складності алгоритму з точністю до мультипликативных констант, зроблених для конкретної машини. Саме асимптотическая оцінка алгоритму визначає результаті розмірність завдання, яке можна вирішити з допомогою ЕОМ. Якщо алгоритм обробляє вхідні дані розміру N під час CN2, де З — якась стала, то кажуть, що тимчасова складність цього алгоритму є [pic]. Точніше говорити, що позитивна і нульова функція [pic] є [pic], якщо є така стала З, що [pic] всім негативних значень N.

Обчислення тимчасової сложности.

А, щоб перевірити правильність тимчасової оцінки алгоритму, треба знати апріорну оцінку сложности.

Перевірка обчислювальної складності алгоритму зводитися до експериментальному порівнянню двох чи більше алгоритмів, вирішальних те ж саме завдання. У цьому виникають головні проблеми: вибір вхідних даних, і перекладу результатів експерименту в графіки кривих сложности.

При прогоні програми ми маємо значення функції, які можна зобразити на графіці як функцію f (NX, NY, NZ). Дані точки показують характер кривою. Для апроксимації цього хмари точок у своїй курсової роботі я використовував метод найменших квадратов.

Аналіз методом найменших квадратів залежить від визначенні параметрів кривою, що описують зв’язок між деяким числом N пар значень Xi, Yi (у разі n і t відповідно), забезпечуючи у своїй найменшу среднеквадратичную похибка. Графічно це завдання можна уявити так — в хмарі точок Xi, Yi площині XY (дивися малюнок) потрібно провести пряму те щоб величина всіх відхилень відповідала условию:

[pic].

N.

F =[pic].

K=1.

Где.

[pic] У моєму разі T (NX, NY, NZ)=O (NX*(NY+NZ) =>

T (NX, NY, NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ).

Следовательно для мого прикладу ми получим:

[pic] Щоб отримати значення функції на K-том експерименті, ми засікаємо значення часу перед викликом функції, яка реалізує алгоритм, уставимо оператор вида:

TikTak=clock (); Де функція clock () дає період із точністю за кілька мілісекунд (в мові З++ вона описано на заголовочном файлі time. h). По виконанні процедури, реалізує алгоритм, ми бачимо різницю времени.

TikTak=cloc () — TikTak; Після всіх пророблених маніпуляцій потрібно прировнять до нуля всі приватні похідні. Це виглядатиме, загалом, приблизно так:

[pic].

После розкриття скобок заміна T (n)= T (n)=(c,((n))= [pic]получим.

[pic] Поклавши А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 — кількість вершин в графі Х.

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.

//////////////////////////////////////////////////////////////////////////// /////////////////////////// struct Spisok //Пов'язане уявлення графа { int index; //Содержвтельная «осередок «.

Spisok *next; //Следуюцая «дуга «}; //////////////////////////////////////////////////////////////////////////// /////////////////////////// struct Array //Послідовне уявлення графа { int I; //з якої вершини int J; //у яку вершину }; //////////////////////////////////////////////////////////////////////////// ///////////////////////////.

inline double fun1(double N_X, double N_Y, double N_Z){ return 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;} //////////////////////////////////////////////////////////////////////////// /////////////////////////// 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 }; //////////////////////////////////////////////////////////////////////////// //// int gordanA (int n, int m) { int і, j, k, ir; double p. s, з; for (j = 0; j < n; j++){ for (p.s = 0, і = 0; і < (n — j); i++)if (fabs (A[i][j]) > fabs (s)) p. s = A[ir = i][j]; if (s==0)return -1; for (k = j + 1; k < m; k++){ з = A[ir][k]/s; for (і = 0; і < ir; i++)A[i][k] -= з * A[i][j]; for (і = ir + 1; і < n; i++)A[i — 1][k] = A[i][k] - з * A[i][j];

A[n — 1][k] = c;

} } return 0; } //////////////////////////////////////////////////////////////////////////// /// 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 з; } //////////////////////////////////////////////////////////////////////////// /////////////////////////// void CursorOff (void) {asm{ mov ah, 1 mov ch, 0×20 int 0×10 } } //////////////////////////////////////////////////////////////////////////// /////////////////////////// Spisok **GenSeY (int Mas_y, int & Counter) { Counter=0; Spisok **Y = new Spisok* [Mas_y]; for (int і = 0; і< Mas_y; і++){ int m = 0; int *Pro = new int [Mas_y];

Spisok *beg = NULL, *end = NULL; for (int j = 0; j< Mas_y; j++){ int k = random (Mas_y); int flag = 0; for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1; if (k ≠ 0 && flag == 0){.

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 [і] = beg; delete [] Pro; } return Y; } //////////////////////////////////////////////////////////////////////////// //// Array *GenSeX (int Mas_y, int & Counter) { Counter=0; Array *X = new Array[Mas_y*Mas_y]; if (X==NULL){cout.