Харківський національний університет будівництва та архітектури

 

 

Петрова О.О, Солодовник Г.В.

АЛГОРИТМИ: АНАЛІЗ ТА ПОБУДОВА

Навчально-методичний посібник

 

Харків 2015

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

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

БУДІВНИЦТВА ТА АРХІТЕКТУРИ

 

 

Петрова О.О, Солодовник Г.В.

АЛГОРИТМИ: АНАЛІЗ ТА ПОБУДОВА

Навчально-методичний посібник

 

Рекомендовано науково-методичною радою університету

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

 

Харків 2015

ББК 73

П – 30

УДК 004.383.1

 

Рецензенти:

Л.В. Курпа, доктор техн. наук, професор, завідуюча кафедрою прикладної математики Національного технічного університету «Харківський політехнічний університет» (НТУ «ХПІ»)

Н.Д. Сізова, доктор фізико-математичних наук, професор кафедри економічної кібернетики та інформаційних технологій Харківського національного університету будівництва та архітектури (ХНУБА).

 

Рекомендовано кафедрою економічної кібернетики

та інформаційних технологій, протокол № 6 від 25.12.2015

Затверджено науково-методичною радою університету,

протокол № 5 від 26.02.2015

 

 

П – 30

О.О. Петрова, Г.В. Солодовник Алгоритми: аналіз та побудова: Навчально-методичний посібник. – Х.: ХНУБА, 2015 р. –90с.

 

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

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

 

Іл.: 23; табл.: 4; бібліогр.: 8 назв.

 

 

©	О.О. Петрова, Г.В. Солодовник, 2015

 

ВСТУП

 

Під час розв’язання науково-технічних задач велика увага приділяється розробці алгоритму їх розв’язання.

Не зважаючи на зусилля дослідників, єдиного вичерпного і чіткого визначення поняття алгоритму не існує.

Варіанти вербального визначення алгоритму, що вже існують, належать російським вченим А.М. Колмогорову і А.А. Маркову [1,2]:

Визначення 1 (за Колмогоровим): Алгоритм – це будь-яка система обчислень, що виконується за чітко визначеними правилами, яка після певного числа кроків явно призводить до розв’язання поставленої задачі.

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

Зазначимо, що різні визначення алгоритму, в явній або неявній формах, визначають наступні вимоги [3]:

1) алгоритм повинен містити скінченну кількість приписів, що виконуються елементарно, тобто задовольняти вимогам скінченності запису;

2) алгоритм повинен виконувати скінченну кількість кроків під час розв’язання задачі, тобто задовольняти вимогам скінченності дій;

3) алгоритм повинен бути єдиним для всіх допустимих первинних даних, тобто задовольняти вимогам універсальності;

4) алгоритм повинен призводити до отримання вірного розв’язку задачі, що ставиться, тобто задовольняти вимогам правильності.

Розглянемо деякі основні принципи, за якими будуються алгоритми:

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

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

3 Робота алгоритму складається з окремих елементарних кроків, до того ж множина кроків, з яких складено алгоритм є скінченною.

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

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

Слід розрізняти:

- опис алгоритму (реалізовану програму);

- механізм реалізації, що включає засоби пуску, зупинення, реалізації елементарних кроків, видачі результатів та забезпечення управління ходом обчислення (ЕОМ);

- процес реалізації алгоритму, тобто послідовність кроків, яка утвориться в результаті застосування алгоритму до конкретних даних [3].

Для створення алгоритму необхідно знати:

- яку роботу повинен виконувати алгоритм;

- якими повинні бути вхідні дані;

- якими повинні бути вихідні дані.

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

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

2 Гнучкі алгоритми, наприклад стохастичні, тобто ймовірнісні та евристичні. Ймовірнісний (стохастичний) алгоритм надає програму для розв'язання задачі декількома шляхами або способами, що призводять до вірогідного досягнення результату. Евристичний алгоритм – це алгоритм, що використовує різні розумні міркування без чітких обґрунтувань.

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

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

Навчальний посібник дозволить студентам:

- ознайомитися з формами подання алгоритмів та зі структурою алгоритмів;

- ознайомитися з основними характеристиками алгоритму: алфавітом даних та формою їх подання, пам’яттю та розміщенням в ній елементів;

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

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

 

 

ЗАГАЛЬНІ ВІДОМОСТІ

 

1 Формалізація та алгоритмізація обчислювальних процесів

 

Під час розв’язання задач визначеного спрямування: математичних, інженерних, економічних та інших, розробник повинен:

1) сформулювати умови задачі;

2) виконати математичний опис задачі;

3) обрати та обґрунтувати метод розв’язання задачі;

4) провести алгоритмізацію обчислювального процесу;

5) скласти програму;

6) налагодити програму;

7) розв’язати задачу на ЕОМ та проаналізувати результати.

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

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

Нехай D – область (множина) первинних даних задачі, а R – множина можливих результатів, тоді можна говорити, що алгоритм здійснює відображення D → R.

Алгоритмами, наприклад, є правила додавання, множення, розв’язання алгебраїчних рівнянь, множення матриць, тощо. Слово «алгоритм» походить від лат. algoritmi, що є латинською трансляцією арабського імені хорезмійського математика IX століття Абу́ Абдулла́х (або Абу Джафар) Муха́ммад ибн Муса́ аль-Хорезмі. Завдяки латинському перекладу трактату аль-Хорезмі європейці в XII столітті ознайомилося з позиційною системою числення, а в середньовічній Європі алгоритмом називалася десяткова позиційна система числення та правила розрахунків за її допомогою.

Для запису послідовності дій, описаних алгоритмом у ЕОМ, потрібна формалізована мова - мова програмування, а сам запис алгоритму такою мовою називають програмою.

Алгоритм повинен мати наступні властивості:

1 Зрозумілість - виконувач алгоритму повинен знати як його виконувати.

2 Дискретність - алгоритм повинен відображати процес розв’язання задачі як послідовне виконання простих (або раніше визначених) кроків (етапів).

3 Результативність - можливість отримання результату після виконання кінцевої кількості операцій.

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

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

Існують наступні типи алгоритмів:

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

2 Розгалужений алгоритм - це алгоритм, дії якого виконуються залежно від виконання (або невиконання) певної умови (питання, на яке можна відповісти тільки «так» або «ні»).

3 Циклічний алгоритм - це алгоритм, дії якого повторюються.

 

Способи опису алгоритмів:

1) словесно-формульний, за якого алгоритм записується у вигляді тексту з формулами відповідно до пунктів, що визначають послідовність дій;

2) структурний або блок-схемний, за якого алгоритм зображується геометричними фігурами (блоками), пов’язаними між собою відповідно до управління лініями (напрямками потоків) зі стрілками; в блоках записується послідовність дій;

3) із використанням граф-схем;

4) із використанням мереж Петрі.

 

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

 

Таблиця 1 – Призначення блоків структурного опису алгоритмів

 

 

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

Продовження таблиці 1 – Призначення блоків структурного опису алгоритмів

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