Шукати в цьому блозі

Хто Вам більше подобається і кому Ви надаєте перевагу?

РОЗДІЛ "ІНФОРМАТИКА"46-47


Аналіз алгоритмів
} Разом з поширеннямінформаційнихтехнологійзбільшивсяризикпрограмнихзбоїв. Одним ізспособівуникненняпомилок в алгоритмах та їхреалізаціяхслужатьдоказикоректності систем математичнимизасобами.
Використанняматематичногоапарату для аналізуалгоритмів і їхреалізаційназиваютьформальними методами. Формальніметодипередбачаютьзастосуванняформальнихспецифікацій і, звичайно, набору інструментів для синтаксичногоаналізу та доказивластивостейспецифікацій.Абстрагуваннявід деталей реалізаціїдозволяєвстановитивластивостісистеминезалежновідїїреалізації. Крім того, точність і однозначністьматематичнихтвердженьдозволяєуникнутибагатозначності і неточностіприроднихмов [15] .
За гіпотезоюРічардаМейса, «уникнутипомилоккращеусуненняпомилок»[16] . За гіпотезою Хоара, «доказпрограмвирішує проблему коректності, документації і сумісності» [17] . Доказкоректностіпрограмдозволяєвиявлятиїхвластивості по відношенню до всьогодіапазонувхіднихданих.Дляцьогопоняттякоректностібулорозділено на два типи:
§  Часткова коректність - програма дає правильний результат для тих випадків, коли вона завершується.
§  Повна коректність - програма завершує роботу і видає правильний результат для всіх елементів з діапазону вхідних даних.
Під час доказикоректностіпорівнюють текст програмизіспецифікацієюбажаногоспіввідношеннявхідних-вихіднихданих. Для доказівтипу Хоара цяспецифікаціямає вид тверджень, якіназиваютьпередумовою та постусловіем. В сукупності з самою програмою, їхщеназиваютьтрійкою Хоара. Эти утверждения записывают
P { Q } R
где P — это предусловие, что должно выполняться перед запуском программы Q , а R — постусловие, правильное после завершения работы программы.
Формальные методы были успешно применены для широкого круга задач, в частности: разработке электронных схем, искусственного интеллекта, автоматических систем на железной дороге, верификациимикропроцессоров , спецификации стандартов и спецификации и верификации программ

Алгоритм пошуку рядка
Матеріал з Вікіпедії — вільної енциклопедії.
Алгори́тимипо́шукурядка́ (англ. stringsearchingalgorithms) — важливий клас рядкових алгоритмів, що намагаються знайти місце де один або декілька текстових рядків (зразків, англ. pattern) входять у довший рядок або текст.
Зміст
·         4 Джерела
[ред.]Постановка задачі
Формальна постановка задачі пошуку рядка (англ. string-matchingproblem) така:
Нехай текст задано у вигляді масиву   довжини  , а зразок — масиву   довжини  . Передбачається, що елементи масивів — символи із скінченного алфавіту  . Наприклад, алфавіт може мати вигляд   чи  .
Зразок   зустрічається у тексті   зі зсувом   (англ. occurswithshifts), якщо   і   (іншими словами  ).
Якщо зразок   зустрічається у тексті   зі зсувом  , то величину  називають допустимим зсувом (англ. validshift); інакше її називаютьнедопустимим зсувом (англ. invalidshift)
Задача полягає в знаходженні всіх допустимих зсувів, з якими зразок  зустрічається у тексті  .
[ред.]Термінологія
 — множина всіх рядкув скінченної довжини, утворенних за допомогою символів алфавіту  . Порожній рядок   також належить  .
