Лекція " ВСТУП. АЛГОРИТМИ. ВЛАСТИВОСТІ АЛГОРИТМІВ."

Тема 1. ВСТУП. АЛГОРИТМИ. ВЛАСТИВОСТІ АЛГОРИТМІВ.

План:

1. Поняття алгоритму.
2. Історія розвитку теорії алгоритмів.
3. Властивості алгоритму.
4. Класи алгоритмів.

1. Поняття алгоритму

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

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

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

Алгоритм – одне з головних понять сучасної науки. З настанням ери інформатики – його можна віднести до найважливіших факторів цивілізації. Сучасна система поглядів на інформатику й інформацію ґрунтується на тому, що інформація є новим, надзвичайно коштовним ресурсом людства поряд з іншими, давно відомими, наприклад, енергетичними, природними, людськими. Причому цей ресурс, на відміну від інших перерахованих, не зменшується, а навпаки - росте. Це ресурс - що розширюється.

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

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

Алгоритм (algorithm) — це формально описана обчислювальна процедура, яка отримує вхідні дані (input), що називаються входом алгоритму або його аргументом, і видає результат обчислень на вихід (output).

Алгоритм являє собою послідовність обчислювальних кроків, що перетворюють вхідні величини на вихідні.

Алгоритми будують для розв’язання тих чи інших обчислювальних задач (computational problems). У постановці задачі у загальних рисах задається взаємодія між входом і виходом. В алгоритмі описується конкретна обчислювальна процедура, за допомогою якої вдається домогтися виконання зазначених взаємодій. Алгоритм вважається коректним (correct), якщо для будь-якого допустимого входу він закінчує роботу і видає результат, який задовольняє вимогам задачі. В цьому випадку говорять, алгоритм розв'язує дану обчислювальну задачу. Якщо алгоритм некоректний, то для деяких входів він може взагалі не завершити свою роботу або видати неправильну відповідь.

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

Форми запису алгоритму :

• словесна або вербальна(мовна, формульно-словесная);
• псевдокод(формальні алгоритмічні мови);
• схематична: графічна(блок-схеми, виконується з вимогами стандарту).

Властивості алгоритмів:

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

Алгоритм повинен мати наступні п’ять якостей:

• Обмеженість в часі – робота алгоритму обов’язково повинна завершитись через деякий розумний період часу.
• Правильність – алгоритм повинен знаходити правильне, а не будь-яке рішення.
• Детермінованість – скільки б разів не виконувався алгоритм з однаковими вхідними даними, результат повинен бути однаковим.
• Скінченність – опис роботи алгоритму повинен мати скінчену кількість кроків.
• Однозначність – кожний крок алгоритму повинен інтерпретуватися однозначно.

2. Історія розвитку теорії алгоритмів

Історія в його величності Алгоритму дуже довга, а от у теорії алгоритмів, як наукового напрямку порівняно коротка.

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

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

Протягом тривалого часу, аж до початку XX століття саме слово «алгоритм» уживалося в стійкому сполученні «алгоритм Евкліда». Для опису покрокового рішення інших математичних задач вживалося слово «метод».

Слово «алгоритм», як стверджують історики математики, з'явилося 12 століть назад і означало не термін, а ім'я. Узбецький математик Аль-Хорезмі, вчений, якому математика зобов'язана багатьма відкриттями, - був відомий європейським математикам як Алгоризмі.

Саме із трактату Аль-Хорезмі по арифметиці почалося знайомство Європи з алгоритмами - процедурами для виконання арифметичних операцій. Тобто алгоритм, вірніше як алгоризм, - розумілося як керівництво до дії для рішення завдань.

Подальший розвиток математики затвердив ту думку, що рішення будь-якої проблеми повинне бути алгоритмічним. Декарт, Лейбниц, Гільберт, особливо останній стимулював алгоритмічні дослідження, запропонувавши в 1900 році на міжнародному математичному конгресі свої знамениті 23 проблеми.

Для уточнення поняття алгоритму були поширені 2 точки зору :

1.Всі проблеми є алгоритмічно вирішеними. Просто ще не існують знання для їхньої побудови.

2.Існують класи завдань, для рішення яких взагалі не існує алгоритмів. Це дуже сильне твердження, тому що воно поширюється на все майбутнє.

Початком відліку сучасної теорії алгоритмів можна вважати роботу німецького математика Курта Гьоделя (1931 рік - теорема про неповноту символьних логік), у якій було

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

Перші фундаментальні роботи з теорії алгоритмів були опубліковані незалежно в 1936 році роком Аланом Т’юрингом, Алоізом Черчем і Емілем Постом. Запропоновані ними машина Т’юринга, машина Поста й лямбда-вирахування Черча були еквівалентними формалізмами алгоритму. Сформульовані ними тези (Поста й Черча-Т’юринга) стверджували еквівалентність запропонованих ними формальних систем і інтуїтивного поняття алгоритму. Важливим розвитком цих робіт стало формулювання й доказ алгоритмічно нерозв'язних проблем.

В 1950 роки істотний внесок у теорію алгоритмів внесли роботи Колмогорова й Маркова.

Напрямки розвитку теорії алгоритмів

До 1960-70 років набрали чинності наступні напрямки в теорії алгоритмів:

