Теорія алгоритмів

Размещено на http://www.allbest.ru/

ЗМІСТ

Вступ

1. Вибір варіанту

2. Алгоритм сортування Шейкер

2.1 Математичний опис задачі

2.2 Словесний опис алгоритму та його роботи

2.3 Опис схеми алгоритму

2.4 Контрольний приклад

3. Алгоритм покриття: побудова одного найкоротшого покриття

3.1 Математичний опис задачі

3.2 Словесний опис алгоритму та його роботи

3.3 Опис схеми алгоритму

3.4 Контрольний приклад

Перелік використаної літератури

ВСТУП

Алгоритм - це точно визначена (однозначна) послідовність простих (елементарних) дій, які забезпечують вирішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових здібностей і можливостей виконавця.

Як зауважив Кнут: "Алгоритм повинен бути визначений настільки чітко, щоб його вказівкам міг слідувати навіть комп'ютер".

Теорія алгоритмів та практика їх побудови і аналізу є концептуальною основою різноманітних процесів обробки інформації. В даний час теорія алгоритмів утворює теоретичний фундамент обчислювальних наук. Застосування теорії алгоритмів здійснюється як у використанні самих результатів (особливо це стосується використання розроблених алгоритмів), так і у виявленні нових понять і уточнення старих. З її допомогою прояснюються такі поняття як довідність, ефективність, розв'язність, перераховуваність та інші.

Ефективність алгоритму визначається аналізом, який повинен дати чітке уявлення, по-перше, про ємнісну і, по-друге, про часову складність процесу.

Мова йде про розміри пам'яті, в якій належить розміщувати всі дані, які беруть участь в обчислювальному процесі (до них відносяться вхідні набори, проміжна і вихідна інформація), а також фізичні ресурси, витрачені виконавцем.

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

1. Вибір варіанту

Номер варіанту визначається знаходженням остатку від цілочисленного ділення числа Y ,яке є сумою числа X і номеру по списку в журналі. Номер по списку в журналі N=9. Таким чином:

X=Nгр*100=6*100=600;

Y=N+X=9+600=609.

По формулам знаходжу види алгоритмів у моїй роботі.

1) (Y mod 4) + 1 =(609 mod 4) + 1=1 + 1= 2; Алгоритм покриття: побудова одного найкоротшого покриття.

2) (Y mod 5) + 1 =(609 mod 5) +1 =4 + 1 = 5; Алгоритм сортування: сортування - шейкер.

Таким чином необхідно розробити алгоритми для знаходження одного найкоротшого покриття і шейкер сортування.

2. АЛГОРИТМ СОРТУВАННЯ: СОРТУВАННЯ ШЕЙКЕР

2.1 Математичний опис задачі

Сортування - це перестановка елементів деякої множини в заданому порядку при якому елементи впорядковуються.

Сортування використовується для полегшення пошуку елемента в відсортованій множині.

Завдання сортування вирішується за допомогою таких алгоритмів: сортування за допомогою прямого включення, прямого вибору, прямого обміну, включень з зменшеними відстанями, дерева, поділу та інші.

2.2 Словесний опис алгоритму та його роботи

Сортування Шейкер є вдосконаленим сортуванням методом бульбашки. Ідея методу: крок сортування полягає в проході знизу вгору по масиву. На шляху проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями. (см. Таб. 1)

Таблиця 1

i=1	2	3	4	5	6	7	8
44	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12
12	55	44	18	18	18	18	18
42	12	55	44	42	42	42	42
94	42	18	55	44	44	44	44
18	94	42	42	55	55	55	55
06	18	94	94	67	67	67	67
67	67	67	67	94	94	94	94

Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого згори елемента, таким чином другий за величиною елемент піднімається на правильну позицію.

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