Довжина рядка   позначається як  . Конкатенація (об'єднання) двох рядків   і   записується як  , її довжина відповідно дорівнює  . Конкатенація складається з символів рядка   після яких записані символи рядка  .
Приклад:
Рядок   називається префіксом рядка   (позначається  ), якщо  . Якщо  , то  .
Аналогічно, рядок   називається суфіксом рядка   (позначається  ), якщо  .
Пустий рядок є одночастно префіксом і суфіксом будь-якого рядка.
Відношення   і   є транзитивними.
[ред.]Лема про суфікси, що перекриваються
Припустимо, що  ,   і   — рядки, для яких виконується співвідношення   і  . Тоді, якщо  , то  ; якщо  , то  . Якщо  , то  .
Доведення: Всі три випадки розібрані на малюнку:

Позначимо k-символьний префікс
   зразка   через  . Таким чином,   і  . Аналогічно через  позначимо k-символьний префікс тексту  .
За допомогою цих позначень, задачу пошуку рядка можна сформулювати, як задачу виявлення всіх зсувів  , таких що,  .
[ред.]Базова класифікація алгоритмів
Різноманітні алгоритми розв'язання цієї задачі можна класифікувати за кількістю зразків, що обробляються одночасно. Крім того, алгоритми мають різну складність роботи. Окремо розглядається складність передобробки (передобробка здійснюється або тільки для тексту і не залежить від зразків, або ж тільки для зразків і не залежить від тексту), і складність самого пошуку.
[ред.]Алгоритмипошуку для одного зразка
Алгоритм
Складність передобробки
Складність пошуку
0 (без передобробки)
Θ(n m)
Θ(m)
в середньому Θ(n+m),
в найгіршому випадку Θ(n m)
Пошук за допомогоюскінченного автомата
Θ(m |Σ|)
Θ(n)
Θ(m)
Θ(n)
Θ(m + |Σ|)
Ω(n/m), O(n)
Θ(m + |Σ|)
Θ(n)
[ред.]Алгоритмипошукускінченноїмножинизразків
[ред.]Алгоритмипошукунеобмеженоїмножинизразків
Для пошуку зразків, що утворюють нескінченну (або дуже велику) множину, користуються формальними граматиками і регулярними виразами.
[ред.]Інші класифікації
Класифікація, що бере наявність переобробки, за основний критерій:
Класи алгоритмів пошуку рядку
Текст не передобробляється
Текст передобробляється
Зразки не передобробляються
Елементарні алгоритми (англ. Elementaryalgorithms)
Індексуючі методи (англ. Indexmethods)
Зразки передобробляються
Конструктивні пошукові системи (англ. Constructed search engines)
Підписуючі методи (англ. Signature   methods)
[ред.]Індексуючіметоди
Швидкі алгоритми пошуку використовують передобробку тексту. Входження зразка може бути швидко знайдене, якщо для тексту побудувати індекс підрядків (наприклад, суфіксне дерево чи суфіксний масив). Так, суфіксне дерево можна побудувати за час Θ(n), а всі z входжень зразка можна знайти за час O(n + z) (якщо вважати, що розмір алфавіту — константа).
[ред.]Інші варіанти
Деякі алгоритми пошуку, такі як пошук тріграм, замість точного входження зразка, шукають частину тексту, що найбільш близька до зразка.
масиви використовують коли потрібно занести якусь інформацію у вигляді таблиці. Наприклад, на метеостанціях кожен час вимірюють температуру повітря і значення вимірів за добу записуються в таблицю. (Демонструю кодоплівку 2).  
Температура, 0С 17 15 19 21 14 19,5 17,5 15,5 16 ... 16,5 20
Уявіть тепер, що нам потрібно знайти найбільшу та найменшу температуру за добу. Ми можемо скористатися алгоритмом пошуку найбільшого елемента та алгоритмом пошуку найменшого елемента. А тепер уявіть, що в нас елементи таблиці  розміщені по зростанню. (Демонструю кодоплівку 3).
Температура, 0С 14 15 15,5 16 16,5 17 17,5 19 19,5 ... 20 21
То який елемент таблиці буде найбільшим, а який – найменшим. Останній елемент буде найбільшим, а перший – найменшим.
Таблиця в якій елементи розміщенні по зростанню або спаданню називається впорядкованою або відсортованою. А сам процес розміщення елементів по зростанню (спаданню) називається сортуванням. Отже.
 Сортування – це процес розміщення елементів таблиці (масиву) по зростанню або спаданню.
Є такі алгоритми сортування масивів:
• Алгоритм “бульбашкового” сортування
• Алгоритм пірамідального сортування.
• Алгоритм швидкого сортування.
Ми з вами розглянемо найпростіший (і найгірший з погляду витрат часу) спосіб сортування масиву. Нехай А[1], А[2], ... , А[n] – масив з довільними значеннями елементів. Порівняємо А[1] і А[2]: якщо А[1]  А[2], то поміняємо їхнього значення місцями. Потім порівняємо А[2] А[3] і при необхідності обміняємо їхнього значення. У результаті А[3] має найбільше значення серед А[1], А[2], А[3]. 
Для всіх і від 1 до n-1 виконати
Якщо А[i]>A[i+1], то
Значення А[i] і A[i+1] обмінюються
Якщо значення елементів розглядати  як розміри бульбашок, то ці порівняння й обміни схожі на те, як великі бульбашки відтискують менші вниз і спливають на верх. Тому найбільша бульбашка стає верхньою, тобто останній елемент А має найбільше значення. Наприклад,   послідовність значень 3, 4, 2, 1 перетвориться в 3, 2, 1, 4.
Далі почнемо всі спочатку і перемістимо другий по величині елемент в передостанній елемент А(n-1), перетворивши, наприклад 3,2,1,4 у 2,1,3,4. Потім третє по величині значення перемістимо в А(n-2) і т.д. На останньому кроці порівнюються  лише А1 і А2 (їхні значення обмінюються при необхідності).
Метод полягає у відшуканні найбільших значень елементів масиву і перестановці їх на початок масиву.
Алгоритм сортування
Матеріал з Вікіпедії — вільної енциклопедії.
Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
Зміст
·         6 Див. також
[ред.]Постановка задачі
Вхід алгоритму: послідовність з   чисел 
Вихід алгоритму: перестановка   вхідної послідовності таким чином, що   ( — перестановка послідовності чисел  ).
Вхідна послідовність найчастіше представляється у вигляді n-елементного масиву, хоча може мати й інше представлення, наприклад, у вигляді зв'язного списку.


Вхідна послідовність: (5, 6 ,1 ,8 ,5 ,7, 4)
Вихідна послідовність: (1, 4, 5, 5, 6, 7, 8)
[ред.]Структури даних
Детальніше: Структура даних
На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше, кожен такий елемент є записом (англ. record). В кожному записі є ключ (англ. key), по якому власне і здійснюється впорядкування, в той же час є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом з ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого обсягу, то з метою звести до мінімуму переписування великих обсягів інформації, впорядкування відбувається не у самому масиві елементів, а в масиві вказівників на елементи.
Сам метод сортування не залежить від того, чи впорядковуються тільки числа, чи також і супутня інформація, тому при описі алгоритмів для простоти припускають, що елементи є числами.
[ред.]Характеристики алгоритмів
Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є: час необхідний на впорядкування n-елементного масиву і додаткова пам'ять необхідна для впорядкування. Крім цих двох характеристик, сортування буває стабільнимчи нестабільним, з використанням додаткової інформації про елементи, чи без використання.
Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є  , це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.
Інший клас алгоритмів здійснює впорядкування за час  . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
[ред.]Теорема про найкращий час сортування
Якщо алгоритм сортування в своїй роботі спирається тільки на операції порівняння двох об'єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за   в найгіршому випадку.
[ред.]Доведення
На кожному кроці алгоритм проводить одне порівняння, результатом якого є один з двох варіантів:
1.    
2.    
В залежності від результату порівняння алгоритм буде робити подальші дії. Отже, всю роботу алгоритму можна представити у вигляді бінарного дерева в листах якого лежать можливі перестановки вхідного масиву.
Отже, дерево має   листів, а висота дерева є  . Час роботи в найгіршому випадку пропорційний висоті дерева: 

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


РЕКУРСИВНІ ФУНКЦІЇ ТА АЛГОРИТМИ

Взагалі багато об'єктів різної природи, не тільки функції, визначаються як рекурсивні.
Приклад 1. Множинанатуральних чисел.
1.     1 - натуральне число;
2.     Якщо n - натуральне число, то n+1 - натуральне число.
Приклад 2. Двійкові дерева.
1.     o - дерево (пусте, одна изольована вершина).
2.     якщо t1 та t2 - дерева, то
є деревами.
Приклад 3.
ліва крива Дракона left(S1,S2) порядку 1
права крива Дракона right(S1,S2) порядку 1
2) Якщо ( S1, S2, ..., S2n-1 ) - крива Дракона порядку n-1, то
( left (S11, S12), right (S21, S22), ..., right (S2n-11, S2n-12) )
- крива Дракона порядку n.
Принципові властивості рекурсивного визначення:
  1. визначення об'єкту самого через себе, але з іншими параметрами;
  2. завершеність ланцюжка визначень на деякому значенні аргументів.
