Введення в алгоритмiзацiю

ВВЕДЕННЯ В АЛГОРИТМЗАЦЮ Алгоритми 1. Загальн вдомост. Вимоги до алгоритмв У 820 р. нашо ори в Бухар був написаний пдручник Аль-Джабр Ва-аль-Мукабала Наука виключення скорочення, у якому були представлен правила виконання чотирьох арифметичних дй над числами в десятковй систем числення. Автором пдручника був арабський математик Мухаммед бен

Муса аль-Хорезм. Вд слв альджебр у назв пдручника пшло слово алгебра, а пд мен Аль-Хорезм слово алгоризм, що пзнше перейшло в алгоритм що розумться як сукупнсть правил. Найдавншому записаному алгоритму вже 3800 рокв. Близько 1800р. до п. е. житель Вавилона зобразив па глинянй табличц процедуру розвязування задач, в якй було потрбно знайти, скльки часу пде на подвоння наявно клькост зерна при рчному прирост в 20.

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

Незважаючи на простоту гнучксть такого представлення, воно нечтке й обмежене. Кожний з вас ум завязувати шнурки. Спробуйте без картинок демонстрацй описати алгоритм завязування шнуркв. Великий роздл нформатики, що називаться алгоритмзаця, вивча алгоритми, хн властивост, методи прийоми побудови алгоритмв. У будь-якого алгоритма ма бути виконавець. Оскльки мова йде про розвязування задач за допомогою компютера, то виконавцем компютер.

Можна сказати, що алгоритм це однозначна скнченна послдовнсть точно визначених крокв або дй. що забезпечу розвязання задач, й для виконання яко потрбн скнченний обсяг оперативно памят скнченний час. Розберемося, як вимоги предявля таке визначення до алгоритмв. Масовсть. Алгоритм ма бути придатним для використання у розвязанн цлого класу однотипних задач. Скнченнсть. Алгоритм ма складатися з скнченного числа крокв, кожний з яких вимага для свого виконання

скнченного промжку часу. Результативнсть. Псля закнчення виконання алгоритму мамо отримати певний результат. Однозначнсть. Виконання кожного кроку алгоритму вс послдовност крокв повинне здйснюватися у диний спосб. Це означа, що скльки б разв алгоритм не застосовувався до тих самих вихдних даних, результати виконання кожного кроку вс послдовност в цлому будуть т сам. нод цю вимогу називають визначенстю або детермнованстю алгоритму вд англ. о determine визначати. Правильнсть.

При застосуванн алгоритму до припустимих вихдних даних повинний бути отриманий необхдний результат. Доказ правильност алгоритму один з найважчих етапв його створення. Найрозповсюдженша процедура переврки правильност алгоритму як програми це обрунтування правомрност переврка правильност виконання кожного з крокв на набор теств, пдбраних так, щоб охопити вс припустим вхдн вс припустим вихдн дан. Ефективнсть. Алгоритм повинен забезпечувати розвязання задач за мнмальний

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

конкретна операця виконуться за скнченний заздалегдь вдомий час. Розглянемо просту задачу сну n чисел, наприклад результатв вимрв температури або нших експериментв. Потрбне виконати аналз даних знайти мнмальне число, максимальне, вдсортувати х, тобто розташувати в порядку зростання чи убування. Коли таких чисел небагато, цю задачу легко розв язати вручну. Але коли число n велике сотн, тисяч мльйони, роботу краще доручити компютеру.

При цьому слд вибрати метод скласти алгоритм виконання дй. Навть за приблизними пдрахунками зрозумло, що для знайдення мнмального числа потрбно переглянути всю послдовнсть тобто зробити n порвнянь. Якщо ж потрбно виконати сортування, то операцй знадобиться ще бльше. Виходить, чим бльше n, тим бльше часу буде потрбно на роботу, причому часовi витрати можуть рости набагато швидше, нж саме число n. снують методи , вдповдно, алгоритми, що вимагають для розвязування

задач сортування часу, пропорцйного n . Це означа, що при збльшити числa n вхдних, елементв час витрачений на хн сортування, росте прямо пропор-цйно квадрату цього числа. швидш алгоритми. З ншого боку, снують задач, у яких для знайдення потрбного результату треба виконати повну низку всх можливих розвязань. Наприклад, вдома задача комвояжера агента в справах продажу товарв агент ма вдвдати n мст, затративши на дорогу мнмальну кльксть грошей вартсть перезду з мста до мста вдомою.

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

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