Тим не менш, у нього є величезний плюс: він простий і його можна по-різному покращувати. Чим ми зараз і займемося. По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося жодного обміну. Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку). Отже, перше поліпшення алгоритму полягає в запам'ятовуванні останнього змінюваного елементу. Якщо такого елемента немає - алгоритм закінчує роботу. Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але й індекс останнього обміну k. Всі пари сусідніх елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легка бульбашка знизу підніметься вгору за один прохід, важкі бульбашки опускаються із найменшою швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок проходів почергово. Одержаний алгоритм називають "шейкер-сортуванням". Далі проведена програма на мові С++, що реалізує сортування Шейкер.

#include <iostream>

#include <cstdlib>

#include <stdio.h>

using namespace std;

int size=0;

void shaker(int* m){ //функція сортування

int a=0,b=size-1,p=0,k=0;

for(;;){

if (a==(b+1)) break;

p=0;

for(int i=a;i<b;i++) if(m[i]<m[i+1]){//прохід вниз

int t=m[i];

m[i]=m[i+1];

m[i+1]=t;

p=1;

k=i;

};

b=k;

if (p==0) break;

if (a==(b+1)) break;

p=0;

for(int i=b;i>a;i--) if(m[i]>m[i-1]){//прохід вверх

int t=m[i];

m[i]=m[i-1];

m[i-1]=t;

p=1;

k=i;

};

a=k;

if (p==0) break;

};

}

int main()

{

for(;size==0;){

printf("Введите размер массива \n");

cin>>size;

system("clear");

};

int* mas=new int[size];

printf("Ввод эл-в \n");

for(int i=0;i<size;i++) cin>>mas[i];

printf("Ввод окончен \n");

shaker(mas);

printf("Отсортированый массив \n");

for(int i=0;i<size;i++) printf("%u ",mas[i]);

return 0;

}

Середня кількість порівнянь, хоч і зменшилася, але залишається O (n2), в той час як число обмінів не змінилося взагалі ніяк. Середня (вона ж найгірша) кількість операцій залишається квадратичною, кількість зайвих подвійних перевірок скоротилася. Додаткова пам'ять, очевидно, не потрібна. Поведінка удосконаленого (але не початкового) методу досить природна, майже відсортований масив буде відсортований набагато швидше випадкового. Сортування бульбашкою стійке, однак шейкер-сортування втрачає цю якість. На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому - майже не застосовується.

2.3 Опис схеми алгоритму

Алгоритми сортування дуже сильно залежать від структури даних. У даній роботі розглядається сортування масивів. Тип даних "масив" зручний тим, що зберігається у внутрішній пам'яті і має випадковий доступ до елементів, тобто більш швидкий, ніж у послідовності. Тому масиви доцільно використовувати для зберігання невеликих, часто використовуваних множин.

З вище сказаного випливає, що в процесі роботи будуть потрібні наступні змінні: і - кількість елементів масиву;

M - масив для сортування; p - змінна;

t - i-й ключ (елемент що переноситься);

b - номер останнього обміну при русі зліва-направо.

a - номер останнього обміну при русі справа-наліво.

Всі змінні цілого типу. Блок-схема даного алгоритму зображена на рис. 1 в Додатку. Алгоритм працює наступним чином. Спочатку вводяться початкові данні: довжина масиву та його елементи (блок 1), потім організуємо цикл на весь масив, під час якого (блоки 5 -8) і проводиться зрівняння елементів m[i]<m[i+1] та їх обмін при проході зліва-направо. Номер останнього обміну k запамятовується. Далі організується цикл, в якопу проводиться перевірка умови m[i]>m[i+1] при проході масиву зліва-направо (блоки 12 - 15).

2.4 Контрольний приклад

Розглянемо приклад роботи алгоритму сортування Шейкер.

Заданий масив M з 8 елементів: 44, 55, 12, 42, 94, 18, 6, 67.

Крок 1.

алгоритм сортування покриття інструкція

1) a=0, b=7

2) a=b+1 нет

3) p=0

4) i=a=0, m[0]<m[1], t=m[0]=44, p=1, m[0]=m[1]=55, m[1]=t=44, k=0

5) i=i+1=1, m[1]>m[2]