У програмуваннірекурсивнимиможуть бути не тількифункції, але йпроцедури (з цим ми познайомимосянижче).
При програмуваннірекурсіїслідвпевнитисяутому, що задачу не можналегшерозв'язати за допомогоюітеративних процедур. Рекурсіювикористовувативартотоді, коли нерекурсивнийпідхід сильно ускладнюєпрограмуванняабо не призводить до сильного зменшення часу роботи алгоритму, об'ємупам'яті для роботитощо.
Приклади. Усінайбільшвідоміприкладизастосуваннярекурсії, фактично є прикладом того, як не слід застосовуватирекурсію.
1. n! := ( if n = 0 then 1 else n * (n-1)! );
Програмуванняцього фрагменту призведе до копіюванняу сегмент стеку n рядків сегменту данихпроцедуриобчисленняфакторіалу та адрес повернення. 
Простішенаписати
f := 1;
if n > 0 then
for i := 1 to n do
f := f*i;
що потребує лише використання параметру циклу.
Щебільшконтрастним є наступний приклад.
2. Біноміальнікоефіцієнти:
    C(n,m) := (if (m = 0) or (m = n)
then 1
else C(n-1,m-1) + C(n-1,m));
Цеприведе до ~ 2n викликівпроцедурою C(n,m) самою себе з меншими параметрами. Міжтим, багатовикликівбудутьдублюватися, буде багатовикликів з однаковими параметрами. Навітьзастосовуючисаме формулу біноміальноїтеореми, можнаобмежитисялише (m + 1)(n - m + 1) викликів, щозначноменше 2n при великих n. Але значнокращевикористати формулу
( 1 )
яка програмується за допомогою одного циклу і не призводить до переповненьрозрядноїсітки.
3. Числа Фібоначчі.
f(0) = 0; f(1) = 1; f(n) = f(n-2) + f(n-1).
Картина повністю аналогічна до такої у прикладі 2. 
Рекурсивна функція:
function Fibonacci (n: Word): LongInt;
begin
if (n = 0) or (n = 1) then Fibonacci := n;
else
Fibonacci := Fibonacci(n-2) + Fibonacci(n-1)
end;
Попри свою "естетичнувитонченість" вимагає 2n викликів, щоможе привести до переповнення стеку.
Але значнопростіше числа Фібоначчіобчислитипослідовно:
if (n = 0) or (n = 1)
then f := n
else begin
f1 := 0; f2 := 1;
for i = 1 to n begin
f0 := f1;
f1 := f2;
f2 := f1 + f0;
end;
end;
Поступовозсуваючизначення, обчислюємо числа цього ряду, займаючилише три коміркипам'яті та не дублюючивикликів з однаковими аргументами.
Не слідвикористовуватирекурсію, якщо є очевиднийітеративнийрозв'язок.
Будь-яку рекурсивну-перекурсивнупрограмуврешті-решт ЕОМ перекладає у машиновікоди, середякихрекурсією і не пахне. Цеозначає,що будь-яку задачу можнарозв'язати без застосуваннярекурсії. Але є випадки, коли застосуваннярекурсивнихалгоритмів є виправданим. Це в першу чергу, область штучногоінтелекту.
Приклади, що ми розглянемодалі, розглянуто у Н.Вірта [2,3] та у книзі [4], де всіпрограмивикладено на Фортрані - мовою, що не дозволяєрекурсії.
Вправи.
1.     Напишіть програму для обчислення біноміальних коефіцієнтів
o    через використання програми-функції для обчислення факторіалу;
o    без її використання - за допомогою формули (1).
Визначіть область значень аргументів, для яких вона ще працює.
2.     Напишіть програму-функцію, що для даного дійсного аргументу перевіряла б, чи є він натуральним числом. При цьому обов'язково використайте рекурсивне визначення натурального числа.
Контрольніпитання.
1.     Що таке рекурсія?
2.     Що таке ітерація?
3.     Чи існують задачі, що неможливо запрограмувати без застосування рекурсії? Наведіть приклади.


