Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2009
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
№
від . .2009р.
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра СКС
Алгоритми та методи обчислень
Методичні вказівки до лабораторних робіт з курсу “Алгоритми та методи обчислень” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Спеціалізованих Комп’ютерних Систем Протокол № від ____ 2009 року
Львів – 2009
Алгоритми та методи обчислень : Методичні вказівки до лабораторних робіт з курсу “ Алгоритми та методи обчислень ” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: М. Черкаський, В. Мітьков – Львів: Національний університет “Львівська політехніка”, 2009, __ с.
Укладачі: М. Черкаський, професор кафедри СКС
В. Мітьков,ст.. викладач кафедри СКС
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Алгоритми та методи обчислень
Вступ
Наукове пізнання навколишнього світу людина здійснює за допомогою його моделювання. Кожна наукова дисципліна широко використовує різні моделі.
Графічні схеми, математичні рівняння, діаграми причинно-наслідкових зв'язків, таблиці і навіть вербальні конструкції є різновидами моделювання.
Модель - це формалізоване, спрощене представлення реального об'єкту
Будь-яка наукова модель має цільовий характер, тобто вона будується для конкретних цілей і для вирішення певних задач. Вона достатньо точно відображає ті сторони модельованого явища, які мають ключове значення для вирішення поставленої задачі. Укладена в моделі помилка рано чи пізно заважає вирішувати інші задачі, пов'язані з модельованим об'єктом. Вирішити нові задачі можна або шляхом уточнення, узагальнення первинної моделі, або шляхом побудови нової моделі.
Алгоритм – фундаментальне поняття математики, йому не можна дати точне математичне визначення із залученням інших фундаментальних понять. Відсутність такого визначення не заважає інтуїтивному розумінню його змісту. Але в літературних джерелах наводяться різні варіанти розуміння сутності алгоритму. В загальному випадку під терміном “алгоритм” розуміють шлях (метод, спосіб) розв’язання задачі. Таке тлумачення не дозволяє досліджувати особливості роботи, конструювати ефективні алгоритми. Проблема розв’язується застосуванням моделей алгоритму.
В залежності від складності задачі, мети дослідження, практичного застосування моделі поділяються на декілька груп, які показані на рис.1.
Рис. 1
Виконанню обчислювальних операцій без вказівки на засоби виконання відповідають дві моделі: “алгоритм – процес” і “алгоритм – припис”
Першу модель “алгоритм – процес” виконання чотирьох арифметичних операцій детально у словесній формі описав аль-Хорезмі (IX стор). Пізніше в працях Хр. Рудольфа (XVI стор.) і Г.В.Лейбніця (XVII стор.) модель аль-Хорезмі набула наступного тлумачення – “Алгоритм означає будь-який регулярний обчислювальний процес, який за кінцеву кількість кроків розв’язує задачі визначеного класу” [1]. Це тлумачення близьке до наведеного у сучасній фундаментальній монографії: “Кажучи неформально, алгоритм – це будь-яка коректно сформульована обчислювальна процедура, на вхід якої подається деяка величина або набір величин, і результатом виконання якої є вихідна величина або набір значень” [2]. Більш детальне тлумачення з описом властивостей алгоритму дано А Марковим:
“а) Алгоритм – це процес послідовної побудови величин, який проходить в дискретному часі таким чином, що в початковий момент задається початкова скінчена система величин, а в кожний наступний момент система величин отримується за певним законом (програмою) із системи величин, які були в попередній момент часу (дискретність алгоритму).
б) Система величин, які утримуються в якийсь (не початковий) момент часу, однозначно визначається системою величин, отриманих в попередні моменти часу (детермінованість алгоритму).
в) Закон отримання наступної системи величин із попередньої повинен бути простим і локальним (елементарність кроків алгоритму).
г) Якщо спосіб отримання наступної величини із якої-небудь заданої величини не дає результату, то повинно бути вказано, що потрібно рахувати результатом алгоритму (спрямованість алгоритму).
д) Початкова система величин може вибиратися із деякої потенційно нескінченної множини (масовість алгоритму)”[3].
Це розширене тлумачення можна знайти в ряді сучасних джерел, наприклад в [4]. Порівнюючи ці три тлумачення, не можна сказати, яке з них краще або вірніше, бо це лише неформальний опис моделі алгоритмічного процесу. Для такого опису не має математичних підстав порівняння. Розглянуті тлумачення відрізняються один від одного. Наприклад, процес вимірюється часом виконання, припис вимірюється кількістю інструкцій програми або блок-схем програми, але ці відміни незначні.
Друга модель “алгоритм – припис” реалізується у вигляді блок-схем програм і програм на мові високого рівня. Прикладом тлумачення алгоритму на основі цієї моделі є: “Алгоритм – це послідовність інструкцій для виконання деякого завдання”[5]. Варіанти наведеного тлумачення є поширеними у літературних джерелах [6,7].
Наступні варіанти тлумачення зумовлені використанням конструктивно заданих математичних моделей алгоритму – формальних алгоритмічних систем. Абстрактні формальні системи використовуються для дослідження теоретичних проблем обчислень, наприклад, проблем розв’язності. На основі абстрактних систем була створена теорія складності. До формальних алгоритмічних систем відносяться два класи математично строго визначених моделей, які містять всі основні засоби для здійснення обчислювального процесу. До першого класу відносяться абстрактні моделі, які у своєму визначенні не описують апаратні засоби, хоча їх наявність припускається. Також припускається, що операції алгоритмічного процесу здійснюються людиною без будь-яких інтелектуальних зусиль. Прикладами моделей цього класу є машина Тюрінга, нормальні алгоритми Маркова та декілька інших. Тлумаченням алгоритму, що випливає з аналізу цих моделей є: “Алгоритм – точний припис, який задає обчислювальний процес (що називається в цьому випадку алгоритмічним), що починається з довільного початкового даного (з деякої сукупності можливих для даного алгоритму початкових даних) і спрямований на отримання результату, який повністю визначається цим початковим даним”(8(. Тут точний припис і алгоритмічний процес об’єднані в одному тлумаченні. Абстрактні формальні системи використовуються для дослідження теоретичних проблем обчислень, наприклад, проблем розв’язності. На основі абстрактних систем була створена теорія складності.
Другий клас формальних систем складається з моделей комп’ютерних алгоритмів. У цих моделях апаратні засоби задекларовані безпосередньо у її визначенні. Прикладом моделі другого класу є SH-модель алгоритму (SH – Software/Hardware). Теорія складності комп’ютерних алгоритмів суттєво відрізняється від абстрактної теорії. Тут крім технічних характеристик складності (часової, апаратної та ємнісної) використовуються додатково інформаційні (програмна та структурна). Модель комп’ютерного алгоритму дозволила формально визначити властивість “елементарність”, сформулювати властивість “ієрархічність”, створити модель універсального обчислювача. Відображення змісту моделі комп’ютерного алгоритму знайшло в неформальному тлумаченні.: “Алгоритм - це фіксована для розв’язання деякого класу задач конфігурація апаратно-програмних засобів перетворення, передавання і зберігання даних, який задає обчислювальний процес (що називається в цьому випадку алгоритмічним), який починається з будь-яких початкових даних (з деякої потенційно нескінченної сукупності можливих для даного алгоритму початкових даних) і скерований на отримання результату, повністю визначеного цими початковими даними”(9(.
Таким чином кожне наведене тлумачення поняття “алгоритм” адекватне обраній для дослідження конкретної моделі обчислень.
Параметрична модель алгоритму
Деяка змінна величина, яка визначає значення характеристик математичного об’єкту, називається параметром. Прикладом може бути частотна характеристика RC – ланцюга. R і C – параметри, затримка прямокутного сигналу τ = RC
Характеристики алгоритму визначаються наступними параметрами Рис. 2 :
1. Правило початку.
2. Правило вводу даних.
3. Система вхідних даних.
4. Правило безпосереднього перероблення .
5. Система проміжних результатів.
6. Система кінцевих результатів.
7. Правило виводу.
8. Правило закінчення.
Рис. 2
Зміна будь-якого параметру алгоритму змінює часову складність та інші характеристики. Зміна параметру алгоритму з метою мінімізації часової складності алгоритму називається параметричною оптимізацією алгоритму.
До способів мінімізації часової складності відносяться:
1. Зміна правила початку визначає
= вибір черговості використання даних в процесі обчислень
= векторизація,
= конкурентизація, тощо.
2. Зміна системи вхідних даних, наприклад, 10-вої, 16 річної тощо
3. Зміна системи проміжних результатів наприклад, використання двійкової системи,
4. Зміна правила вводу даних:
== генерування,
= читання,
= інкапсуляція
5. Зміна правил безпосереднього перероблення:
= розбиття масивів вхідних, вихідних даних проміжних,
= еквівалентні перетворення,
= апроксимація,
= використання попередніх обчислень
Визначення Параметрична модель алгоритму це сімка параметрів алгоритму об’єднаних зв’язками, які задають послідовність операцій виконання задачі ,
де
А – множина символів зовнішнього алфавіту. А охоплює множини символів систем проміжних і кінцевих результатів,
Q – множина символів алфавіту станів
q0, qf – початковий та кінцевий стани роботи моделі алгоритму; q 0, q f Q
I,O – операції вводу та виводу даних
P – правило безпосереднього перероблення
Правило безпосереднього перероблення може бути задано деякою функцією, словесно, таблицею, графом, блок-схемою, тощо.
Рис.3
На Рис 3 зображено блок-схема параметричної моделі пари задача-алгоритм. Від блок-схеми алгоритму вона відрізняється доданим блоком ”сформульоване намагання”. Крім того в системі вхідних даних та системі кінцевих результатів виділений набір вхідних даних {X} та набір кінцевих результатів {Y}, які належать безпосередньо до задачі, яка розв’язується
Лабораторна робота №1.
“Алгоритм, властивості алгоритму, характеристики складності. Порівняння алгоритмів виконання арифметичних операцій в римській та десятковій системах числення”.
Мета роботи: засвоїти основні поняття та визначення теорії алгоритмів.
МЕТОДИЧНІ МАТЕРІАЛИ
Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації обсягу досліджень – часовій складності розв’язання задач. Але зміст складності алгоритму не обмежується однією характеристикою. В ряді випадків не менше значення має складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім часової та програмної складності, досліджуються також інші характеристики складності, наприклад, ємкістна, але найчастіше розглядають дві з них - часову і програмну. Якщо у кінцевому результаті часова складність визначає час розв’язання задачі, то програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму. Вона впливає на витрати часу проектування алгоритму.
Вперше значення зменшення програмної складності продемонстрував аль-Хорезмі у своєму
трактаті “Про індійський рахунок”. У часи аль-Хорезмі для розрахунків користувалась непозиційною римською системою числення. Її вузловими числами є І, V, X, L, C, D, M, всі решта чисел утворюються сумуванням і відніманням вузлових. аль-Хорезмі, мабуть, першим звернув увагу на складність римської системи числення у порівнянні з позиційною десятковою з точки зору простоти операцій, їх послідовного виконання та засвоєння. Він писав: “…ми вирішили розтлумачити про індійський рахунок за допомогою .ІХ. літер, якими вони виражали будь-яке своє число для легкості і стислості, полегшуючи справу тому, хто вивчає арифметику, тобто число найбільше і найменше, і все, що є в ньому від множення і ділення, сумування, віднімання та інше.”[1]. Виокремленні слова – легкість, стислість, полегшення свідчать перш за все про те, що мова йде про програмну складність алгоритмів арифметичних операцій з використанням двох систем числення. Мабуть, ці слова аль-Хорезмі про складність алгоритмів при їх порівнянні були першими в історії арифметики.
Алгоритми реалізації арифметичних операцій, описані аль-Хорезмі у словесній формі, були першими у позиційній десятковій системі числення. Цікаво спостерігати, як точно і послідовно описує він алгоритм сумування, користуючись арабською системою числення і кільцем (нулем). В цьому опису є всі параметри алгоритму. [1]
Це один з перших відомих у світі вербальних арифметичних алгоритмів.
Розглянемо логіку побудови арифметичних процедур з використанням римської та арабської систем числення з метою порівняння їх за програмною складністю. Розглянемо приклад операції сумування. Будемо користуватися алгоритмом на основі табличного методу. У арабській системі з порозрядними операціями розмір таблиці 10*10. Визначення суми чергових розрядів двох чисел, наприклад, 2 і 3 за таблицею дорівнює 5, або 7 і 9 дорівнює 16. Ці таблиці ми пам’ятаємо з дитинства.
Інша ситуація є з римською системою числення. Крім таблиці (I,II,…Х)*(I,II,…Х), що є еквівалентом таблиці 10*10 у арабській позиційній системі, додатково потрібно ще чотири таблиці з вузловими числами римської системи L,C,D,M та доповнення табличного методу логічними процедурами. Наприклад, для операції сумування двох чисел CMLIX + XCIV потрібні таблиці більшого об’єму, ніж 10*10 кожна. Один з варіантів рахунку полягає в представленні чисел, по-перше, розділеними на окремі цифри, по-друге, проведенням операцій віднімання і сумування окремих цифр з використанням таблиць, по-третє, об’єднанням цифр, що залишилися, в єдине число.
CMLIX + XCIV = (-C) + M +L +(-I) + X + (-X) + C +(-I) + V;
Оскільки –C + С = 0; –X + X = 0; – I – I = – II, V – II = III,
то (1) перепишеться у вигляді: CMLIX + CIV = M + L + III = MLIII;
Як бачимо, для проведення розрахунків у римській системі необхідно виконувати більше типів операцій, ніж у десятковій арабській позиційній системі числення. Крім того, у римській системі потрібні додаткові логічні перетворення, що суттєво ускладнюють зв’язки між окремими операціями обчислювального процесу.
Часова складність операцій сумування і віднімання в десятковій системі визначається кількістю розрядів у взаємодіючих числах. У римській системі часова складність залежить від порядку розташування цифр у числах. У тих випадках, коли не потрібно утворювати ланцюги логічних операцій, часова складність не перевищує часову складність операцій з десятковими числами. У протилежному випадку, як у розглянутому прикладі, зростання невелике.
Таким чином, за логікою побудови і різноманітністю операцій – програмною складністю, арабська система суттєво простіша за римську, що й довів аль-Хорезмі. За часовою складністю вони майже однакові.
Позначення цифр в римській системі числення:
I = 1
V = 5
Х = 10
L = 50
С = 100
D = 500
M = 1000
Правила запису і читання чисел в римській системі числення:
Числа читаються зліва на право (від більшого до меншого): MXI = 1011;
Всі цифри складаються окрім тих, які стоять перед тими, що їх перевершують: XIX = 19;
Зліва від цифр, що більші їх самих можуть стояти тільки I, Х, С:
I може стояти зліва тільки від V і Х;
Х може стояти зліва тільки від L і С;
С може стояти зліва тільки від D і M;
· Підряд можуть йти тільки три однакові цифри. Підряд можуть йти I, Х, С, M;
V, L, D можуть зустрічатися тільки один раз;
I, Х, C зліва (від більшої цифри) можуть зустрічатися тільки один;
Цифра, яка стоїть справа не може стояти зліва.
Приклад.
На рис.1 – 4 відображене покрокове виконання алгоритму додавання двох чисел в Римській системі числення.
Рис. 1 Ввід доданків XXIX та XLIV
Рис.2 Розкладання першого доданку.
Рис.3 Розкладання другого доданку
Рис. 4 Формування результату.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Скласти програму, яка на прикладі виконання додавання/віднімання двох чисел в римській та десятковій системах числення демонструє властивості алгоритму (дискретність, детермінованість, елементарність кроку та масовість).
Програма повинна мати зручний графічний інтерфейс
Скласти та захистити звіт з лабораторної роботи.
Контрольні запитання
Дати тлумачення понятю алгоритм.
Пояснити властивості алгоритму.
Визначити характеристики складності алгоритму
Пояснити спосіб мінімізації часової складності вибором системи числення.
Праці Аль-Хорезмі, їх роль в теорії алгоритмів.
Лабораторна робота №2.
"Параметри та характеристики складності алгоритму".
Мета роботи: проаналізувати вплив параметрів алгоритму на характеристики складності алгоритму
МЕТОДИЧНІ МАТЕРІАЛИ
Схема розроблення будь-якого об’єкту складається з трьох операцій: синтез, аналіз, оптимізація (Рис.1)
Рис. 1
Існує два види синтезу: структурний і параметричний. Вихідними даними для структурного синтезу параметри задачі – сформульоване намагання і набори вхідних даних. В результаті структурного синтезу отримують алгоритм, який розв’язує задачу в принципі.
Параметричний синтез змінами параметрів дозволяє таку його структуру, яка дозволяє зменшити часову складність попередньої моделі. Існує багато способів конструювання ефективних алгоритмів на основі зміни параметрів. Розглянемо спосіб зміни правила безпосереднього перероблення на прикладі задачі знаходження найбільшого спільного дільника двох натуральних чисел..
Алгоритм знахождення найбільшого спільного дільника, яким ми користуємось для цієї цілі і донині, був запропонований Евклідом приблизно в 1150 році до н.е. у геометричній формі, в ньому порівняння величин проводилося відрізками прямих, без використання арифметичних операцій Алгоритм розв'язку передбачав повторювання віднімання довжини коротшого відрізка від довжини довшого.
Опис алгоритму
Маючи два натуральні числа a та b:
якщо b=0, то a є шуканим НСД,
інакше повторюємо обчислення для пари b та залишку від ділення a на b (тобто a mod b).
Версія ітераційна:
НСД( a, b)
поки b ≠ 0
c := остача від ділення a на b
a := b
b := c
поверни a
Версія рекурсивна:
НСД( a, b)
якщо b = 0
поверни a
інакше
поверни НСД( b, остача від ділення a на b)
Для того, щоб довести ефективність алгоритму, потрібно порівняти його з таким, який
приймається за неефективний. Прикладом такого неефективного алгоритму є процедура послідовного перебору можливих розв’язань задачі. Будемо вважати, що алгоритм перебору утворений в результаті структурного синтезу, на основі вхідних даних та намагання знайти серед всіх допустимих чисел такє, що є найбільшим дільником двох заданих чисел.
Ефективність, як правило, визначається такою характеристикою як часова складність, що вимірюється кількістю операцій, необхідних для розв’язання задачі.
Дослідимо розв’язання задачі знаходження найбільшого спільного дільника двох цілих чисел (N1>0,N2 >0, N1≥N2 ) алгоритмом перебору і алгоритмом Евкліда.[10] Алгоритм перебору заснований на операції інкременту змінної (n) від одиниці до меншого (N2) з двох заданих чисел і перевірці, чи ця змінна є дільником заданих чисел. Якщо це так, то значення змінної запам’ятовується і операції алгоритму продовжуються. Якщо ні, то операції алгоритму продовжуються без запам’ятовування. Операції алгоритму закінчуються видачею з пам’яті знайденого останнім спільного дільника. Блок-схема алгоритму приведена на рис.2(а).
a) б)
Рис2. Блок-схема алгоритму перебору (а) і Евкліда (б).
Адаптований до сучасної арифметики алгоритм Евкліда використовує циклічну операцію ділення більшого числа на менше, знаходження остачі (r) і заміну числа, яке було більшим, на число, яке було меншим, а менше число на остачу. Всі перераховані операції виконуються в циклі. Операції циклу закінчуються, коли ділення не дає
остачу. Останній дільник є найбільшим спільним дільником. Блок-схема алгоритму приведена на рис.2(б).
Аналіз цих двох алгоритмів показує, що часова складність алгоритму перебору значно перевищує часову складність алгоритму Евкліда. Для обох алгоритмів часова складність є функцією від вхідних даних, а не їх розміру. В таких випадках при порівнянні ефективності алгоритмів користуються порівнянням часових складностей визначених для найгіршого випадку.[5] Часова складність для найгіршого випадку (Lmax) представляє собою максимальну часову складність серед всіх вхідних даних розміру N.
Очевидно, що часова складність для алгоритму перебору
(1)
дe , яка дорівнює кількості операцій в кожній ітерації.
Для цілих чисел n алгоритм Евкліда знаходження
найбільшого спільного дільника має найбільшу часову складність для пари чисел і
, де
1 , 2 , 3 , ... , , , - числа Фібоначчі.
Алгоритм Евкліда є ефективним за часовою складністю у порівняні з алгоритмом перебору. Мінімізація часової складності дозволяє за всіх інших рівних умова збільшити продуктивність розв’язання задачі. Якщо розв’язання задач з різними початковими даними проводиться багаторазово, мінімізація часу дозволяє одержати економічний ефект.
Приклад
Рис.3 Головне вікно програми Lab_NSD.exe.
На Рис.3 наведено головне выкно програми Lab_NSD.exe Дана програма може бути використана для дослідження ефективності різних алгоритмів знаходження найбільшого спільного дільника, зокрема для пошуку таких пар чисел, для яких часова складність буде найбільшою.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Скласти програму (Pascal , C), яка дозволяє провести порівняння трьох алгоритмів знаходження НСД за характеристикою "часова складність"
Користуючись програмою Lab_NSD.exe знайти два числа з діапазону [1, 150], для яких часова складність алгоритму Евкліда буде найбільшою.
Скласти та захистити звіт з лабораторної роботи.
Вимоги до програми:
Можливість задавати діапазон вхідних даних.
Программа виконується циклічно.
В кожному циклі вибирається пара випадкових чисел з заданого діапазону.
Для вибраної пари чисел знаходиться НСД трьома методами.
Визначається часова складність для кожного з методів.
Для кожного методу підраховується середне та найбільше значення часової складності .
Отримані результати оперативно відображуються на екрані.
Оператор може зупинити програму в довільний момент часу.
Контрольні запитання
Показати зв'язок між параметрами та характеристикамі складності алгоритму.
Порівняти за часовою складністю алгоритм пошуку НСД методом перебору з більших чисел , з одиниці, та методом Евкліда.
Дати тлумачення поняттю "задача".
Пояснити спосіб мінімізації часової складності зміною правила початку, правила безпосереднього перероблення, правила закінчення.
Структура алгоритму.
Структура пари : задача-алгоритм.
Схема побудови алгоритму.
Лабораторна робота №3.
“Асимптотичні характеристики складності алгоритму.
Алгоритми з поліноміальною та експоненціальною складністю”.
Мета роботи: ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів.
МЕТОДИЧНІ МАТЕРІАЛИ
В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній:
= бути простим для розуміння, переводу в програмний код, відлягодження.
= ефективно використовцвати комп'ютерні ресурси і виконуватись швидко.
Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання ( а не виконання) програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма.
На час виконання програми впливають наступні чинники:
= ввід інформації в програму
= якість скомпільованого коду
= машинні інструкції, які використовуються для виконання програми
= часова складність алгоритму (ЧС)
Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування).
Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму.
Використовується також ЧС в середньому ( в статистичному сенсі ), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані.
Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції.
Асимптотичні співвідношення
Для опису швидкості зростання функцій використовується О-символіка. Функція f(n) має порядок зростання O(g(n)), якщо що існують додатні константи С i n0 такі, що
f(n) <= С*g(n), для n > n0.
Позначемо функцію яка виражає залежність часової складності від кількості вхідних даних (n) через L(n) Тоді, наприклад, коли говорять, що часова складність L(n) алгоритму має порядок(ступінь) зростання O(n2) (читається як "О велике від n в квадраті, або просто "о від n в квадраті", то вважається, що існують додатні константи c i n0 такі, що для всіх n, більших або рівних n0, виконується нерівність L(n)<=cn2.
Наприклад, функція L(n) = 3n3+2n2 має порядок зростання O(n3).
Нехай n0=0 і с = 5. Очевидно, що для всіх цілих n>=0 виконується нерівність 3n3+2n2 <= 5n3.
Коли кажуть, що L(n) має ступінь зростання O(f(n)) , то вважається, що f(n) є верхньою границею швидкості зростання L(n). Щоби вказати нижню границю швидкості зростання L(n) використовують позначення ((g(n)) , що означає існування такої константи с , що для нескінченогї кількості значень n виконується нерівність L(n)>=c g(n).
Теоретичне визначення порядку зростання функції є складною математичною задачею.
На практиці визначення порядку зростання є задачею, що цілком вирішується за допомогою кількох базових принципів. Існують три правила для визначення складності:
O(с* f(n))=O(f(n))
O(f(n) + g(n)) = O(max(f(n), g(n)))
O(f(n) * g(n)) = O(f(n)) * O(g(n))
Перше правило декларує, що постійні множники не мають значення для визначення порядку зростання.
Друге правило називається "Правило сум".
Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями.
Порядок зростання скінченої послідовності програмних фрагментів (без врахування констант) дорівнює порядку зростання фрагменту з найбільшою часовою складністю.
Якщо алгоритм складається з двох фрагментів, функції часових складностей яких L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n)) відповідно, то алгоритм має ступінь зростання O(max(f(n),g(n))).
Третє правило називається "Правило добутків".
Правило добутків полягає в наступному. Якщо L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n))
відповідно, то добуток L1(n) L2(n) має ступінь зростання O(f(n)g(n)) .Прикладом може бути фрагмент програми "цикл в циклі".
Приклад.
Задані функції часової складності L(n) для чотирьох алгоритмів
1. 2. 3. 4.
Використавши правило сум і правило добутків знайдемо O(n) :
Розташуємо функції Oi(n) у порядку зростання
Функція має найбільшу ступінь зростання.
Побудуємо графіки, для k = 3,4,5; n = (1,2,…,10)
Для спрощення виберемо відповідно до к наступні поліноми , та
Побудуємо графіки :
; n = 1,2,…
Графіки показують, що існують такі значення n0 (при зростанні к значення n0 теж зростає ), починаючи з яких значення функції порядку зростання часової складності буде приймати більші значення ніж значення відповідного поліному. Це ілюструє приналежність алгоритму до класу алгоритмів з експоненціальною складністю .
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Відповідно до варіанту завдання для заданих функцій часової складності L(n) визначити асимптотичні характеристики O(n).
Розташувати отримані функції в порядку зростання асимптотичних характеристик O(n).
Скласти програму (Pascal , C), яка ілюструє клас (поліноміальний чи експоненциальний) складності алгоритму, асимптотична складність якого була визначена в п2, як найбільша. При складанні прорами передбачити можливість зміни значень к та n.
Скласти та захистити звіт з лабораторної роботи
Варіанти завдань.
1
_________________________________________________________________________________________
2
__________________________________________________________________________________________
3
__________________________________________________________________________________________
4
__________________________________________________________________________________________
5
__________________________________________________________________________________________
6
__________________________________________________________________________________________
7
__________________________________________________________________________________________
8
__________________________________________________________________________________________
9
__________________________________________________________________________________________
10
__________________________________________________________________________________________
11
__________________________________________________________________________________________
12
__________________________________________________________________________________________
13
14
15
__________________________________________________________________________________________
16
__________________________________________________________________________________________
17
__________________________________________________________________________________________
18
__________________________________________________________________________________________
19
__________________________________________________________________________________________
20
__________________________________________________________________________________________
21
__________________________________________________________________________________________
22
__________________________________________________________________________________________
23
__________________________________________________________________________________________
24
__________________________________________________________________________________________
25
Лабораторна робота № 4.
"Формальні алгоритмічні системи (ФАС). Машина Тьюрінга (МТ)".
Мета роботи:. Ознайомитись зі способами зменшення часової складності.
МЕТОДИЧНІ МАТЕРІАЛИ
Теза Тьюрінга: Будь-яка обчислювальна функція може бути реалізована на деякій машині Тьюрінга.
Математичні ФАС
Основним призначенням математичних ФАС є дослідження проблем розв’язності. Для цієї проблеми вимога елементарності кроку є необхідною. Оскільки ця вимога не може бути математично точно сформульована, вона інтерпретується як умова загальної зрозумілості. Математичні моделі ФАС ( вийнятки становлять рекурсивні функції) використовують елементарні операції типу розпізнавання символу, трасування, заміна або зміщення. Всі ці операції нагадують дитячу гру з кубиками, тому можуть вважатись загальнозрозумілими або елементарними.
Прикладом ФАС є машина Тьюрінга.
Структура МТ.
Існує низка варіантів детермінованих машин Тьюрінга: однострічкова, багатострічкова, універсальна та ін.Відмінність цих варіантів не принципова, вони зумовлені пошуком способів зменшення часової складності.
Модель однострічкової детермінованої МТ задається шісткою:
М = < A, Q, q0, qf, a0, p >,
де A – кінцева множина символів зовнішнього алфавіту,
Q – кінцева множина символів внутрішнього алфавіту,
q0 – початковий стан,
qf – кінцевий стан,
q0, qf Є Q
a0 – позначення порожньої комірки стрічки,
p – така програма, яка не може мати двох команд, у яких би збігалися два перші символи:
{A}x{Q}( {A}{L,R,S}{Q},
де L – зсувати головку вліво,
R - зсувати головку вправо,
S – головка залишається на місці.
Машини Тьюрінга мають одну і ту ж конфігурацію засобів реалізації алгоритму. У конфігурацію входять такі елементи: нескінчена нерухома стрічка, що поділена на окремі комірки, в які можна помістити тільки один символ зовнішнього алфавіту ; рухома головка, яка може стирати, записувати і зчитувати символи зовнішнього алфавиту в комірках стрічки, програма з кінцевою кількістю станів.
Ці елементи і лінії передавання повідомлень, що їх пов’язують, утворюють структуру машини Тьюрінга, яка не залежить від структури алгоритму, що моделюється. [] Ця важлива особливість мМТ дозволяє кількісно порівнювати різні алгоритми з часової, місткісної складності і складності програм.
Машина Тьюрінга як модель алгоритму відповідає визначенню алгоритму. В явному вигляді тут означені всі сім параметрів. Слід машини наочно відображає структуру алгоритму, кількість циклів програми.
Особливості роботи МТ не суперечать властивостям алгоритму. Кроки МТ дискретні і детерміновані, мають властивість масовості. Єдина властивість, яка приймається умовно – це елементарність кроку. У машині Тьюрінга крок алгоритму супроводжується декількома операціями: читання символу в комірці стрічки, пошук необхідної команди, виконання команди – операція зі змістом комірки ( залишити попередній символ, стерти його, записати новий ), операція переміщення головки ( залишити на місці, зсунути ліворуч чи праворуч). Всі ці операці, що складають крок алгоритму, є загальнозрозумілими.
Крок машини Тюрінга описується виразом {A}x{Q}x{→}x{A}x{R,L,S}x{Q}. Звідси, стан це мить, коли читаний із стрічки символ та новий символ готові до виконання нової команди.
Способи зменшення часової складності МТ .
Часова складність МТ задається послідовністю миттєвих станів машини. Місткісна складність вимірюється кількістю комірок стрічки, яка необхідна для реалізації алгоритму. Складність програми визначається кількістю команд.
Мінімізація часової складності МТ пов’язана з використанням наступних способів:
( зміна розташування початкових даних на стрічці;
( вибір місця розташування проміжних результатів;
( вибір стратегії руху головки;
( вибір початкового положення головки;
( збільшення символів зовнішнього алфавіту;
( застосування паралелізму ( багатострічкова МТ ).
Обмеженність використання МТ.
Наведені способи мінімізації часової складності, крім останньго, не мають практичного значення для комп’ютерної реалізації. МТ є ідеалізованою моделлю алгоритму. Основним пунктом її ідеалізації, як і всіх інших математичних ФАС, є неврахування апаратних витрат, необхідних для реалізації алгоритму. Ця особливість математичних ФАС не дозволяє у повній мірі використовувати досягнення теорії ФАС у проектуванні апаратно-програмних засобів. А у деяких випадках цей недолік приводить до практично неприйнятних висновків. Прикладом тому є теорема про лінійне прискорення.
Послідовність розв’язання задач на МТ.
Розміщуються дані на стрічці
Визначається необхідність використання додаткових символів і місця їх розташування
Розробляється стратегія розв’язання задачі (слід машина Тюрінга )
Будується таблиця програми.
У відповідності до сліду машина Тюрінга розробляється набір команд, які розміщуються в клітинах таблиці.
Мінімізується кількість станів (команд) не змінюючи стратегії розв’язання задачі
Основна гіпотеза теорії алгоритмів: уточнення змісту алгоритму за допомогою рекурсивних функцій, моделей алгоритму: машини Тюрінга, нормальних алгоритмів Маркова – еквівалентні один одному. Основу гіпотези складають наступні тези:
Теза Чьорча: клас рекурсивно – примітивних функцій співпадає з класом обчислювальних функцій.
Теза Тюрінга: будь-яка обчислювальна функція може бути реалізована на відповідній машині Тюрінга.
Теза Маркова: будь-який довільний потенційно-здійснюваний процес перероблення слів в деякому алфавіті може бути представлений у вигляді певного нормальних алгоритму.
Приклади.
1. Виконати операцію (Х mod 3), де Х= 100111.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.
Q
A
q0
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
m
Lq0
Rq2
Lq3
Rq4
Rq5
Rq8
1
xLq1
yLq0
Rq2
Lq3
Rq5
0
Lq1
Lq0
Rq2
Lq3
Rq4
Rq5
xLq3
yLq3
Rq8
a0
Rq2
Rq2
Lq3
Rq8
Lq6
Lq7
0Rq11
1Rq11
0Rq11
x
Rq2
0Rq4
Rq4
Rq5
yLq3
0Lq3
0Rq9
y
Rq2
0Rq5
Rq4
Rq5
0Lq3
xLq3
1Rq10
#
qf
P = 44
В алгоритмі використано наступну властивість :
Якщо С = А + В , то С mod3 =(A mod3 + B mod3) mod3
2. Виконати операцію кон’юнкції: (Х ( Y), де Х= 0101, Y = 0110.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.
Q
A
q0
q1
q2
q3
q4
q5
q6
q7
q8
a0
Lq1
Lq4
Lq5
1Rq8
0Rq8
Rq8
0
Rq0
a0Lq3
Lq2
Lq3
a0Lq7
a0Lq7
Lq6
Lq7
Rq8
1
Rq0
a0Lq2
Lq2
Lq3
a0Lq6
a0Lq7
Lq6
Lq7
Rq8
^
Rq0
qf
Lq4
Lq5
Rq0
P = 29
3. Виконати операцію переводу формата числа із десяткового в унарний : Х(10) ( Y(1), де Х= 10.
Визначити часову (L), програмну (P) та місткісну (M) складність алгоритму.
Q
A
q0
q1
q2
q3
0
9Lq0
1
Lq0
a0Rq1
a0Rq1
2
1Rq1
3
2Rq1
4
3Rq1
5
4Rq1
6
5Rq1
7
6Rq1
8
7Rq1
9
8Rq1
a0
Rq3
|Lq2
qf
|
Rq1
Rq1
Lq2
ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. Скласти програму для МТ, користуючись програмою ALGO2000.EXE
2. Визначити часову, програмну та ємністну складність алгоритму
3. Скласти та захистити звіт з лабораторної роботи
Варіанти завдань.
Номер варіанту відповідає номеру студента в журналі.
Виконати операцію Y = (X mod 3 ), де X, Y – двійкові числа. L=20
Виконати операціюY = (X mod 3), де X, Y – двійкові числа з мінімальною часовою складністю L=10
Виконати операцію Y = (X mod 3), де X, Y – десяткові числа
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
Без збереження вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
Без збереження вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
Зі збереженням вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
Зі збереженням вхідних даних.
Виконати операцію додавання двох двійкових чисел: Z= ( X+Y)
Результат розташувати на місці вхідних даних
Виконати операцію додавання двох двійкових чисел:Z= ( X+Y) з мінімальною часовою складністю
Розташування даних довільне.
Виконати операцію додавання двох десяткових чисел, Z=( X+Y)
Без збереження вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
Без збереження вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
Зі збереженням вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
Зі збереженням вхідних даних.
Виконати операцію додавання двох десяткових чисел: Z= ( X+Y)
Результат розташувати на місці вхідних даних
Виконати операцію віднімання двох двійкових чисел, Z=( X-Y)
Без збереження вхідних даних. Числ...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора