Тема 14. Теорія алгоритмів. Основні поняття і визначення.
Теорія алгоритмів. Основні поняття і визначення.
Питання теми
1. Поняття алгоритму.
2. Інтуїтивне поняття алгоритму.
3. Приклади алгоритмів.
Основні терміни теми : алгоритм, теорія алгоритмів.
1. Поняття алгоритму.
Поняття алгоритму є не тільки центральним поняттям теорії алгоритмів, не тільки одним з головних понять математики взагалі, але одним з головних понять сучасної науки. Більш того, сьогодні, з настанням ери інформатики, алгоритми стають одним з найважливіших факторів цивілізації.
Успенський В.А., Семенов А.Л.
Точне поняття "алгоритм" було вироблено лише в тридцятих роках XX століття. До цього математики задовольнялися інтуїтивним поняттям алгоритму. Це пояснюється тим, що до середини XIX століття математика мало справу в основному з числами й обчисленнями. Поняття алгоритму ототожнювалося з поняттям методу обчислень. Усе різноманіття обчислень комбінувалося з чітко визначених операцій арифметики, тригонометрії й аналізу. Тому поняття методу обчислення вважалося інтуїтивно ясним і не було потреби в спеціальних дослідженнях.
Нові більш тверді вимоги до строгості стимулювалися в основному математикою нечислових об'єктів у другій половині XIX століття. Одною з вирішальних обставин, що привели до перегляду основ математики, з'явилося створення Кантором теорії множин.
Досвід парадоксів теорії множин навчив математика вкрай обережно звертатися з нескінченністю і навіть про нескінченність міркувати за допомогою фінітних методів. Істота фінітного підходу полягає в тім, що він допускає тільки кінцеві комплекси дій над кінцевим числом об'єктів. З'ясування того, які об'єкти і дії над ними варто вважати точно визначеними, якими властивостями і можливостями володіють комбінації елементарних дій, що можна і чого не можна зробити з їх допомогою - усе це стало предметом теорії алгоритмів. Головним внутрішньо математичним додатком теорії алгоритмів з'явилися докази неможливості алгоритмічного рішення деяких математичних проблем. Такі докази нездійсненні без точного поняття алгоритму (для доказу неіснування алгоритму рішення того або іншого класу задач, треба точно знати не існування чого потрібно довести).
2. Інтуїтивне поняття алгоритму.
Людина щодня зустрічається з безліччю задач, що виникають у різних областях діяльності суспільства, наприклад:
а) підготуватися до уроку по математиці;
б) приготувати розчин для прояву фотоплівки;
в) позбутися від зайвої ваги.
Для рішення задач треба знати, що дано, і що варто одержати. Іншими словами, задача являє собою сукупність двох об'єктів: вихідних даних і шуканих результатів. Щоб одержати результати, необхідно знати метод рішення задачі, тобто мати у своєму розпорядженні розпорядження (інструкцію, правило), у якому зазначено, які дії й у якому порядку варто виконати, щоб вирішити задачу (одержати шукані результати). Розпорядження, що визначає порядок виконання дій над даними з метою одержання шуканих результатів, називається алгоритмом.
Алгоритм - це точна кінцева система правил, що визначає зміст і порядок дій виконавця над деякими об'єктами (вихідними і проміжними даними) для одержання (після кінцевого числа кроків) шуканого результату.
Варто мати на увазі, що це - не визначення в математичному змісті слова, але досить докладний опис поняття алгоритму, що розкриває його сутність. Опис може бути іншим. Так, у шкільному підручнику по інформатиці поняття алгоритму дається в наступній формі: "Під алгоритмом розуміють зрозуміле і точне розпорядження виконавцю зробити послідовність дій, спрямованих на рішення поставленої задачі".
Поняття алгоритму є одним з основних понять сучасної математики і є об'єктом дослідження спеціального розділу математики - теорії алгоритмів.
Ще на самих ранніх ступінях розвитку математики в ній стали виникати різні обчислювальні процеси чисто механічного характеру. З їхньою допомогою шукані величини ряду задач обчислювалися послідовно з вихідних величин за визначеними правилами. До числа таких правил відносилися і правила виконання арифметичних операцій над числами.
Протягом сторіч ці правила були дуже складні і не дивно тому, що робити обчислення з великими числами могли тільки люди з вищою освітою. Так, щоб навчитися арифметичного ділення в середні століття було потрібно закінчити університет. Так ще не всякий університет міг навчити цієї премудрості. Потрібно було неодмінно їхати в Італію: тамтешні математики домоглися великого мистецтва в діленні. Якщо нагадати, що в ті часи користувалися непозиційною (римською) системою числення, стане ясно, чому ділення мільйонних чисел був доступний лише бородатим чоловікам, що присвятили цьому усе своє життя.
З уведенням позиційної системи числення усе змінилося. У IX столітті узбецький математик Мухаммед ибн Муса ал-Хорезми ("ал-Хорезми" означає "Хорезмиец") описав правила виконання чотирьох арифметичних дій у десятковій системі числення. Нові правила були значно простіші і зараз ними володіють уже школярі молодших класів. Разюча простота зазначених правил стимулювала їхнє повсюдне поширення. Ці правила були викладені Мухаммедом у книзі по математиці, виданої в 825 році, де, крім того, приводилися численні рецепти рішення різних задач.
По латинських перекладаннях арифметичного трактату ал-Хорезми середньовічна Європа знайомилася з індійською позиційною системою числення і з мистецтвом рахунка в цій системі. При перекладі ім'я автора переробили в Алгоритми. Посилання на рецепти рішень із книги Мухаммеда європейські автори починали зі слів: "Так говорив Алгоритми ...". З часом самі рецепти для рішення математичних задач стали називати алгоритмами.
Спочатку під алгоритмами розуміли тільки правила виконання чотирьох арифметичних дій над десятковими числами. Надалі це поняття стали використовувати для позначення будь-якої послідовності дій, що приводить до рішення поставленої задачі.
Інтуїтивне поняття алгоритму включає в себе декілька загальних рис, які часто визнаються характерними для поняття алгоритму.
1. Алгоритм - це процес послідовної побудови величин, який проходить в дискретному часі таким чином, що в початковий момент задається вихідна скінчена множина величин, а в кожний наступний система величин знаходиться за цілком визначеним законом (програмою) із системи величин, які були в попередній момент часу (дискретність алгоритму).
2. Система величин, що одержується в якийсь відмінний від початкового момент часу, однозначно визначається системою величин, одержаних в попередні моменти часу (детермінованість алгоритму).
3. Закон одержання подальших систем величин із попередніх повинен бути простим і локальним (елементарність кроків алгоритму).
4. Якщо спосіб одержання наступної величини із якої-небудь заданої величини не дає результату, то слід вказати, що вважати результатом алгоритму (направленість алгоритму).
5. Початкова система величин може вибиратись із деякої потенціальної нескінченної множини (масовість алгоритму).
Поняття алгоритму, в деякій мірі визначене пунктами 1) - 5), звичайно, не строге: в формулювання цих пунктів зустрічаються слова спосіб, величина, простий, локальний, точний зміст яких не встановлено. Надалі це нестроге поняття алгоритму буде називатися безпосереднім або інтуїтивним поняттям алгоритму.
Користуючись інтуїтивним поняттям алгоритму, можна описувати процес розв'язку тієї чи іншої задачі, але з його допомогою не можна упевнитися в тому, що описаний процес являє собою алгоритм. Дійсно, одна справа - довести існування алгоритму, а зовсім інша - довести його відсутність. Для цього потрібно знати точно, що таке алгоритм. Розв'язок цієї задачі одержано в середині тридцятих років 20-го століття в двох формах. Перша ґрунтувалась на понятті рекурсивної функції, а друга - на точно окресленому класі процесів. Обидві форми одержали назву алгоритмічні системи.
3. Приклади алгоритмів.
Для роз'яснення інтуїтивного поняття алгоритму розглянемо кілька прикладів.
Як перший приклад розглянемо один із самих древніх і найвідоміших математичних алгоритмів - алгоритм знаходження найбільшого загального дільника двох натуральних чисел. Цей алгоритм ще в III столітті до нашої ери виклав (у геометричній формі) грецький вчений Евклід у теоретичному трактаті по математиці "Начала". Тому він зветься алгоритмом Евкліда. Алгоритм Евкліда обговорюється практично в кожній книзі по програмуванню.
Приклад 1.1. Обчислення найбільшого загального дільника двох натуральних чисел m і n.
Складемо алгоритм рішення цієї задачі в припущенні, що його виконавцем буде деякий обчислювальний пристрій.
Алгоритм Евкліда
1. Помістити в ділянку пам'яті з ім'ям x число m; перейти до виконання пункту 2.
2. Помістити в ділянку пам'яті з ім'ям y число n; перейти до виконання пункту 3.
3. Якщо виконується умова , то перейти до виконання пункту 5, інакше перейти до виконання пункту 4.
4. Помістити в ділянку пам'яті з ім'ям НОД значення з блоку пам'яті x; перейти до виконання пункту 8.
5. Якщо виконується умова x > y, то перейти до виконання пункту 6, інакше перейти до виконання пункту 7;
6. Помістити в ділянку пам'яті з ім'ям x значення вираження x - y; перейти до виконання пункту 3.
7. Помістити в ділянку пам'яті з ім'ям y значення вираження y - x; перейти до виконання пункту 3.
8. Закінчити роботу.
Уважний розгляд алгоритму Евкліда показує, що запис алгоритму розпадається на окремі команди. Кожна команда позначена номером і являє собою указівку виконавцю виконати деяку закінчену дію. Виконання алгоритму починається з команди, що має номер 1. Далі команди виконуються відповідно до вказівок, що супроводжують кожну команду алгоритму.
Для зручності посилань, алгоритм звичайно забезпечується назвою. У випадку, коли для алгоритму не вказується спеціальна назва, його назвою звичайно вважають весь текст задачі, для рішення якої цей алгоритм призначений.
Існує правило, відповідно до якого, при відсутності спеціальної вказівки наступний за даною командою повинна виконуватися команда, номер якої на одиницю більше даної. Така послідовність виконання команд називається природною. За вказівкою "скінчити роботу" виконання алгоритму припиняється.
Приклад 1.2. Множення натуральних чисел стовпчиком.
1. Записати множене.
2. Підписати множник під множеним так, щоб розряди множника знаходилися під відповідними розрядами множеного.
3. Провести чорту під множником (під нею будуть записуватися приватні суми).
4. Узяти чергову цифру множника, починаючи з одиниць.
5. Якщо чергова цифра множника дорівнює нулю, пропустити її і перейти до пункту 7.
6. Якщо чергова цифра не дорівнює нулю, помножити на неї множене і добуток як чергову приватну суму, підписати під рисою або під попередньою приватною сумою так, щоб одиниці добутку знаходилися б під черговою цифрою множника.
7. Якщо чергова цифра не була останньої, перейти до пункту 4.
8. Якщо чергова цифра виявилася останньої, скласти приватні суми стовпчиком і загальною сумою взяти як шуканий добуток.
Приклад 1.3. Інструкція з готування проявника. Уміст великого пакета розчинити в 300 мол. води при температурі I8-20° C; потім додати вміст малого пакета. Обсяг розчину довести до 500 мол. Розчин профільтрувати.
У цьому прикладі команди не пронумеровані. Усі команди записані послідовно, у виді суцільного тексту. Друг від друга команди розділені або крапкою, або крапкою з коми. При такому оформленні алгоритму виконавець виконує команди в порядку їхнього природного проходження в тексті.
Така форма запису алгоритму часто використовується у всякого роду інструкціях, правилах, рецептах і т.п. Вона гарна у випадку, коли алгоритм невеликої і коли для опису алгоритму приділяється мало місця. Недоліком такого оформлення є його мала наочність .