РЕКУРСИВНА ПРОГРАМА ПОШУКУ МІНІМУМА
Ясно, щоякщодеякиймасивподілити на двічастини, відшукатимінімальніелементи у обохчастинах, а з них взятименший, то це і буде мінімальнийелемент у масиві. Якщомасив (підмасив) складається з одного елементу, то він і є найменшим.
Найменшийелементпідмасиву a[n]..a[m] можнавизначити як
Min(a, n, m) = min(Min(a, n, (n+m) / 2), Min(a, (n+m) / 2, m)), якщо n<m; 
Min(a, n, m) = a[n],
 якщо n = m.
Тут через min(x, y) позначеноменше з x та y, а через Min(a, n, m) - найменшийелементпідмасиву a[n .. m].
Відповіднапрограма на Паскалімаєвигляд
typearr = array[0..N-1] of Integer;
var a : arr;
 ...
function Min(var a: arr; n, m: 0..N-1): Integer;
var
x,y : Integer;
begin
if n > m then Halt;
if n = m then Min := a[n]
else begin
x := Min(a, n, (n+m) div 2]);
y := Min(a, (n+m) div 2 + 1, m);
if x < y then Min := x
else Min := y
end
end;
Цей алгоритм вимагає ~ n звертань до підпрограми, тобто є у порівнянні з попередніми прикладами більш економним. А от навіщо перший параметр - масив задається зі словомvar?


