Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Інтелектуальні системи
Частина тексту файла (без зображень, графіків і формул):
Кафедра комп’ютерних інтелектуальних систем та мереж
Курсова робота
з дисципліни
«Теорія алгоритмів»
ВСТУП
Під час розробки програмних проектів часто виникає необхідність обробки великої кількості одноманітно організованих даних. У таких випадках подібні дані зручно обробляти як єдине ціле, для чого вони представляються у вигляді масиву - іменованої послідовності даних одного типу.
У курсовій роботі розглядаються такий популярний спосіб обробки масивів як сортування. Сортування-процес перестановки елементів заданої множини в певному порядку, мета якого – полегшити наступний пошук елементів у масиві.
В даний час існує безліч алгоритмів сортування масивів, які застосовуються залежно від того які умови функціонування стоять перед розроблюваної програмою.
Алгоритм - це точно визначена (однозначна) послідовність простих (елементарних) дій, які забезпечують вирішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових здібностей і можливостей виконавця.
Ефективність алгоритму визначається аналізом, який повинен дати чітке уявлення, по-перше, про ємнісну і, по-друге, про часову складність процесу.
Мова йде про розміри пам'яті, в якій належить розміщувати всі дані, які беруть участь в обчислювальному процесі (до них відносяться вхідні набори, проміжна і вихідна інформація), а також фізичні ресурси, витрачені виконавцем.
У курсовій роботі представлені два методи реалізації математичних задач сортування за допомогою алгоритмів. Проведена коротка характеристика використовуваних структур даних, ефективність їх застосування у даних завданнях.
ЗМІСТ
Вступ.... 2
. Завдання до курсової роботи 4
. Загальні положення 5
2.1. Число з плаваючою точкою (комою) 7
2.2. Представлення чисел з плаваючою точкою в ЕОМ 8
2.3. Стандарт IEE-754 13
3. Складання чисел з плаваючою точкою (комою) 21
3.1. Правила виконання операції додавання 22
3.2. Склад АЛУ для операції складання чисел з плаваючою точкою 26
3.3. Алгоритм додавання чисел з плаваючою точкою 26
4. Висновок 28
Додатки 29
Список літератури 31
1.ЗАВДАННЯ ДО КУРСОВОЇ РОБОТИ
Для вибору варіанта завдання визначимо цілочислову остачу від ділення виразу Y, утвореного сумою: Х+23, де Х отримана шляхом множення останньої цифри номера групи на 100. число Х = 2*100 = 200, 23 – останні цифри у заліковій книжці (номер за списком групи) .
(Y mod 2) + 1 — алгоритми покриття; 223= 1+1=2
(Y mod 2) + 1 — алгоритми сортування. 223=1+1=2
Виходячи з цього, в якості алгоритму покриття буде виступати алгоритм A2 – побудова одного мінімального покриття, а як алгоритм сортування – С2 - простим обміном (бульбашкове сортування).
АЛГОРИТМ СОРТУВАННЯ ПРОСТИМ ОБМІНОМ (БУЛЬБАШКОВЕ СОРТУВАННЯ)
Існує безліч методів сортування. Одні з них є більш ефективними, інші - простіше для розуміння. Досить простий для розуміння є сортування методом бульбашки, який також називають методом простого обміну.
1.1.1. Постановка завдання
Завданням даної роботи є побудова алгоритму сортування масиву методом простого обміну (бульбашкового покриття). Дуже часто для зручності в обчислювальної техніки однотипні дані представляються у вигляді масивів. Масив – це об'єкт даних, в якому зберігається кілька одиниць даних, ідентифікованих за допомогою одного або декількох індексів. У простому випадку масив має постійну довжину і зберігає одиниці даних одного і того ж типу.
Кількість використаних індексів масиву може бути різним. Масиви з одним індексом називають одновимірними, з двома – двовимірними і т.д. Одновимірний масив не строго відповідає вектору в математиці, двовимірний – матриці. Найчастіше застосовуються масиви з одним або двома індексами, рідше – з трьома, ще більша кількість індексів зустрічається вкрай рідко.
Алгоритм сортування бульбашкою полягає в послідовних обходах масиву з перестановкою пар сусідніх елементів (якщо потрібно) таким чином, що на кожному обході максимальний елемент «спливає» до кінця масиву - як бульбашка в воді. Потрібен n-1 обхід, щоб впорядкувати масив (n - число елементів масиву).
Математичний опис завдання і методів його розв’язання
Словесний опис алгоритму і його роботи
Алгоритм і особливості сортування бульбашкою такі:
- при першому проході по масиву елементи попарно порівнюються між собою: перший з другим, потім другий з третім, слідом третій з четвертим і т.д. Якщо попередній елемент виявляється більше подальшого, то їх міняють місцями.
- поступово найбільше число виявляється останнім. Інша частина масиву залишається відсортованою, хоча деяке переміщення елементів з меншим значенням в початок масиву спостерігається.
- при другому проході немає потреби порівнювати останній елемент з передостаннім. Останній елемент вже стоїть на своєму місці. Значить, число порівнянь буде на одне менше.
- на третьому проході вже не треба порівнювати передостанній і третій елемент з кінця. Тому число порівнянь буде на два менше, ніж при першому проході.
- при проході по масиву, коли залишаються тільки два елементи, які треба порівняти, виконується тільки одне порівняння.
- після цього перший елемент немає з чим порівнювати, і, отже, останній прохід по масиву не потрібен. Іншими словами, кількість проходів по масиву дорівнює N-1, де N - це кількість елементів масиву.
Кількість порівнянь в кожному проході одне mi, де i - це номер проходу по масиву (перший, другий, третій і т.д.).
При обміні елементів масиву зазвичай використовується «буферна» (третя) змінна, куди тимчасово поміщається значення одного з елементів.
Вибір структур даних
З аналізу задачі та її даних видно, що алгоритм повинен працювати зі змінними, котрі представлені нижче (усі змінні цілого типу):
n - Кількість елементів у масиві
m - Лічильник обходів масиву
t - прапор
M - буферна змінна
i – індекс елемента масиву
Опис схеми алгоритму
Початок виконання алгоритму бульбашкового сортування починається з
введення даних - елементів масиву A, який буде сортуватися та привласнення початкових значень змінних (блоки 1- 2).
Початкове значення t - true, щоб обійти масив хоч раз.
У блоці 3 відбувається перевірка завершення сортування. Якщо були перестановки на попередньому обході масиву, обхід масиву починається знову. Якщо не було - масив впорядкований і алгоритм завершується.
Початок обходу елементів масиву починається з блоку 4. Індекс елемента масиву j встановлюємо в 0 - початок масиву, t встановлюємо в false - перестановок не було.
Збільшуємо лічильник m обходів масиву.
Порівняння сусідніх елементів (чи наступний [j +1] елемент масиву більше попереднього [j]?) відбуваетьлся у блоці 5. Якщо наступний елемент більший попереднього, то відбувається перехід на перестановку елементів масиву (блоки 6-8) . Якщо ні - то перехід до наступного елементу масиву.
У блоці 10 відбувається перевірка завершення обходу. Якщо дійшли до кінця масиву, то припиняємо обхід, якщо ні - то відбувається перехід до порівняння
Присвоєння ознаки перестановки відбувається у блоці 9. Перехід до наступного елемента – у блоці 11.
Приклад роботи алгоритму
Вихідний масив
[34,25,19,124,17]
1-а ітерація зовнішнього циклу: і:=1
1-а ітерація внутрішнього циклу: j=1
[34,25,19,124,17] Так [25, 34,19,124,17]
2-а ітерація внутрішнього циклу: j=2
[25, 34,19,124,17] Так [25, 19, 34 ,124,17]
3-я ітерація внутрішнього циклу: j=3
[25, 19, 34 ,124,17] Ні [25, 19, 34 ,124,17]
4-а операція внутрішнього циклу: j=4
[25, 19, 34 ,124,17] Так [25, 19, 34 , 17, 124]
Вихідний массив
[25, 19, 34 , 17, 124]
2-а ітерація зовнішнього циклу: і:=2
1-а ітерація внутрішнього циклу: j=1
[25, 19, 34 , 17,124] Так [19, 25, 34 , 17, 124]
2-а ітерація внутрішнього циклу: j=2
[19,25, 34 , 17,124] Ні [19,25, 34 , 17,124]
3-я ітерація внутрішнього циклу: j=3
[19,25, 17,34 , 124] Так [19, 25, 17, 34 , 124]
Вихідний масив
[19, 25, 17, 34 , 124]
3-а ітерація зовнішнього циклу: і:=3
1-а ітерація внутрішнього циклу: j=1
[19,25, 17,34 , 124] Ні [19, 25, 17, 34 , 124]
2-а ітерація внутрішнього циклу: j=2
[19,25, 17,34 , 124] Так [19, 17, 25, 34 , 124]
Вихідний масив
[19, 17, 25, 34 , 124]
4-а ітерація зовнішнього циклу: і:=1
1-а ітерація внутрішнього циклу: j=1
[19, 17, 25, 34 , 124] Так [17,19, 25, 34 , 124]
АЛГОРИТМ ПОКРИТТЯ ПОБУДОВИ ОДНОГО МІНІМАЛЬНОГО ПОКРИТТЯ
Постановка завдання
Завданням даної роботи є побудова алгоритму покриття одного мінімального покриття заданої таблиці, тобто знайти мінімальне покриття, яке містить найменшу ціну.
Покриття – це сукупність підмножин заданої множини, що утворюють вихідну безліч. Покриттям таблиці буде така сукупність строк, при якій в кожному стовбці є хоча б одна одиниця.
Таблиця покриття — це двовимірна матриця. Її доцільно представити у вигляді двовимірного масиву. Cлід також передбачити одновимірний масив для зберігання номерів рядків матриці покриття, що перевіряються. Для зберігання номерів обраний масив, оскільки кількість рядків, хоча і невідома заздалегідь, обмежена кількістю рядків матриці покриття.
Математичний опис завдання і методів його розв’язання
Визначимо опірну множину: B= {b1,b2,b3,..bn}. Множина підмножин множини В ( ) буде А= {а1,а2,а3,..аm}. Кожній множині Ai відповідає ціна ai. Рішенням завдання про покриття буде покриття (множина) P={Aij,..Aik} (ij), якщо виконується умова , при цьому ціна . Термін «покриття» означає, що сукупність множин Aij,..Aik включає всі елементи множини В, тобто «покриває» множину B.
Беззбитковим буде покриття, якщо при видаленні з нього хоча б одного елемента воно перестає бути покриттям. Інакше - покриття надлишкове.
Покриття Р буде мінімальним за умови, що його ціна - найменша серед всіх покриттів даного завдання.
Нехай матриця М буде заданою таблицею покриттів. Стовпці матриці зіставлені елементам множини В, рядки - елементам множини А:
1, якщо bj B та bj Ai
A: M =
0, якщо bj B та bj Ai
В таблиці покриттів нулі не проставляються.
Сформулюємо завдання щодо покриття:
- знаходимо всі покриття, для чого необхідно виконати повний перебір всіх підмножин множини А.
- знаходимо тільки безнадлишкові покриття, хоча слід зауважити, що простого і ефективного алгоритму, який не потребує побудови всіх надлишкових покриттів не існує: можемо тільки зменшити їх кількість, використовуючи, зокрема, граничний перебір або розкладання по стовпцю в таблиці покриттів. Достатньо визначити хоча б одне безнадлишкове покриття. Зробимо це, шляхом скорочення таблиці.
- знаходимо покриття, яке має найменшу ціну.
Найбільш точним рішення поставленого завдання буде при невеликій розмірності матриці М.
Словесний опис алгоритму і його роботи
Наближене рішення задачі про покриття базується на розумінні того, що навіть скорочений перебір призводить до дуже трудомісткого процесу вирішення, то для отримання відповіді доводиться відмовлятися від гарантій побудови оптимального рішення (мінімального або найкоротшого); однак доцільно отримати не найгірший результат - хоча б одне безнадлишкове покриття, яке задовольняє необхідній умові.
Тому алгоритм роботи наступний:
1. уведення числа рядків (i) і числа стовпців (j) таблиці покриття;
2. уведення таблиці покриття;
3. уведення номерів рядків таблиці покриття, що перевіряються;
4. розрахунок суми елементів (S) по стовпцях таблиці (у суми включаються тільки ті рядки, які перевіряються), починаючи з першого до останнього (i-го), або поки не зустрінеться сума, що дорівнює 0;
5. якщо всі розраховані суми ненульові, отже, рядки, що перевіряються, є покриттям. У протилежному випадку — ні;
6. якщо в результаті перетворень таблиця покриттів змінилася, виконуємо пункт 3. Інакше - показ безлічі покриття, вихід.
2.4. Вибір структур даних
З аналізу задачі і її даних видно, що алгоритм повинен працювати з таблицею покриття і з деякими змінними, котрі представлені нижче (усі змінні цілого типу):
M [i,j] – матриця (таблиця покриття)
a кількість рядків таблиці покриття;
b кількість стовпців таблиці покриття;
k– кількість рядків, які перевіряються на покриття;
str [i] проміжна змінна для збереження номера рядка;
i, j змінні циклу.
min, max - попередня сума стовпця;
S - поточна сума стовпця або рядка.
Таблицю покриття представляємо двовимірним масивом М(a,b). Для зберігання номерів обраний масив, оскільки кількість рядків, хоча і невідома заздалегідь, обмежена кількістю рядків матриці покриття (a).
Опис схеми алгоритму
Блок-схема даного алгоритму зображена на рис. 2 в Додатку.
Спочатку вводяться розміри a, b та таблиця покриття (блок 1). Далі відбувається пошук пустого стовпця (блок 2): це доцільно, оскільки, якщо хоча б один стовпець не покритий, то й не існує покриття цієї таблиці, і, отже, кінець алгоритму. Розглядаємо певну кількість комбінацій знаходження суми рядків у стовпчиках. Номери строк, перевіряються, заносяться до Str [i]. В результаті отримуємо підстановку PR [i,j] PR [str[i], j] .
3.5 Підпрограми основного алгоритму
Функція PR(D, kol, А, n) визначає, чи є рядки матриці А, номера яких задані в списку D, покриттям. Тут kol – кількість елементів у масиві D; n – кількість стовпців матриці А. Функція повертає 1, якщо задані рядки матриці А утворюють покриття, 0 – у протилежному випадку. Для функції PR(D, kol, A, n) використовується алгоритм, наведений у п. 4 словесного опису алгоритму для розв’язання всієї задачі. Блок-схема цієї функції представлена на рис. 2.2 Додатку.
Опис локальних змінних (усі – цілі):
Sj – змінна для підрахунку суми (ціла);
i, j – змінні для організації циклів;
k – змінна для вибору номера рядка зі списку D.
Алгоритм працює таким чином. При виклику в основному алгоритмі функції PR(D, kol, А, n) у неї передаються параметри D, kol, А, n; потім організується зовнішній цикл (блоки 2-8) проходу по всіх стовпцях матриці А і внутрішній цикл (блоки 3-6) розрахунку суми S по i-му стовпцю для заданих рядків, які перевіряються на покриття. Як ознака відсутності покриття використовується значення суми S = 0, оскільки якщо в деякому стовпці на всіх позиціях, які відповідають розглянутим рядкам, будуть нулі, то цього досить, щоб констатувати відсутність покриття (у цьому випадку можна не перевіряти інші стовпці). Обчислення S відбувається в блоці 5 для обраного з масиву D (блок 4) рядка з номером k. У блоці 7 перевіряється умова S = 0, і залежно від її значення приймається рішення про те, яке значення функції повертається в основний алгоритм (блоки 9 і 10), де воно присвоюється змінній usl. Відзначимо, що, коли цикл проходу по стовпцях цілком завершився, то жодна сума по стовпцях не дорівнює 0. Це означає, що задані рядки є розв’язанням задачі про покриття.
Приклад роботи алгоритму
Нехай задана таблиця покриття (див. таб. 1).
Таблиця 1.
B
B1
B2
B3
B4
B5
S
А1
1
1
2
А2
1
1
1
4
A3
1
1
1
1
А4
1
1
7
Крок 1
Складаємо строки А1В1 та А2В1
Сума S1 > 0, переходимо на наступний стовпчик
Сума S2 = 0, отже {А1 ,А2} не є покриттям.
Крок 2
Складаємо строки А1В1, та А3В1
Сума S1 > 0, переходимо на наступний стовпчик
Сума S2 = 0, отже {А1 ,А3} не є покриттям.
Крок 3
Складаємо строки А1В1, та А4В1
Сума S1 = 0, отже {А1 ,А4} не є покриттям.
Крок 4
Складаємо строки А2В1, та А3В1
Сума S1 > 0, переходимо на наступний стовпчик
Сума S2 = 0, отже {А2 ,А3} не є покриттям.
Крок 5
Складаємо строки А2В1, та А4В1
Сума S1 = 0, отже {А2 ,А4} не є покриттям.
Крок 6
Складаємо строки А3В1, та А4В1
Сума S1 = 0, отже {А3 ,А4} не є покриттям.
Крок 7
Складаємо строки А1В1, А2В1, та А3В1
Сума S1> 0, переходимо на наступний стовпчик
Сума S2 = 0, отже { А1, А2 ,А3} не є покриттям.
Крок 7
Складаємо строки А1В1, А2В1, А3В1 та А4В1
Сума S1> 0, переходимо на наступний стовпчик
Сума S2> 0, переходимо на наступний стовпчик
Сума S3> 0, переходимо на наступний стовпчик
Сума S4> 0, переходимо на наступний стовпчик
Сума S5> 0, отже {А1, А2 ,А3, А3} є покриттям:
Р={А1, А2 ,А3, А3}
Це єдине покриття, тому й мінімальна ціна дорівнюватиме
Smіn=2+4+1+7=14
ВИСНОВОК
У роботі розроблено алгоритми сортування сортування за методом простого обміну (бульбашкове сортування) та покриття – побудову одного мінімального покриття. Алгоритми виконані з достатньою для розуміння деталізацією виконуваних операцій. Розглянуто приклади використання розроблених алгоритмів.
Розглянуто ефективність роботи алгоритмів, способи її підвищення.
Розроблений алгоритм сортування методом простих включень (бульбашковий метод) виконує сортування елементів масиву. Недоліком його є те, що іноді масив може вийти відсортованим раніше останньої ітерації циклу сортування. Для вирішення цієї проблеми, наприклад, можна перевіряти, чи були проведені переміщення елементів на кожному кроці сортування, і, якщо вони не були зроблені, слід, що масив відсортований. У цьому випадку сортування припиняється.
Розроблений алгоритм побудова одного мінімального покриття. Цей алгоритм є більш ефективним тому, що швидше знаходить найбільш значущі для знаходження мінімального покриття підмножини. Хота, на мою думку, алгоритми потребують вдосконалення.
СПИСОК ЛІТЕРАТУРИ
1. Вірт Н. Алгоритмы и структуры данных. – С.-П.: Невский диалект, 2001. – 350 с.
2. Новиков Ф. А. Дискретная математика для программистов. – С.-П.: Питер, 2003.–292 с.
3. http://www.bestreferat.ru/referat-107618.html
4. http://do888.narod.ru/6.htm
5. http://cpp.com.ru/shildt_spr_po_c/21/2104.html
Додаток 1
Рис.1. Блок-схема алгоритму сортування простим обміном (бульбашкове сортування)
Додаток 2
INS
PR [i,j] PR [str[i], j]
Рис.1. Блок-схема алгоритму побудова одного мінімального покриття:
1.Основна схема алгоритму;
2. Схема алгоритму для функції покриття PR(D, kol, A, n) .
05.01.2015 16:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора