Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

Інформатика

Необчислювальні алгоритмы

Навчальний посібник для 9-10 класів із поглибленим вивченням інформатики

Схвалено

Міністерством освіти і науки

України

київ

«ГЕНЕЗА» 2007

ББК 32.81я721 К21

Схвалено до використапня в навчальновиховному процесі (лист МОН України №1/12-1313 від 04.04.2006 p.)

Рецензенти: Тимофієва Є. М. - канд. фіз.-мат. наук, доцент Чернівецького

національного університету

імені Юрія Федьковича; Деркач Н. Й. - викладач інформатики Чернівецького

міського ліцею № 1 математичного

та економічного профілів, учитель-методист

Караванова Т. П.

К21 Інформатика: Методи побудови алгоритмів та їх аналіз. Необчисл. алгоритми: Навч. посіб. для 9-10 кл. із поглибл. вивч. інформатики. - К.: Генеза, 2007. - 216 с: іл. -Бібліогр.:с. 212. ISBN 966-504-538-5

Матеріал навчального посібника відповідає «Програмі для спеціалізованих шкіл, гімназій, ліцеїв. Інформатика і програ-мування. 8-11 класи», рекомендовано! Міністерством освіти і науки України.

У посібнику розглядаються питания методики загальної по­будови алгоритмів, структур даних, пошукових алгорнтмів та сортування. До всіх тем наведено запитання для самоконтролю та завдання, виконання яких дасть змогу закріпити новий мате-ріал.

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

ББК32.81я721

ЄКараванова Т. П., 2006 ! Видавництво «Генеза», ISBN 966-504-538-5 художнє оформления, 2006

Від автора

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

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

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

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

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

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

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

3

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

Хочеться висловити особливу вдячність колегам і друзям, які своїми доброзичливими і водночас високопрофесійними по-радами значно покращили зміст посібника: Хижі Олександру Леонідовичу, Ривкінду Иосифу Яковичу, Войцеховському Ми-кол! Олексійовичу, Мельнику Валентину Івановичу, Голуб-ничій Наталії Вікторівні.

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

Тетяна Караванова

Розділ I

МЕТОДИКА РОЗРОБКИ АЛГОРИТМА, ОЦІНКА IX ЕФЕКТИВНОСТІ

Створення алгоритму

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

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

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

Виникає запитання: а як дізнатися, правильний чи непра­вильний алгоритм ми створили? Як перевірити, зупиниться він чи ні? Можна проаналізувати алгоритм, виконуючи по кроках записані у ньому дії. Але це реально лише для невели­ких вхідних даних. Однак не завжди така перевірка дасть остаточну відповідь. Інший вихід полягає в тому, щоб записати алгоритм обраною мовою програмування і виконати програму на комп'ютері.

Усі алгоритми поділяються на два великі класи. Це алго­ритми з повторениями та рекурсивні алгоритми.

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

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

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

• визначення моделі задачі, що розв'язується;

• запис алгоритму мовою програмування;

• тестування програми на комп'ютері;

• отримання розв'язку поставленої задачі шляхом виконан­ня завершеної програми.

Математична модель, вибір структури даних

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

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

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

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

Є і складніші структури даних. Про них ітиметься в пособ­нику далі. Знания всіх можливих структур даних значно роз-ширить коло задач, які ви зможете розв'язувати.

Пошук оптимального алгоритму розв'язування

Який алгоритм вважати оптимальним? Якими є критерії оптимальності алгоритму? Як визначити, чи даний алгоритм є оптимальним? Чи варто взагалі говорити про оптимальність алгоритму, який розробляється?

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

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

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

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

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

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

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

7

Мал. 1

Ця схема представляв собою бінарне (двійкове) дерево, у вуз-лах якого розміщені пари елементів, що порівнюються на кожному кроці. Pyx гілками дерева від його кореня (найвищої вершини) визначає конкретну гілку, яка у свою чергу є одним із варіантів отримання розв'язку задачі. Ліва гілка кожної вершини відповідає виконанню зазначеної у вершині умови, а права - ні. Кожна гілка завершується вершиною, де вказаний порядок розміщення заданих елементів, що задовольняє розв'язок задачі. Кількість таких гілок визначає кількість можливих варіантів отримання розв'язків задачі. Максимальна довжина гілки дорівнює кількості ребер, якими треба пройти від кореня дерева до останньої вершини у цій гілці. Таке дерево називається деревом розв'язків. За допомогою дерева розв'язків можна визначити кількість операцій, необхідних для роз-в'язування поставленої задачі.

