Лекція 2. Алгоритми і обчислення

2.1. Алгоритми

Потреби суспільства в узагальненні багатьох підходів до роз­в’язання різноманітних задач зумовили створення теорії алгоритмів. Бурхливий розвиток науки і техніки в останні століття, спроби філософів найточніше описати різноманітні аспекти людського буття дали світові науку наук – логіку розвитку, яка породжувала задачі, що стимулювали появу нових ідей і методів їх розв’язання. Складність і вели­кий об’єм обчислень зумовили створення спеціалізованих обчислюваль­них пристроїв. Вони прой­шли складний шлях розвитку. Серед них можна виділити один із найпотуж­ніших класів – це електронно-обчислювальні машини (ЕОМ). Проникнення ЕОМ у різні сфери практичної діяльності людей значно вплинуло на еволюцію теорії алгоритмів, на вибір нових напрямів її застосування. Вона перетворилась у певну школу мислення й аналізу для широкого кола програмістів, дала основу мові алгоритмів, яка об’єднує різні напрями досліджень у програмуванні, полегшує розповсюдження ідей. Теорія алгоритмів є важливою частиною прикладної математики, а по­няття алгоритму та форм його задання посідає чільне місце в теорії алгоритмів.

Як відомо, слово алгоритм прийшло з Персії, запропонував його автор книги з математики Abu Jafar Mohammed ibn Musa al Khowarizmi. Він визначав його як деякий спеціальний метод вирішення поставленої проблеми.

Поняття алгоритму належить до найскладніших концепцій природознавства. Воно пройшло складний історичний шлях розвитку, починаючи з інтуїтивного розуміння і стихійного застосування на перших кроках розвитку людського суспільства та закінчуючи усвідомленням закономір­ностей природних явищ, застосуванням у сучасних ЕОМ. Багато авторів визначають розвиток науки як безперервний процес уточнення алго­рит­мів і побудови відповідних моделей.

Умовно можна виділити три основні етапи розвитку теорії алго­ритмів.

На першому етапі відбувалося накопичення фактів людиною, що засвоювала знання про природу і стихійно формувала та закріплювала власні алгоритми поведінки.

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

Третій період бере відлік з початку ХХ ст. Було побудовано формаль­ну класичну теорію алгоритмів, яка уточнювала можливості тео­ретич­ного обчислення для практичного застосування в кібернетиці й про­гра­му­ван­ні. Теорію алгоритмів можна поділити на класичну і прикладну. У кла­сичній теорії алгоритмів існує безліч формальностей для опису алгоритмів. Серед них можна виділити найзначніші: арифметичне чис­лення предикатів Гьоделя, машини Поста і Тьюринга, автомати Маркова, схеми Янова, блок-схеми.

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

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

Приклад і властивості алгоритму

Задача 2.1.

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

Алгоритм 2.1:

П1: Покласти ціле число рівним двом і перейти на крок П2.

П2: Якщо ділиться без остачі на , то завершити роботу алгоритма, видавши в якості результату ; інакше перейти на крок П3.

П3: Збільшити значення на одиницю і перейти на крок П2.

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

 

		= 2
П1:	П1:	П1:
П2:	П2:	П2:
П3:
П2:

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

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

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

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

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

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

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

Кажуть, що на ЕОМ практично неможливо працювати з дійсними числами. Більш того, навіть із справжніми цілими числами на комп'ютері працюють не так вже й часто. Зазвичай замість множин цілих і дійсних чисел доводиться працювати з їх замінниками і відповідно. Ці машинні аналоги часто цілком дозволяють забути

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

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

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

Розглянемо такий приклад. Нехай потрібно дослідити розв’язання повного квадратного рівняння

Алгоритм дослідження можна описати українською мовою за допомогою такої послідовності кроків:

0. Ввести значення a, b, c.

1. Обчислити дискримінант .

2. Якщо , тоді надрукувати повідомлення «рівняння має один роз­в’я­зок: ».

В іншому разі, якщо тоді надрукувати повідомлення «рівняння має два корені: і ».

Інакше (якщо ) надрукувати повідомлення «рівняння не має дійсних коренів».