6) i=i+1=2, m[2]<m[3], t=m[2]=12, p=1, m[2]=m[3]=42, m[3]=t=12, k=2

7) i=i+1=3, m[3]<m[4], t=m[3]=12, p=1, m[3]=m[4]=94, m[4]=t=12, k=3

8) i=i+1=4, m[4]<m[5], t=m[4]=12, p=1, m[4]=m[5]=18, m[5]=t=12, k=4

9) i=i+1=5, m[5]>m[6]

10) i=i+1=6, m[6]<m[7], t=m[6]=6, p=1, m[6]=m[7]=67, m[7]=t=6, k=6

11) b=k=6

Таблиця

a	0	0	1	1	2
b	7	6	6	3	3
Напрямок	v	^	v	^	v
0	44	55	94	94	94
1	55	44	55	55	67
2	12	42	44	44	55
3	42	94	42	67	44
4	94	18	67	42	42
5	18	12	18	18	18
6	6	67	12	12	12
7	67	6	6	6	6

Крок 2. A[7]<A[8] , j = j -1 =7

p=0 нет

1) a=b+1 нет

2) p=0

3) i=b=6, m[6]>m[5], t=m[6]=67, p=1, m[6]=m[5]=12, m[5]=t=67, k=6

4) i=i-1=5, m[5]>m[4], t=m[5]=67, p=1, m[5]=m[4]=18, m[4]=t=67, k=5

5) i=i-1=4, m[4]<m[3]

6) i=i-1=3, m[3]>m[2], t=m[3]=94, p=1, m[3]=m[2]=42, m[2]=t=94, k=3

7) i=i-1=2, m[2]>m[1], t=m[2]=94, p=1, m[2]=m[1]=44, m[1]=t=94, k=2

8) i=i-1=1, m[1]>m[0], t=m[1]=94, p=1, m[1]=m[0]=55, m[0]=t=94, k=1

9) a=k=1

Крок 3.

1) p=0 нет

2) a=b+1 нет

3) p=0

4) i=a=1, m[1]>m[2]

5) i=i+1=2, m[2]>m[3]

6) i=i+1=3, m[3]<m[4], t=m[3]=42, p=1, m[3]=m[4]=67, m[4]=t=42, k=3

7) i=i+1=4, m[4]>m[5]

8) i=i+1=5, m[5]>m[6]

9) b=k=3

Крок 4.

1) p=0 нет

2) a=b+1 нет

3) p=0

4) i=b=3, m[3]>m[2], t=m[3]=67, p=1, m[3]=m[2]=44, m[2]=t=67, k=3

5) i=i-1=2, m[2]>m[1], t=m[2]=67, p=1, m[2]=m[1]=55, m[1]=t=67, k=2

6) a=k=2

Крок 5.

1) p=0 нет

2) a=b+1 нет

3) p=0

4) i=a=2, m[2]>m[3]

Крок 6.

1. p=0 да > кінець алгоритму

Таким чином ми отримали масив, відсортований методом Шейкер:

94, 67, 55, 44, 42, 18, 12, 6.

3. АЛГОРИТМ ПОКРИТТЯ: ПОБУДОВА ОДНОГО НАЙКОРОТШОГО ПОКРИТТЯ

3.1 Математичний опис задачі

Нехай-опірна множина. Маємо множину підмножин множини B ( ). Кожній множині зіставлено число , яке називається ціною. Множина називається рішенням задачі про покриття, або просто покриттям,якщо виконується умова , при цьому ціна . Термін "покриття" означає, що сукупність множин включає всі елементи множини В, тобто "покриває" множину B.

Беззбитковим називається покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Інакше - покриття надлишкове.

Покриття Р називається мінімальним, якщо його ціна- найменша серед всіх покриттів даного завдання.

Покриття Р називається найкоротшим, якщо l - найменше серед всіх покриттів даної задачі.

Зручним і наочним поданням вихідних даних і їх змін у завданні про покриття є таблиця покриттів. Таблиця покриттів - це матриця Т відносин приналежності елементів множин опорній безлічі В. Стовпці матриці зіставлені елементам множини В, рядки - елементам множини