за допомогою алгоритмв т чи ншо складност, багатьма ншими теоретичними питаннями займаться спецальна обдасть нформатики Теоря алгоритмв. 1.2. Базов структури Для опису логчно обумовленого ходу виконання дй при складанн будь-якого алгоритму використовуються т сам складен блоки, що звуться базовими структурами. х усього три проходження, розгалуження, цикл. Це три типи цеглинок, з яких можна скласти будь-який алгоритм.

Для графчного представлення базових структур використовуються спецальн позначення. Прямокутником позначаться дя, яку треба виконати. Mал. 1 Дю тут може бути як одна окрема дя наприклад, скласти два числа чи накреслити лню, так послдовнсть логчно обднаних у блок дй наприклад, виконати розрахунки за заданими формулами або зробити малюнок. Ромбом позначаться операця переврки значення логчного виразу.

У логчних виразах можуть використовуватися логчн операц НЕ АБО. Логчний вираз може приймати одне з двох значень СТИНА чи НЕПРАВДА. СТИНА НЕПРАВДА Mал. 2 Переврка значення логчного виразу звичайно зводиться до переврки виконання чи невиконання певних умов. Перейдемо до опису базових структур. 1. Проходження означа, що д повинн бути виконан послдовно одна за одною.

Mал. 3 Наприклад, будь-який алгоритм може бути представлений як послдовнсть трьох дй Вхiд Вихiд Mал. 4 2. Розгалуження, яке також називаться ЯКЩО-ТО-НАКШЕ, означа вибр одного з двох варантв залежно вд значення певного логчного виразу. СТИНА Вхiд Вихiд НЕПРАВДА Mал. 5 Наприклад, алгоритм обчислення значення функц 1, якщо x 0 Y x 0, якщо x 0 можна представити у такому вигляд СТИНА

НЕПРАВДА Mал. 6 Може виявитися, що при одному з значень логчного виразу не потрбно виконувати жодних дй. У цьому випадку структура розгалуження називаться ЯКЩО-ТО може бути представлена у такому вигляд СТИНА НЕПРАВДА Mал. 7 Така структура використовуться в тих випадках, коли необхднсть виконання дй залежить вд певних умов. Наприклад, виконувати сортування послдовност з n елементв ма сенс лише тод, коли вона

ма бльше одного елемента СТИНА НЕПРАВДА Mал. 8 3. Цикл означа повторне виконання т само д або блока дй, що звуться тлом циклу, доти, поки певний логчний вираз залишаться стинним. СТИНА Умова продовження Тiло цикла закiнчення циклу НЕПРАВДА Mал. 9 Такий цикл називаться ЦИКЛ-ПОКИ, або цикл з передумовою умова перевряться перед виконанням тла циклу. Спочатку на першому кроц циклу перевряться значення логчного виразу.

Якщо воно е стинним, то виконуться тло циклу. Потм на другому кроц знову робиться переврка значення логчного виразу , якщо воно дос стинним, знову виконуться тло циклу т. д. Цикл завершуться, коли значення логчного виразу ста помилковим. Можлив ситуац, коли тло циклу не виконаться жодного разу. Це вдбуваться, якщо на першому кроц циклу значення логчного виразу помилковим.

Наприклад, для пдрахунку суми n чисел а1, а2 аn п 2 слд користуватися структурою циклу. Позначи-мо через S шукану суму, а через номер числа в послдовност. До початку циклу S0 ще нчого не пдсумовували 1 почнемо пдсумовувати з першого члена. Вхiд S0,i1 СТИНА Тiло циклу НЕПРАВДА Mал. 10 Запис 1 означа, що значення змнно на наступному кроц лворуч вд знака рвност дорвню значенню на попередньому кроц праворуч вд знака рвност плюс один.

Це перехд до наступного числа в послдовност. Аналогчно розумться запис S S аi значення S на наступному кроц циклу дорвню значенню S на попередньому кроц плюс -те число послдовност. Це додавання до суми чергового доданка. На першому кроц циклу умова стинною, значить S 0 а1 а1 ста рвним 2. На другому кроц циклу умова ще стинною, до старого значення