3. Кінець алгоритму.

Якщо уважно подивитися на таке задання алгоритму, то можна виділити основні недоліки опису: громіздкість та неоднозначність трактувань інструк­цій. Для їх усунення використовують спеціалізовані формалізми: блок-схеми, мови програмування тощо.

Наш алгоритм можна описати блок-схемою, яку зображено на рис. 2.1.

Блок-схема є зв’язним орієнтованим графом, вузли якого можуть бути блоками чотирьох типів: блок ініціалізації (ввести значення a, b, c), функціональні блоки (обчислити , вивести…), предикатні блоки ( , ) і блок закінчення обробки інформації (кінець). Кожен блок належить певному шляху з початкового блоку в кінцевий. Передачу керування між блоками визначають напрямленими стрілками. Предикатний блок використовують для розгалуження керу­вання (умовної передачі керування). Він функціонує так: якщо предикат, що стоїть в середині ромба, справджується (набуває значення «істина», позначається «і»), то керування передається одному блоку, якщо ж пре­ди­кат не справджується (набуває значення «хибність», позначається «х»), тоді керування передається іншо­му блоку.

Для дослідження цієї задачі на ЕОМ слід описати алгоритм дослі­дження за допомогою якоїсь мови програмування. Таке задання нази­вають програмою.

Структура програми більшості мов програмування типова і має загаль­ний характер. Розглянемо запис програми 1.1 дослідження розв’язання пов­ного квадратного рівняння в мові програмування Паскаль.

program EХ1_1;

var A, B, C, D: real;

begin

read(A, B, C);

D := B*B – 4*A*C;

if D = 0 then

writeln(‘Рівняння має один розв’язок x = ‘, –B/(2*A))

else

if D > 0 then

writeln(‘Рівняння має два корені x₁ = ‘, (–B + D)/(2*A),

‘ i x₂ = ‘, (–B – D)/(2*A))

else

writeln(‘Рівняння не має дійсних коренів’);

end.

Програма 1.1. Дослідження розв’язку повного квадратного рівняння

Знання англійської мови дає змогу зрозуміти в загаль­них рисах призначення кожної інструкції (відділяється крапкою з комою) у програмі.

Програми Паскаль, як і програми більшості мов програмування, скла­даються з таких основних частин: заголовка (program), блока опису кон­­стант (const), блока конструювання типів (type), блока опису змінних (var), блока опису процедур та функцій і блока виконань (begin–end).

Заголовок програми, в нашому прикладі іменується EХ1_1, викори­стовується для ідентифікації програми і може містити опис пристроїв введення-виведення інформації.

Блок опису змінних використовують для визначення розмірів ділянок пам’яті, де процесор оброблятиме інформацію для отримання кінцевого результату. У цьому випадку змінні A, B, C, D виступають у ролі засобів доступу до ділянок пам’яті (імен), а опис real визначає розмір пам’я­ті, що виділяється для змінної зазначеного типу у разі отримання даної програми на виконання процесором.

Блок опису констант використовують для визначення даних, що не змінюють своїх значень за час виконання програми.

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

Блок виконань містить інструкції, що описують послідовність дій, які процесор здійснюватиме над пам’яттю для отримання кінцевого результату алгоритму.

Спробуйте описати алгоритм дослідження квадратного рівняння за допомогою блок-схеми, а потім переведіть блок-схему в програму на Паскалі.

Традиційно програми можна поділити на два класи: прикладні та системні. Прикладні програми використовують для розв’язання конкретних прикладних задач. Системні програми полегшують роботу користувача на комп’ютері. До системних програм належить і набір програм, який дістав назву операційна система (ОС).

ОС забезпечує взаємодію між користувачем і комп’ютером, а також між програмою і різними компонентами апаратури комп’ютера. Загальне керування комп’ютером здійснюють за допомогою мови директив. У кожній ОС є набір службових програм (утиліт), які використовують для полегшення роботи у разі написання програм. Одна з типових конфігурацій ОС для комп’ютера має такі складові компоненти: файлову систему; драйвери зов­нішніх пристроїв; процесор командної мови.