Дерево розв'язків можна побудувати для кожної задачі. На малюнку 1 ми бачимо, що в даній задачі є 6 можливих варіантів отримання результату. Також можна помітити, що не всі гілки дерева однакової довжини. Серед них є найкоротші, які дають розв'язок задачі при певних початкових даних. Інші гілки є довшими і також дають правильну відповідь при іншій послідовності початкових даних. Для нашого прикладу найменша гілка мае довжину 2, а найбільша - 3. Яке з цих значень обрати за оптимальну кількість операцій, необхідних для отри­мання правильного розв'язку нашої задачі?

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

Давайте підійдемо до визначення оптимально! кількості виконуваних алгоритмом дій не лише за допомогою аналізу дерева розв'язків, а й з точки зору математичних міркувань.

На кінцях кожної з шести гілок розміщені всі можливі варіанти розташування заданих трьох вхідних елементів. Вияв-ляється, що можлива кількість переставлень для N елементів обраховується за формулою k - N\. Це можна пояснити так. Треба розмістити N різних елементів на N місцях. Для першого елемента є N варіантів розміщення, для другого залишається уже (N - 1) місце, для третьего - (N - 2) і т. д. Для останнього N-ro елемента залишиться одне місце. Для одержання загаль-ної кількості варіантів необхідно всі ці числа перемножити: N- (N - 1) • (N - 2) • ... • 1 = iVI. Це пояснюється тим, що, наприклад, для всіх варіантів розміщення першого елемента необхідно перебрати всі варіанти розміщення другого, а для всіх цих варіантів - розміщення третьего і т. д. Для нашої конкретно!' задачі одержимо 3! = 6.

А скільки рівнів мае бути у дереві розв'язку? Будемо нуме-рувати рівні, починаючи з 0. 3 малюнка 1 видно, що на кож­ному рівні кількість вершин подвоюється: на нульовому рівні -1 вершина, на першому — 2, на другому - 4, на третьому - 4. За логікою на третьому рівні мало б бути 8 вершин, але для нашої задачі їх усього 4, оскільки не всі вершини попереднього рівня мають своїх нащадків. Напрошується висновок, що на К-му рівні кількість вершин дорівнює 2^К~¹. А для всієї кількості елементів N треба знайти таке найменше L, для якого вико-нуеться умова N\ < 2^L~^l.

У математиці існує функція, яка визначає степінь у вказано-го числа х. Називається така функція логарифмічною і позна-чається log. Якщо ввести позначення k = х^у, то можна сказати, що, знаючи число k, за допомогою логарифма можна дізнатися, до якого степеня треба піднести число х, щоб отримати k. Ма-тематично це записується так: у = \og_xk.

Використовуючи нові терміни, перейдемо до нашої задачі. Оскільки з нерівності N\ < 2^L'^X треба знайти L, то прологариф-муємо обидві и частини за основою 2. Таким чином, у правій частині нерівності ми отримаємо (L - 1), а у лівій - вираз log₂M:

log^KL-l.

Як спростити вираз log₂iV!? Нагадаємо його тлумачення: це степінь, до якого треба піднести 2, щоб отримати значения N1. Оскільки Nl'N- (N-l) ■ (N-2) ■... ■ 2 • 1, то нас цікавитиме сте-пінь, до якого треба піднести окремо числа N, (N-l), (N-2),..., 2, 1. Тому можна записати:

9

log₂M = log₂(N ■ (N-l) ■ (N-2) ■ ... • 1) =

N

«= log^ + log₂(W - 1) + \og₂(N - 2) + ... + log₂l = ]>>g₂ i.

1=1 Скориставшись математичними формулами сумування, які не будемо тлумачити у рамках даного посібника, запишемо:

£log₂l~N • log^ - 1,5 ~N • log₂N.

i=l

Отриманий запис N ■ log₂N слід розуміти так: оптимальна кількість операцій, необхідних для упорядкування заданої послідовності з N елементів, не повинна перевищувати добутку такого степеня числа 2, що в результаті дає N, та самого числа N. Зрозуміло, що log₂N значно менше за саме число JV, а тому N • \og₂N значно менше за N².