S, що дорвню а1, додаться а2 ста дорвнюваним 3, тобто на другому кроц циклу S а1 а2 сума перших двох елементв 3. На третьому кроц циклу умова все ще стинна тому що n 2, S S a3 а1 a2 a3 сума перших трьох елементв послдовност та ста рвним 4. Кроки будуть повторюватися рвно n раз. Псля завершення циклу значення буде дорвнювати n 1, а в S буде знаходитися сума всх елементв S a1 а2 аn . Звернть увагу, що на кожному кроц циклу змнн та

S мають той самий змст номер першого, ще не пройденого елемента, a S це сума всх уже пройдених елементв. Так величини називаються нварантами циклу вд англ. nvariant незмнний хнй змст залишаться незмнним на будь-якому кроц циклу. Часто в цикл використовуться спецальна змнна лчильник циклу. Вона раху кроки циклу. До початку циклу значення дорвню нулю.

На кожному кроц циклу значення лчильника дорвню номеру цього кроку. Псля закнчення циклу лчильник показу загальну кльксть виконаних крокв. Уданому випадку змнну , а точнше 1, можна розглядати як лчильник циклу. Хоча ЦИКЛ-ПОКИ повнстю забезпечу опис циклчних процесв, нод бува зручно користуватися ншим типом циклу, що ма назву ЦИКЛ-ДО. Його схема ма вигляд НЕПРАВДА

СТИНА Тiло циклу Mал. 11 Цей цикл ма дв вдмнност вд циклу типу ЦИКЛ-ПОКИ значення логчного виразу перевряться псля виконання тла циклу. Цс означа, що тло ЦИКЛу-ДО буде виконано принаймн один раз ЦИКЛ-ДО повторються доти, поки значення логчного виразу помилковим, завершуться, коли воно ста стинним. Друга вдмннсть несуттва, тому що за допомогою операц заперечення

НЕПРАВДУ СТИНУ можна помняти мсцями. Приклад пдсумовування п чисел за допомогою ЦИКЛу-ДО НЕПРАВДА Вхiд СТИНА S0, I1 Тiло циклу Mал. 12 Циклчн процеси часто називають терацйними вд англ. to iterate повторювати, а кожен крок циклу терацю. Описан вище базов структури можуть комбнуватися одна з другою для опису ходу виконання дй у будь-якому алгоритм. Усякий прямокутник на кожнй з схем може бути замнений будь-якою з базових структур або х комбнацю.

Будь-який алгоритм може бути побудований з трьох базових структур проходження, розгалуження, циклу. 1.3. Основн способи запису алгоритмв Розроблений алгоритм повинний бути представлений у вигляд, зрозумлому будь-якй людин, що використову цей алгоритм. снують рзн способи запису алгоритмв. Часто запис алгоритму словесним описом кожного кроку алгоритму з зазначенням порядку крокв. Зручним способом запису алгоритму блок-схема. З допомогою алгоритм представляться графчно.

Для складання блок-схеми використовуються схеми базових структур, наведен на мал. З, 5, 7, 9, 11. Блок-схема робить запис алгоритму бльш наочним. Одним з основних способв запису алгоритму програма. Для запису алгоритму у вигляд програми використовуються спецальн мови алгоритмчн. Запишемо алгоритм виконання домашнього завдання з нформатики.

Припустимо, що задано розробити записати алгоритми для розвязування трьох рзних задач. Блок-схема, зображена на мал. 13, допоможе справитися з цим трудомстким завданням. Змнна познача номер поточно задач 1, 2, 3. Ще один приклад. Повернемося до задач аналзу даних деякого експерименту п. 1.1 знайдемо серед них найбльше. Припустимо для простоти, що вс дан цл числа.

Таким чином, необхдно виршити задачу знайти максимальне з даних цлих чисел. Виконамо поетапне розвязування задач вдповдно до загально схеми мал. 14. Постановка задач. Дано п натуральне число а1 а2 a3 an цл числа. Знайти максимальне з чисел а1, а2 а3 an. Модель. Як модель тут пдходить такий текстовий опис цл числа мають таку властивсть, що будь-як два з них або рвн, або одне з них бльше за нше.

Ця властивсть дозволя вибрати максимальне з двох чисел якщо числа рвн, то як максимальне вибираться одне з них. Для ршення дано задач можна скористатися готовим ПЗ, наприклад електронною таблицею Ехcel. Для цього необхдно запустити Ехсеl або, якщо Ехсеl уже працю, але в нй розвязувалася нша задача, то зберегти результати створити нову книгу увести вихдн числа а1, а2 а3 an n задано в умов задач.