Жа́дібнийалгори́тм — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення. Легкий в реалізації і часто дужеефективний за часом виконання.Багато задач не можуть бути розв'язані з йогодопомогою.
Наприклад, використанняжадібноїстратегії для задачікомівояжерапороджуєнаступний алгоритм: «На кожному етапівибиратинайближче з невідвіданихміст».
Зміст
·         1 Специфіка
·         4 Приклади
·         5 Примітки
·         6 Дивіться також
[ред.]Специфіка
Зазвичай, жадібний алгоритм базується на п'яти принципах:
1.    Набір можливих варіантів, з яких робиться вибір;
2.    Функція вибору, за допомогою якої знаходиться найкращий варіант;
3.    Функція придатності, яка визначає придатність отриманого набору;
4.    Функція цілі, оцінює цінність рішення, не виражена явно;
5.    Функція розв'язку, яка вказує на те, що знайдене кінцеве рішення.
[ред.]Визначанняпридатності
Придатнийнабірваріантів — такий, щообіцяє не просто отриманнярішення, а отримання оптимального рішеннязадачі.
На відмінувід динамічногопрограмування, щорозв'язує проблему знизу догори, жадібнастратегіяробитьцезгори донизу, роблячи один жадібнийвибір за іншим, зводячивелику задачу до малої.
[ред.]Критерії застосування
Жадібний алгоритм добре розв'язуєдеякізадачі, а інші — ні. Більшість задач, для якихвінспрацьовує добре, маютьдвівластивості: по-перше, до них можливозастосувати Принцип жадібноговибору, по-друге, вони маютьвластивість Оптимальноїпідструктури.
[ред.]Принцип жадібноговибору
До оптимізаційноїзадачіможназастосувати принцип жадібноговибору, якщопослідовність локально оптимальнихвиборівдає глобально оптимальнийрозв'язок. В типовому випадкудоведенняоптимальностімаєтаку схему: спочатку доводиться, щожадібнийвибір на першомуетапі не унеможливлює шлях до оптимального розв'язку: для всякого розв'язку є інше, узгодженеізжадібним і не гіршепершого. Далі доводиться, щопідзадача, щовиниклапісляжадібноговибору на першомуетапі, аналогічнапочатковій, і міркуваннязакінчується за індукцією. Інакшекажучи, жадібний алгоритм ніколи не переглядаєсвоїпопереднівибори для здійсненнянаступного, на відмінувіддинамічногопрограмування.
[ред.]Властивістьоптимальноїпідструктури
«Задача має оптимальнупідструктуру, якщооптимальнерішеннязадачіміститьоптимальнерішення для підзадач»[1]. Інакшекажучи, задача маєоптимальнупідструктуру, якщокоженнаступнийкрокведе до оптимального розв'язку. Прикладом 'неоптимальноїпідструктури' може бути ситуація в шахах, коли взяття ферзя (хороший наступнийкрок) веде до програшупартії в цілому.
[ред.]Коли алгоритми жадібного типу зазнають невдачі
Жадібніалгоритмиможнахарактеризувати як 'короткозорі' і 'невідновлювані'. Вони ідеальнілише для задач з 'оптимальною підструктурою'. Попри це, жадібніалгоритминайкращепідходять для простих задач. Для багатьохінших задач жадібніалгоритмизазнаютьневдачі у продукуванніоптимальногорозв'язку, і можутьнавітьвидатинайгірший з можливихрозв'язків. Один з прикладів — алгоритм найближчогосусідньогоміста, описаний вище.
Також у задачірозміну монет, якщо є тільки 25, 10 і 4-центові монети, жадібний алгоритм не зможезробитирозмін 41 цента.
[ред.]Приклади
[ред.]Розмін монет
Задача. Монетна система деякоїдержавискладається з монет вартістю  . Вимагаєтьсявидати суму S найменшоюможливоюкількістю монет.
Жадібний алгоритм розв'язанняцієїзадачітакий. Беремонайбільшуможливукількість монет вартості  :  . Так само знаходимоскількипотрібно монет меншогономіналу, і т.д.
Для цієїзадачіжадібний алгоритм не завждидаєправильнерішення. Наприклад, суму в 10 копійок монетами в 1, 5 і 6 коп. жадібний алгоритм розміняє так: 6 коп. - 1 шт., 1 коп. - 4 шт., в той час як правильнерішення 2 монети по 5 копійок. Тим не менш, на всіхреальнихмонетних системах жадібний алгоритм видаєправильнувідповідь.
[ред.]Вибір заявок
Задача. На конференції, щобвідвестибільше часу на неформальнеспілкування, різнісекціїрознесли по різнихаудиторіях. Вченийізнадзвичайно широкими інтересамибажаєвідвідатидекількадоповідей в різнихсекціях. Відомі початок   і кінець   кожноїдоповіді. Визначити, яку максимальнукількістьдоповідейможнавідвідати.
Наведем жадібний алгоритм, якийрозв'язуєцю задачу. При цьомувважатимемо, що заявки впорядковані за зростанням часу закінчення. Якщоце не так, то можнавідсортуватиїх за час  ; заявки з однаковим часом закінченнярозташовуємо в довільному порядку.
Activity-Selector(s,f)
1.     length[s]
2.   
3.   
4.    for   to n
§  doif 
§  then    {i}
§ 
5.    return A
На вхід алгоритму подаютьсямасиви початку і закінченнядоповідей. Множина Аскладається з номеріввибраних заявок, а j - номер наступної заявки. Жадібний алгоритм шукає заявку, щопочинається не ранішезакінчення j-ї, потімзнайдену заявку включає в А, а j присвоюєїї номер.
Алгоритм працює за  , тобто сортування плюс вибірка. На кожному кроціобираєтьсянайкращерішення. Покажемо, що в результатіотримаємооптимальнерішення.
Доведення. Зауважимо, щовсі заявки відсортовані за неспаданням часу завершення. Заявка номер 1 однозначно входить в оптимальнерішення, (якщоні, замінимонайпершу заявку в оптимумі на неї, гіршевідцього не стане). Відкинувшивсі заявки, щосуперечатьпершій, отримаємопочаткову задачу з меншоюкількістю заявок. Розмірковуючиіндуктивно, приходимо до оптимального рішення.

СКЛАДНІСТЬ АЛГОРИТМІВ
Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту, необхідного для розв'язання задачі часу та розміру пам'яті при збільшені вхідних даних. З кожною конкретною задачею пов'яжемо число, яке назвемо розміром задачі і яке б виражало міру кількості вхідних даних. Наприклад, розміром задачі множення матриць може бути найбільший розмір матриць-співмножників. Розміром задачі про графи може бути число ребер даного графа.
Час, витрачений на обчислення при виконанні алгоритму, являє собою суму часів окремих виконаних операторів. Програму, написану на мові високого рівня, можна перетворити прямим ( хоча і не простим) шляхом в програму на машинному коді заданої ЕОМ. Це в принципі дає метод оцінки часу виконання вказаної програми, але такий підхід орієнтований на конкретну ЕОМ і не дає загальної залежності часу обчислення від розмірів задачі. В області аналізу та побудови алгоритмів прийнято виражати час виконання, як і будь-яку іншу міру ефективності, з точністю до мультиплікативної константи. Це, зазвичай, робиться шляхом підрахунку лише певних ключових операцій, виконаних алгоритмом (що легко здійснити, аналізуючи версію цього алгоритму, записану на мові високого рівня). Такий підхід абсолютно правомірний при визначені нижніх оцінок часу виконання, оскільки невраховані операції можуть лише збільшити їх; однак при роботі з верхніми оцінками ми повинні впевнитись у тому, що вклад вибраних ключових операцій в сумі відрізняється не більше, ніж в константу раз від вкладу усіх операцій, виконаних алгоритмом.
Означення 1.2 Час, який витрачається алгоритмом, як функція розміру задачі, наз. часовою складністю цього алгоритму. Граничну поведінку цієї складності при збільшені розміру задачі наз. асимптотичною часовою складністю. Аналогічно, можна виділити об'ємну складність таасимптотичну об'ємну складність.
Просторова та часова складності як функції від розмірів задачі є дві фундаментальні оцінки ефективності при аналізі алгоритмів.
Кнут популяризував апарат позначень , які відрізняють верхні та нижні оцінки.
Оцінки складності.
(верхні оцінки);
(нижні оцінки);