•класична теорія алгоритмів (формулювання завдань у термінах формальних мов, поняття задачі вирішення, введення класів складності тощо);

•теорія асимптотичного аналізу алгоритмів (поняття складності й

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

урозвиток якої внесли істотний вклад Кнут, Ахо, Хопкрофт, Ульман, Карп;

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

варто вважати фундаментальні праці.

Визначення алгоритму

Сучасне визначення алгоритму може бути сформульоване таким чином:

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

переробки допустимих вхідних даних у шукані результати.

або іншими словами

•алгоритм - це формально описана обчислювальна процедура, що одержує вхідні дані, що називаються входом алгоритму або його аргументом, і подає результат обчислень на вихід.

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

Відомими є наступні визначення алгоритму:

«Алгоритм — це кінцевий набір правил, який визначає послідовність операцій для розв’язання конкретної множини задач і володіє наступними важливими рисами: кінцевість, визначеність, введення, выведення, ефективність». (Д. Э. Кнут)

«Алгоритм — це всяка система обчислень, що виконуються за суворо визначеними правилами і після виконання деякої кількості кроків призводить до розавязання поставленої задачі». (А. Колмогоров)

«Алгоритм — це точний опис обчислювального процесу, що виконується від варійованих вхідних даних до шуканих результатів». (А. Марков).

«Алгоритм — точний опис у визначеному порядку деякої системи операцій, що ведуть до розв’язання всіх задач даного типу». (Філософсікий словник / Під ред. – М. Розенталя)

«Алгоритм — суворо детермінована послідовність дій, що описує процес перетворення об’єкту з початкового стану в кінцевий за допомогою зрозумілих виконавцю команд». (М.

Угринович)

«Алгоритм — це суворо визначена послідовність дій, направлена до досягнення цілей за кінцеву кількість кроків». (Є.Привалов).

«Алгоритм — це послідовність дій, яка або призводить до розв’язання задачі, або пояснює чому цей розв’язок отримати неможливо».

Найбільш розповсюдженим останній час є таке визначення:

«Алгоритм – це набір достеменно викладених інструкцій, що описує послідовність дій

виконавцю для досягнення результату, рішення поставленої задачі за скінчений час.»

Сучасне значення слова “алгоритм” багато в чому є аналогічним таким поняттям, як рецепт, процес, метод, спосіб, процедура, програма, але все-таки алгоритм має ще й додатковий значеннєвий відтінок. Крім цього він має ряд важливих особливостей або

характеристик

3. Властивості алгоритму

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

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

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

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

Зрозумілість – алгоритм повинен бути зрозумілим конкретному виконавцеві, що повинен реалізувати кожну команду алгоритму в суворій відповідності до призначення.

Результативність (кінцівка, збіжність) – виконання алгоритму повинне кінчатися результатом або інформацією про те, що результат не може бути отриманим.

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

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

Узагальнюючи результати різних розділів теорії алгоритмів можна виділити наступні цілі

йспіввіднесені з ними завдання, що розв'язуються в теорії алгоритмів:

–формалізація поняття «алгоритм» і дослідження формальних алгоритмічних

систем;

–формальний доказ алгоритмічної нерозв'язності ряду завдань;

–класифікація завдань, визначення й дослідження класів складності;

–асимптотичний аналіз складності алгоритмів;

–дослідження й аналіз рекурсивних алгоритмів;

–одержання явних функцій трудомісткості з метою порівняльного аналізу

алгоритмів;

–розробка критеріїв порівняльної оцінки якості алгоритмів.

Отримані в теорії алгоритмів теоретичні результати знаходять досить широке практичне застосування, при цьому можна виділити наступні два аспекти:

Теоретичний аспект: при дослідженні деякого завдання результати теорії алгоритмів дозволяють відповістити на запитання – чи є це завдання в принципі алгоритмічно має розв'язок.

Практичний аспект: методи й методики теорії алгоритмів (в основному розділі асимптотичного й практичного аналізу) дозволяють здійснити:

–раціональний вибір з відомої множини алгоритмів рішення даного завдання з урахуванням особливостей їхнього застосування (наприклад, при обмеженнях на розмірність вхідних даних або обсягу додаткової пам'яті);

–одержання тимчасових оцінок рішення складних завдань;

–одержання достовірних оцінок неможливості рішення деякого завдання за певний час, що важливо для криптографічних методів;

розробку й удосконалювання ефективних алгоритмів рішення завдань в області обробки

інформації на основі практичного аналізу.

4.Класи алгоритмів

Науковці виділяють три основні класи алгоритмів:

• Обчислювальні алгоритми – це такі, які працюють з порівняно простими видами даних, наприклад, числами, векторами, матрицями.
• Інформаційні алгоритми являють собою набір простих процедур, що працюють з великими обсягами інформації. Прикладом такої процедури може бути пошук необхідної числової або символьної інформації, що відповідає певним ознакам. Ефективність роботи цих алгоритмів залежить від організації даних.
• Керуючі алгоритми характерні тим, що дані до них надходять від зовнішніх процесів, якими вони керують. Результатами роботи цих алгоритмів є вироблення своєчасної управляючої реакції на швидку зміну вхідних даних.