Будемо використовувати для збереження цих чисел блок комрок, наприклад, А1 Аn увести в одну з комрок, наприклад В1, формулу МАХА1 Аn. Значення комрки В1 необхдний у задач результат вивести результат зберегти у файл па диску або вивести на Друк вийти з Ехсеl. Перелчен д можна записати у вигляд алгоритму, зображеному на мал. 15, 16. З попереднього матералу вже вдом способи виконання всх перелчених дй.

Тому в наведеному алгоритм описуться змст кожно д, а не спосб виконання. Багато з описаних дй не одню, а цлою послдовнстю дй вимагають подальшо деталзац. Використовуючи вдом способи виконання зазначених дй, зробть самостйно наступну деталзацю алгоритму. ЯКЩО Ехсеl не запущена ТО запустити Ехсеl НАКШЕ ЯКЩО на екран книга з даними ТО зберегти поточну книгу створити нову книгу припустити значення , що дорвню 1

ПОКИ n зробити активною комрку А та ввести А - а збльшити значення 1 на 1 зробити активною комрку В1, та ввести ФОРМУЛУ МАХА1Аn вивести результат вийти з Ехсеl Mал. 15 Тут наведен два способи запису того самого алгоритму. Звернть увагу на вдступи в текстовому варант алгоритму. Вони обовязков, тому що роблять алгоритми наочними зрозумлими спробуйте записати той же алгоритм без

вдступв, а через деякий час спробуйте прочитати зрозумти його. Нi Так Нi Так Так Нi Mал. 13 Загальна схема процесу розв язування задачi за допомогою комп ютера Mал. 14 Так Нi Нi Так Так Нi Mал. 16 Якщо для розвязування поставлено задач не використовувати готове ПЗ, то вдповдно до загально схеми мал. 14 наступний за побудовою модел етап вибр методу. Для знайдення максимального елемента послдовност сну багато методв.

Наприклад, можна використовувати такий метод. Задана послдовнсть розбиваться на пари. У кожнй з цих пар знаходиться максимальне число. Отримана послдовнсть максимальних чисел знову розбиваться на пари знаходяться максимальн числа в кожнй з цих пар. Описан д продовжуються доти, поки в послдовност максимальних чисел, отриманй на попередньому кроц, залишиться лише два числа. Максимальне з них необхдним у задач результатом.

Наприклад, потрбно знайти максимальне з чисел 28, 3, 111, -2, 48, 33, -5, 128. Описаний метод розвязування ц задач можна зобразити у вигляд схеми рис. 17. Ще один метод поляга ось у чому. Позначимо необхдний результат мям тах. Спочатку значення тах дорвню першому числу a1. Потм значення тах порвнються з a2 , якщо число а2 бльше, нж тах, то значення тах вважаться таким, що дорвню а2, т. д.

Поточне значення тах послдовно порвнються з кожним ще не переглянутим членом послдовност та змнються лише тод, коли який-небудь з членв бльшим за поточне значення тах. Тод тих вважаться таким, що дорвню цьому члену. У приклад, що люстру попереднй метод, значення мах буде змнюватися так тах 28 тах 111 тах 128. Останн значення тах необхдним результатом. Mал. 17 Перший метод менш ефективний, нж другий вн вимага бльшо клькост порвнянь додаткових обсягв

оперативно памят для збереження промжних результатв. Запишемо алгоритм розвязування задач другим методом у вигляд блок-схеми мал. 18. Позначимо через i номер числа в послдовност. Проходження Так Нi Цикл-ПОКИ Так Нi Mал. 18 Звернть увагу на кожному кроц циклу значення тах дорвню максимальному з уже переглянутих членв послдовност, а мстить номер першого ще не переглянутого члена.

Псля завершення циклу, коли будуть переглянут вс елементи послдовност, тах буде мстити необхдний результат. Змнну можна розглядати як лчильник циклу на кожному кроц значення, зменшене на два, показу, скльки крокв уже зроблено, тобто скльки разв виконалося тло циклу. Оцнимо складнсть цього алгоритму. Основна операця тут порвняння. Значення тах порвнються з елементами а1, а2 an. Значить, виконуться п.

1 порвняння, тобто складнсть цього алгоритму лнйна функця вд п. Оскльки перед циклом значення дорвню 2. а не 0.