(ефективні оцінки).
Таким чином, O(f(N)) використовується для вказання верхніх оцінок швидкості росту функцій або для вказання множини усіх функцій, які ростуть не швидше, ніж f(N). Наприклад, коли говорять, що алгоритм виконується за час O(f(N)), то це означає, що час його виконання обмежений зверху значенням O(f(N)) для всіх входів розміру n. Так як при цьому передбачається, що час виконання в найгіршому випадку також обмежений величиною O(f(N)), то це просто час виконання даного алгоритму.
W(f(N)) використовується для вказання нижніх оцінок швидкості росту функцій або для вказання множини усіх функцій, які ростуть не повільніше, ніж f(N). Аналогічний спосіб, але для нижніх оцінок. Нарешті, q (f(N)) використовується для вказання функцій того ж порядку, що і f(N);цей спосіб потрібний для опису "оптимальних" алгоритмів. Якщо алгоритм обробляє входи розміру n за час cn2, де c-деяка константа, то часова складність цього алгоритму є O(n2), для усіх n, крім скінченої ( можливо порожньої) множини, невід'ємних значень. Наприклад, запис   позначає клас функцій, які мають швидкість росту не меншу за n, але не більшу за n2.

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

Алгоритм - набір інструкцій , що описують порядок дій виконавця для досягнення результату рішення задачі за кінцевий час. У старій трактуванні замість слова «порядок» використовувалося слово «послідовність», але в міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовуються процесор і операційна система.

Алгоритм маєтаківластивості:
1. Дискретність. Цявластивістьполягає в тому, що алгоритм повинен представлятипроцесвирішеннязавдання як послідовневиконанняпростихкроків. При цьому для виконання кожного кроку алгоритму потрібнокінцевийвідрізок часу, тобто перетвореннявихіднихданих у результат здійснюється в часі дискретно.
2. Визначеність. Кожне правило алгоритму має бути чітким, однозначним.
3. Результативність. Алгоритм повинен призводити до вирішення за кінцеве число кроків.
4. Масовість. Алгоритм рішеннязадачірозробляється в загальномувигляді, тобто він повинен бути застосовний для деякогокласу задач, щорозрізняютьсялишевихіднимиданими.
5. Правильність. Алгоритм правильний, якщойоговиконаннядаєправильнірезультативирішенняпоставленогозавдання.



Немає коментарів:

Дописати коментар