 ПОЗНАВАТЕЛЬНОЕ
| Алгоритм сортування методом простого виробуМіністерство культури України Київський національний університет культури і мистецтв Факультет економіки і менеджменту Кафедра комп’ютерних наук
Курсова робота «НАЗВА» з дисципліни:«Теорія алгоритмів»
Підготував: студент ІІ курсу групи КН-21 Василевський Давид по-батькові Науковий керівник: К.ф.-м.н., доцент Ткаченко О.І. Київ-2012 Зміст Вступ. 3 Розділ 1. Теоретичні відомості 3 1.1. Алгоритм сортування методом простого виробу. 3 1.1.1. Словесний опис алгоритму. 3 1.1.2. Структура даних. 3 1.1.3. Опис схеми алгоритму. 3 1.1.4. Опис процедури Obmin. 3 1.1.5. Математичний опис. 3 1.1.6. Контрольний приклад. 3 1.2. Хвилевий алгоритм пошуку довгого шляху на зваженому орієнтованому графові. 3 1.2.1. Словесний опис алгоритму. 3 1.2.3. Структури даних. 3 1.2.4. Опис схеми алгоритму. 3 1.2.5. Опис процедури CountTop2. 3 1.2.6. Опис процедури MarkArrow.. 3 1.2.7. Опис процедури BuildWays. 3 1.2.8. Контрольний приклад. 3 Розділ 2. Опис Машини Тюрінга. 3 1.1. Основні поняття. 3 1.2. Постановка завдання. 3 1.3. Ідея вирішення. 3 1.4. Словесний опис алгоритму. 3 1.5. Використовувані символи на стрічці 3 1.6. Структури даних. 3 1.7. Функціональна схема М.Т. 3 1.8. Приклад роботи М.Т. 3 Розділ 3. Програма. 3 3.1. Опис програми командами машини Тюрінга. 3 3.2. Опис програми на мові програмування. 3 Висновки. 3 Список використаних джерел. 3 Додатки. 3 Вступ
Розвиток теорії алгоритмів починається з доказу К. Геделем теорем про неповноту формальних систем, що включають арифметику, перша з яких була доведена в 1931 р.. Виникле у зв'язку з цими теоремами припущення про неможливість алгоритмічного дозволу багатьох математичних проблем (зокрема, проблеми виводимості в численні предикатів) викликало необхідність стандартизації поняття алгоритму. Перші стандартизовані варіанти цього поняття були розроблені в 30-х роках XX століття в роботах А. Тюрінга, А. Чьорча та Е. Поста. Алгоритм - це однозначна послідовність елементарних дій, що забезпечують рішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових Постановка задачі. Побудувати машину Тюрінга для опису алгоритмів арифметичних дій(віднімання, ділення) в десятковій системі числення. У розділі 1 наведені основні теоретичні відомості, щодо алгоритму сортування методом простого вибору і алгоритму знаходження найдовшого шляху. Розділ 2описує машинуТюрінга. Йдутьтеоритичнівідомості про машину з прикладами. Розділ 3містить в собі опис програми командами машиниТюрінга і опис програми на мовіпрограмування, яка була задана в моїйпостановцізадачі.
Теоретичні відомості Алгоритм сортування методом простого виробу
Алгоритм простим вибором - це дуже природний спосіб сортування. Зазвичай він першим спадає на думку людині, що зіткнулася з необхідністю впорядкування таблиці. Він є досить простим в освоєнні і тому зручний. Сортування простим вибором не можливе, доки не буде відомо всі елементи масиву, також його недоліком є досить значна затрата часу на впорядкування масиву порівняно з іншими видами сортувань. Ідея його така. Знайдемо в таблиці елемент з найменшим значенням і поміняємо його місцями з першим елементом. Після цього ті ж дії виконаємо з N, що залишилися (без першого), - 1 елементами таблиці, потім з N - 2 елементами і т. д., поки не залишиться один елемент - останній. Він буде найбільшим. Цей метод для послідовності прямокутників різної висоти. Два перші елементи вже впорядковано. Потім відшукується мінімальний серед інших. Якщо елементи в послідовності можуть бути рівними, то відшукується перший (I) серед мінімальних (таким чином досягається стійкість сортування). Він міняється місцями з третім. Цей метод сортування, званий простим вибором, в деякому розумінні протилежний до методу простих включень; при сортуванні простими включеннями на кожному кроці розглядається тільки один черговий елемент вхідної підпослідовності і усі елементи готового масиву для знаходження місця включення; при сортуванні простим вибором розглядаються усі елементи вхідного масиву для знаходження елементу з найменшим ключем, і цей один черговий елемент вирушає в готову підпослідовність. Наступником методу простого вибору є - сортування модифікованим методом простого вибору. Цей метод ґрунтується на алгоритмі пошуку мінімального елементу. У масиві А(1.n) відшукується мінімальний елемент, який ставиться на перше місце . Для того, щоб не втратити елемент, що стоїть на першому місці, цей елемент встановлюється на місце мінімального . Потім в такій же послідовності, виключаючи перший елемент, відшукується мінімальний елемент і ставиться на друге місце і так далі n - 1 раз доки не встане на своє місце передостанній n - 1 елемент масиву А, перемістивши максимальний елемент в самий кінець. Розглянемо алгоритмічне рішення задачі на прикладі сортування деякого масиву значень за збільшенням. Відповідно до вищеописаного методу нам необхідно кілька разів виконувати операції пошуку мінімального елементу і його перестановку з іншим елементом, тобто потрібно буде кілька разів переглядати елементи масиву з цією метою. Кількість переглядів елементів масиву згідно з описом модифікованого методу простого вибору рівна n - 1, де n - кількість елементів масиву. Таким чином, можна зробити висновок, що проектований алгоритм сортування міститиме цикл, в якому виконуватиметься пошук мінімального елементу і його перестановка з іншим елементом. Позначимо через i - лічильник (номер) переглядів елементів масиву і зображує узагальнений алгоритм сортування на (сх. 1). Нужно написать (див. рис.1 ) Відмітимо, що для перестановки елементів місцями необхідно знати їх порядкові номери, алгоритм перестановки елементів масиву був розглянутий раніше. Алгоритми введення початкового масиву і виведення цього ж масиву після сортування зображені на малюнках 16 і 24 відповідно. Алгоритм пошуку в масиві мінімального елементу і його номера буде аналогічний розглянутому алгоритму пошуку максимального елементу. Проте, в цьому алгоритмі будуть внесені зміни. Для того, щоб визначити які зміни слід внести розглянемо виконання сортування цим методом з акцентом на пошук мінімального елементу на конкретному прикладі. Нехай початковий масив містить 5 елементів (2,8,1,3,7). Кількість переглядів згідно з модифікованим методом простого вибору дорівнюватиме 4. Покажемо в таблиці 1, як змінюватиметься початковий масив на кожному перегляді. Таблиця 1. Назва
Введемо наступні позначення: К- номер мінімального елементу J - номер елементу масиву М і А(К) - одне і теж значення мінімального елементу масиву i - номер що переставляється з мінімальним елементу А(i) - значення елементу, що переставляється. Тоді циклічний алгоритм сортування модифікованим методом простого вибору виглядатиме таким чином (сх.2).
12 |