А:

Нулі в матриці T не проставляються.

Маємо наступні варіанти формулювання задачі про покриття:

1. Потрібно знайти всі покриття. Для вирішення завдання необхідно виконати повний перебір всіх підмножин множини А.

2. Потрібно знайти тільки без надлишкові покриття. Не існує простого і ефективного алгоритму, що не потребує побудови всіх надлишкових покриттів: добре, якщо зменшується їх кількість. (Використовується граничний перебір або розкладання по стовпцю в ТП).

Потрібно знайти одне без надлишкове покриття. Рішення завдання ґрунтується на скороченні таблиці.

Завдання про покриття можуть бути вирішені точно (при невеликій розмірності) або наближено (див. [2]).

Для знаходження точного рішення використовуються такі алгоритми.

1) Алгоритм повного перебору. (Оснований на методі упорядкованого перебору підмножин множини А).

2) Алгоритм граничного перебору по ввігнутій множині. (Оснований на одноіменному методі скорочення перебору).

3) Алгоритм розкладання по стовпчику таблиці покриття. Оснований на методі скорочення перебору, який полягає в тому, щоб розглядати тільки ті строки таблиці покриття, в яких є "1" в обраному для розкладання стовпчику.

4) Алгоритм скорочення таблиці покриття. Заснований на методі побудови циклічного залишку таблиці покриття, для якого далі покриття будується методами граничного перебору або розкладання по стовпцю.

Наближене рішення задачі про покриття базується на розумінні. Якщо навіть скорочений перебір призводить до дуже трудомісткого процесу вирішення, то для отримання відповіді доводиться відмовлятися від гарантій побудови оптимального рішення (мінімального або найкоротшого); однак доцільно отримати не найгірший результат - хоча б безнадлишкове покриття, задовольняє необхідній умові. При цьому на шкоду якості можна значно спростити процес вирішення.

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

3.2 Словесний опис алгоритму і його роботи

1) Вважаємо вихідну таблицю покриттів поточною, а безліч ядерних рядків - порожньою.

2) Знаходимо ядерні рядки, запам'ятовуємо безліч ядерних рядків. Поточну таблицю покриттів скорочуємо, викреслюючи ядерні рядки і всі стовпці, покриті ними.

3) викреслюємо поглинені стовпці.

4) викреслюємо поглинені рядки.

5) Якщо в результаті виконання пунктів з 1 по 4 поточна таблиця покриттів змінилася, знову виконуємо пункт 1, інакше перетворення закінчено.

Тому алгоритм роботи наступний:

1) введення числа рядків і стовпців таблиці покриття;

2) введення таблиці покриття;

3) пошук ядерних рядків. Якщо їх немає, то п.4. Інакше, запам'ятовуємо ці ядерні рядки. Шукаємо стовпці, вкриті ядерними рядками. Викреслюємо всі ядерні рядки і стовпці, покриті ними.

4) викреслення поглинених стовпців.

5) викреслення поглинених рядків.

6) якщо в результаті перетворень таблиця покриттів змінилася, виконуємо пункт 3. Інакше - показ безлічі покриття, кінець алгоритму.

3.3 Вибір структур даних

З аналізу задачі та її даних видно, що алгоритм повинен працювати з таблицею покриття і з деякими змінними, які представлені нижче (всі змінні цілого типу):

a - кількість рядків таблиці покриття;

b - кількість стовпців таблиці покриття;

i, j - змінні циклу по рядках і стовпцях;

min,max - попередня сума стовпця або рядка;

s - поточна сума стовпця або рядка.

Таблиця покриття - це двовимірна матриця. Її доцільно представити у вигляді двовимірного масиву mas (a, b).

p - одномірний масив для зберігання номерів рядків, що покривають матрицю. Для зберігання номерів обраний масив, оскільки кількість рядків, хоча й невідомо заздалегідь, обмежена кількістю рядків матриці покриття (a).

3.4 Опис схеми алгоритму

Блок-схема даного алгоритму зображена на рис. 2 в Додатку.

Спочатку вводяться розміри a, b та таблиця покриття (блок 1). Далі відбувається пошук пустого стовпця (блок 2): це доцільно, оскільки, якщо хоча б один стовпець не покритий, то й не існує покриття цієї таблиці, і, отже, кінець алгоритму. Далі, якщо не знайдено порожнього стовпця (перевірка в блоці 3), - пошук ядерних рядків та стовпців, покритих ними (блок 4, 5). Після цього викреслюються всі рядки, знайдені в блоках 4,5 (блок 6). Викреслюються поглинені стовпці (блок 7-10).. Якщо в результаті виконання блоків 6-10 поточна таблиця покриттів змінилася, то виконується блок 4; інакше випливає висновок знайденого найкоротшого покриття у вигляді номерів рядків, що покривають таблицю. Потім кінець алгоритму.

3.5 Підпрограми основного алгоритму

Функція Пусто (mas) веде пошук порожніх стовпців, тобто не покриваються ні одним рядком. Блок-схема цієї функції представлена на рис. 2.1 Додатку. Організовується цикл по всіх стовпцях (блоки 2-9). У кожному стовпці йде рахунок нулів (лічильник ініціалізується в кожному проході - блок 3; рахунок ведеться в блоці 6), тобто якщо зустрічається хоча б одна одиниця (перевірка в блоці 5), то відбувається перехід у наступний стовпець. Алгоритм працює до тих пір, поки не буде досягнутий кінець таблиці (тобто кінець циклу по i, блок 9) або поки не буде пораховано a нулів в одному стовпці (перевірка умови в блоці 8), тобто j = a. Функція повертає 1, якщо знайдено a нулів, і 0, якщо досягнуто кінець таблиці. Функція Мін (mas) знаходить мінімальний стовпчик. Функція проглядає всі стовпчики в циклі (блок 3-11), знаходить суму їх елементів (блок 7), та, порівнюючи з попередньою сумою (блок 9) знаходить номер мінімального стовпчика (блок 10). Функція Макс (mas) аналогічна Мін, але знаходить мінімальне і працює з рядками. Функція Вив (p) виводить номера ненульових (блок 3) строк.

3.6 Приклад роботи алгоритму

Нехай задана таблиця покриття (див. Таб. 3). Розглянемо приклад роботи алгоритму.

Крок 1.

Таб. 3.

B	B1	B2	B3	B4	B5	B6
А1	1		1			1
А2	1			1	1
A3	1			1	1
А4		1	1			1

Безліч ядерних рядків пуста.

1. Мінімальний стовпчик В6

2. Максимальна строка А4

3. До безлічі ядерних строк додаємо А4

4. Викреслюємо А4 та В2, В3, В6, тепер таблиця покриття має вигляд Таб. 4

5. Залишок стовпчиків існує

Крок 2

Таб. 4.

	В1	В4	В5
А1	1
А3	1	1	1
А4

1. Множина ядерних строк А4

2. Мінімальний стовпчик В5

3. Максимальний рядок А3

4. До безлічі ядерних строк додаємо А3

5. Викреслюємо А3 та В1, В4, В5, тепер таблиці покриття не існує.

6. Залишку не існує

ВИСНОВОК

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

Велику увагу приділено порівнянні можливого використання кількох структур даних, проведений аналіз ефективності роботи алгоритму в залежності від використовуваної структури.

Розглянуто складність кожного алгоритму, її залежність від умов даної задачі, методи спрощення і полегшення розуміння алгоритму. У додатку також приведені тексти програм на мові С++.

ЛИТЕРАТУРА

1. Вірт Н. Алгоритмы и структуры данных. - С.-П.: Невский диалект, 2001. - 350 с.

2. Новиков Ф. А. Дискретная математика для программистов. - С.-П.: Питер, 2003.-292 с.

Размещено на Allbest.ru