Python: алгоритмізація та програмування
Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування теорії алгоритмів та основ програмування, розроблення прикладних засобів та інформаційних систем аналізу та опрацювання інформації за допомогою алгоритмів на мові Python. Теоретичний та практичний матеріал викладено у доступній формі. Викладення матеріалу супроводжується значною кількістю прикладів, що полегшує його сприйняття та засвоєння. Подається перелік питань та тестів для самоконтролю, а також завдань для самостійного виконання трьох рівнів складності. Навчальний посібник призначається для студентів, що навчаються за спеціальностями 122 «Комп’ютерні науки», 124 «Системний аналіз», 126 «Інформаційні системи та технології» та споріднених спеціальностей, які пов’язані з інформатикою та інформаційними технологіями. Він може бути використаний аспірантами як підґрунтя для наукових досліджень та викладачами як дидактичний матеріал, а також для самостійного вивчення. Книга призначена для спеціалістів із проектування, розроблення та впровадження інтелектуальних систем опрацювання інформаційних ресурсів, науковців у галузі глобальних інформаційних системи, систем штучного інтелекту, Інтернет-технологій, фахівців з електронної комерції, Інтернет-маркетингу та Інтернет-реклами, менеджерів комплексних Web-проектів, а також для здобувачів 3-ого (освітньо-наукового) рівня вищої освіти в галузі знань 12 «Інформаційні технології». Кожний розділ закінчується переліком питань для самоконтролю, прикладом тестових питань з відповідями та переліком індивідуальних завдань для виконання лабораторних робіт.
Вступ 9
Розділ 1. Основи програмування 17
1.1. Парадигми програмування 17
1.1.1. Системне програмування 17
1.1.2. Структурне та процедурне програмування 17
1.1.3. Модульне та об’єктно-орієнтоване програмування 18
1.1.4. Функційне програмування 19
1.2. Середовище програмування та програмне забезпечення для Python 19
1.2.1. Інтерактивний режим 20
1.2.2. Створення скриптів 22
1.3. Математичні операції на Python 22
1.4. Порядок виконання операцій 25
1.5. Написання програм на Python 26
1.5.1. Редагування файлів 26
1.5.2. Запускаємо програму з файлу 26
1.6. Функція input 27
1.7. Питання для самоперевірки 29
1.8. Завдання для самостійної роботи 29
Розділ 2. Системи числення 31
2.1. Позиційні системи числення 31
2.2. Одиниці виміру інформації 33
2.3. Двійкова система числення 33
2.4. Вісімкова система числення 35
2.5. Шістнадцяткова система числення 36
2.6. Двійково-вісімкові перетворення 37
2.7. Двійково-шістнадцяткові перетворення 38
2.8. Вісімково-шістнадцяткові перетворення 39
2.9. Питання для самоперевірки 40
2.10. Завдання для самостійно роботи 41
Розділ 3. Типи даних в мові програмування Python 42
3.1. Булевий тип (bool) 42
3.1.1. Логічні вирази і логічний тип даних 42
3.1.2. Логічні оператори, або Булеанівські вирази 42
3.1.3. Складні логічні вирази 44
3.2. Числа 44
3.2.1. Цілі числа (integer) 45
3.2.2. Числа з плаваючою комою (float) 45
3.2.3. Додаткові методи 45
3.3. Змінні 46
3.4. String як складний тип даних 47
3.4.1. Екрановані послідовності 50
3.4.2. Рядки у потрійних лапках чи апострофах 50
3.4.3. Довжина рядка 50
3.5. Комплексні числа (complex) 51
3.6. Питання для самоперевірки 51
3.7. Завдання для самостійної роботи 52
Розділ 4. Основи алгоритмізації 64
4.1. Поняття алгоритму та способи його подання 64
4.2. Властивості та класи алгоритмів 67
4.3. Розроблення програми 73
4.3.1. Структура модуля в Python 73
4.3.2. Багатомодульні програми 73
4.3.3. Помилки 74
4.3.4. Техніка налагодження (зневаджування) програм 74
4.4. Розроблення алгоритму програми 75
4.4.1. Рекурсія 76
4.4.2. Динамічне програмування 76
4.5. Приклади бібліотек Python 76
4.5.1. Matplotlib 76
4.5.2. NetworkX 78
4.5.3. csv 79
4.5.4. NumPy 79
4.5.5. Інші бібліотеки 80
4.6. Питання для самоперевірки 80
4.7. Тестові завдання 80
4.8. Ключ до тестових завдань 81
Розділ 5. Умовний оператор 82
5.1. Інструкція if 82
5.2. Оператори “else” та “elif” – коли це не є правдивим (True) виразом 88
5.3. Завдання для самостійної роботи 90
Розділ 6. Цикли в мові Python 96
6.1. Цикл while 96
6.2. Відступи 100
6.3. Цикл for 101
6.4. Завдання для самостійної роботи 103
Розділ 7. Файли 110
7.1. Відкриття та закриття файлу в Python 110
7.2. Список режимів доступу до файлу у мові Python 110
7.3. Інші Функції Вводу та Виводу 112
7.4. Пікли (Pickles), або як зберегти дані у файл 113
7.5. Завдання для самостійної роботи 115
Розділ 8. Кортежі, списки та словники 118
8.1. Відмінність списків, кортежів та словників 118
8.2. Незмінюваний тип таних 118
8.3. Змінювані впорядковані послідовності об'єктів 119
8.4. Змінюваний невпорядкований набір об’єктів 122
8.5. Присвоювання для списків 126
8.6. Порівняння для списків 127
8.7. Умовні твердження(висловлювання) 128
8.8. Послідовності 128
8.9. Операції над послідовностями різних типів 129
8.10. Процедурний чи декларативний стиль 130
8.11. Завдання для самостійної роботи 131
Розділ 9. Стеки, черги та деки 139
9.1. Стеки 139
9.1.1. Реалізація стеку за допомогою масиву 140
9.1.2. Реалізація стека за допомогою списку 140
9.1.3. Системний стек в програмах 142
9.2. Черги 142
9.2.1. Реалізація черги за допомогою масиву 143
9.2.2. Реалізація черги за допомогою списку 143
9.3. Деки 144
9.4. Завдання для самостійної роботи 145
Розділ 10. Функції 151
10.1. Використання Функцій 151
10.2. Параметри і результати функцій – зв’язок з функцією 151
10.3. Функції, як основа структурного програмування 155
10.3.1. Вхідні та вихідні дані функції 155
10.3.2. Програма Калькулятор 156
10.3.3. Визначення власних функцій 159
10.3.4. Параметри і аргументи функцій 160
10.3.5. Кінцева програма 161
10.4. Локальні та глобальні змінні 163
10.5. Створення функції меню 164
10.6. Наша перша “Гра” 165
10.7. Покращуємо гру 168
10.8. Складні випадки використання функцій 169
10.8.1. Функція, як аргумент 169
10.8.2. Функції вищого рівня 170
10.9. Рекурсія 171
10.10. Обмеження на глибину рекурсії 176
10.11. Опрацювання помилок 178
10.12. Винятки (Exceptions, Ексепшини) – обмеження коду 180
10.13. Хрестики-нулики на Python (текстовий варіант) 183
10.14. Питання для самоперевірки 185
10.15. Тестові завдання 185
10.16. Ключ до тестових завдань 188
10.17. Завдання для самостійної роботи 188
Розділ 11. Графіка та модуль turtle 202
11.1. Простота роботи з модулем turtle 202
11.2. Основні команди Черепашки (модуль turtle) 205
11.2.1. Команда «повзати» 206
11.2.2. Команда «малювати» 206
11.2.3. Команда «взнати про черепашку» 206
11.2.4. Команда «інтерактив» 206
11.2.5. Ще нетривіальні приклади 207
11.3. Обмеження модуля turtle 228
11.4. Генератор случайных чисел 232
11.5. Цикл for для повторення частини коду 234
11.6. Список як засіб збереження даних 240
11.7. Завдання для самостійної роботи 242
Розділ 12. Алгоритми пошуку та хешування 249
12.1. Пошукові алгоритми та їх загальна класифікація 249
12.1.1. Лінійний пошук 249
12.1.2. Двійковий (бінарний) пошук елемента в масиві 249
12.1.3. Пошук методом Фібоначчі 249
12.1.4. Інтерполяційний пошук 250
12.1.5. Бінарний пошук із визначенням найближчих вузлів 250
12.2. Хешування даних 251
12.2.1. Поняття хеш-функції 251
12.2.2. Хеш-таблиці 252
12.2.3. Алгоритми хешування 254
12.2.4. Динамічне хешування 255
12.2.5. Методи розв’язування колізій 257
12.2.6. Уникнення колізій за допомогою ланцюгів 260
12.2.7. Переповнення таблиці і рехешування 262
12.2.8. Хеш-функції 263
12.2.9. Відкрита адресація 266
12.2.10. Оцінювання якості хеш-функції 270
12.3. Пошук з використанням хеш-функції 271
12.4. Питання для самоперевірки 273
12.5. Тестові завдання 273
12.6. Ключ до тестових завдань 274
12.7. Індивідуальні завдання для виконання лабораторних робіт 274
Розділ 13. Алгоритми сортування 277
13.1. Методи внутрішнього сортування 277
13.1.1. Сортування обміном (метод бульбашки) 278
13.1.2. Шейкерне сортування 281
13.1.3. Сортування вставкою (включенням) 281
13.1.4. Сортування прямим вибором 293
13.1.5. Швидке сортування (метод Хоара) 295
13.1.6. Сортування за допомогою дерева 306
13.1.7. Сортування за лінійний час 307
13.1.8. Піраміди 313
13.1.9. Сортування методом злиттям 325
13.1.10. Методи порозрядного сортування 336
13.2. Методи зовнішнього сортування 339
13.2.1. Пряме злиття 340
13.2.2. Природне злиття 340
13.2.3. Збалансоване багатошляхове злиття 341
13.2.4. Багатофазне сортування 342
13.3. Питання для самоперевірки 344
13.4. Тестові завдання 344
13.5. Ключ до тестових завдань 346
13.6. Індивідуальні завдання для виконання лабораторних робіт 346
Розділ 14. Об’єктно-орієнтоване програмування 348
14.1. Класи та об’єкти 349
14.2. Використання класу 350
14.2.1. Приховування атрибутів класу¶ 351
14.2.2. Сетери, гетери і делетери 352
14.2.3. Властивості 353
14.2.4. Обчислювані властивості 354
14.3. Конструктори та деструктори класу 355
14.4. Наслідування 357
14.5. Поліморфізм 359
14.6. Інкапсуляція 361
14.7. Композиція 366
14.8. Перевантаження операторів 367
14.9. Вказівники 371
14.10. Імпортування модулів 371
14.10.1. Що таке модуль? 371
14.10.2. І ще кілька фішок по модулях 373
14.11. Завдання для самостійної роботи 374
Розділ 15. Модуль tkinter 376
15.1. Користувацькі підпрограми і моделювання на основі tkinter 376
15.2. Моделювання математичних функцій 378
15.3. Моделювання фізичного явища: тіло, кинуте під кутом до горизонту 382
15.4. Tkinter замість Черепашки 385
15.5. Опрацювання подій після натискання кнопок 388
15.6. Графічні примітиви tkint 390
15.7. Вспомним цикл for и rnd 391
15.8. Приймаємо рішення, або оператор вибору в tkinter 392
15.9. Деякі задачі для for та while в tkinter 395
15.10. Мишка залишає слід. Працюємо з інформацією про event в Tkinter 397
15.11. Робимо першу гру на Python з модулем tkinter: злови кульку 400
15.12. Починаємо створювати гру «Jumper» (майже як Doodle). Анімація 406
15.13. Продовжуємо робити гру «Jumper». Об’єкти як екземпляри класів 413
15.14. Закінчуємо гру Jumper (майже Doodle) 422
15.15. Створюємо список «кульок» для наступних завдань 428
15.16. Опрацювання списків в tkinter 432
15.17. Перевірьте себе 435
15.18. Завдання для самостійної роботи 439
Розділ 16. Модуль pygame 447
16.1. Особливості розролення комп'ютерних ігор 447
16.2. Місце Pygame серед інструментів розробки ігор 448
16.3. Як встановити Pygame 448
16.4. Вікно відкривається і закривається 449
16.5. Сцени та меню 453
16.6. Анімація в русі 461
16.7. Управління та зіткнення 465
16.8. Звуки музики 468
16.9. Шари і групи 470
16.10. Цілочисельні координати 472
16.10.1. Render 472
16.10.2. Фізика 472
Розділ 17. Модуль NymPy 475
17.1. Пачаток роботи 475
17.1.1. Установка NumPy 475
17.1.2. Починаємо роботу 475
17.1.3. Створення масивів 475
17.1.4. Друк масивів 477
17.2. Базові операції над масивами 478
17.2.1. Базові операції 478
17.2.2. Індекси, зрізи, ітерації 479
17.2.3. Маніпулювання з формою 481
17.2.4. Поєднання масивів 482
17.2.5. Розбиття масиву 483
17.2.6. Копії та подання 483
17.3. Random 484
17.3.1. Шлях перший 485
17.3.2. numpy.random 485
17.3.3. Створення масивів 485
17.3.4. Вибір і перемішування 486
17.3.5. Ініціалізація генератора випадкових чисел 486
17.4. Linalg 487
17.4.1. Підняття ступення 487
17.4.2. Розкладання 487
17.4.3. Деякі характеристики матриць 487
17.4.4. Системи рівнянь 487
17.5. 100 NumPy класичнихзадач 488
Розділ 18. Python для Web через CGI 498
18.1. CGI: пишемо простий сайт на Python 498
18.1.1. Настройка локального сервера 498
18.1.2. Hello world 499
18.2. Опрацювання форм та cookies 499
18.2.1. Отримання даних із форм 499
18.2.2. Уразливість при екрануванні небезпечних символів 501
18.2.3. Cookies 502
18.2.4. Опрацювання Cookies 503
18.3. Приклад додатку 504
18.4. Публікація в мережі Інтернет 508
Термін “інформація” походить від латинського слова “informatio”– виклад, роз’яснення фактів, подій. Тому, в найширшому розумінні інформація трактується як відомості, пояснення, знання про об’єкти, явища та процеси реального світу. Основна маса інформації збирається, передається та опрацьовується у знаковій формі – числовій, текстовій, табличній, графічній і ін. Знакове подання інформації інформатика пов’язує з поняттям “дані”. Дані – це відомості, подані у певній знаковій формі, придатній для передавання, інтерпретації та опрацювання людиною або автоматичним пристроєм.
Взаємозв’язок між інформацією, даними і методами оперування ними характеризується низкою властивостей. Інформація має динамічний характер. Вона не є статичним об’єктом, а динамічно змінюється й існує тільки у момент взаємодії даних і методів, тобто в момент протікання інформаційного процесу. Весь інший час вона перебуває у стані даних. Зв’язок даних і методів носить діалектичний характер. Дані є об’єктивними, коли вони виникають у результаті реєстрації об’єктивно існуючих сигналів, викликаних змінами в матеріальних тілах або полях. У той же час, методи оперування даними в інформаційних процесах є суб’єктивними. Дійсно, інформаційний процес здійснюється за допомогою штучних або природних методів, в основі штучних методів лежать алгоритми, складені і підготовлені людьми (суб’єктами), в основі природних – біологічні властивості суб’єктів інформаційного процесу. Дані надають інформацію лише в момент їх використання. Це означає, що дані, які зберігаються, залишаються лише даними, поки їх не використано в тих чи інших методах деяким суб’єктом інформаційного процесу (людиною або автоматичним пристроєм). Якщо дані зовсім не використовуються, то кажуть, що вони мають нульову інформативність, і вважають такі дані інформаційним шумом. Дані, що використовуються, називають інформативними. Рівень інформативності даних залежить від ступеня адекватності методів, що застосовуються в інформаційних процесах. Дані сприймаються їх отримувачем як певна змістовна інформація лише в тому випадку, коли в його “пам’яті” закладені поняття і моделі, що дають змогу зрозуміти зміст отриманих відомостей. Коли дані опрацьовуються певними методами або евристиками, то на їх основі можна встановити залежності, послідовності чи висновки, які дають змогу здійснити підтримку процесу прийняття рішення. Основними в інформатиці є три поняття: задача, алгоритм, програма. Відповідно, маємо три етапи в розв’язуванні задач (зазначимо, що, з точки зору інформатики, розв’язати задачу – це отримати програму, тобто, забезпечити можливість отримати рішення за допомогою комп’ютера): постановка задачі, побудова і обґрунтування алгоритму, складання і налагодження програми. Оскільки програма – об’єкт гранично формальний, а тому точний (можливо не завжди прозорий, навантажений неістотними із змістовної точки зору деталями, але недвозначний) то, пов’язані з нею об’єкти також мають бути точними. Поняття алгоритму інтуїтивно зрозуміле і часто використовується в математиці та інформаційних технологіях, зокрема в комп’ютерних науках, системному аналізі та розробленні інформаційних систем.
Термін “алгоритм” походить із давніх-давен. Понад тисячу років тому у Багдаді жив Абу Джафар Мухамад ібн Муса аль-Хорезмі, який у своїй праці “Трактат аль-Хорезмі про арифметичне мистецтво індусів” з арифметики та алгебри сформулював правила і окреслив послідовність дій при додаванні та множенні чисел. При переведенні латиною ім’я автора трансформувалося в Algorithmi, а з часом методи розв’язування задач стали називати алгоритмами.
Алгоритм – це система формальних правил, які чітко та однозначно визначають послідовність дій обчислювального процесу від початкових даних до шуканого результату. Алгоритм визначає певні правила перетворювання інформації, тобто визначає певну послідовність операцій опрацювання даних для отримання розв’язку задачі. Також кажуть, що алгоритм – це скінченна послідовність команд, які потрібно виконати над вхідними даними для отримання результату. Побудова алгоритму за точною постановкою задачі дає змогу обґрунтувати його математичними методами. Більше того, існують класи задач, які забезпечують формальне перетворення специфікації в алгоритм. Суттєво, що, порівняно з програмою, алгоритм може перебувати на вищому рівні абстракції, бути вільним від певних деталей реалізації, пов’язаних із особливостями мови програмування та конкретної обчислювальної системи. Засоби для зображення алгоритмів називають алгоритмічною мовою. При цьому жодна мова програмування не може цілком замінити алгоритмічну мову, оскільки консервативна за своєю суттю. Модифікація мови програмування призводить до небажаних наслідків: вимагає перероблення системи програмування, знецінює напрацьоване програмне забезпечення. У той же час алгоритмічна мова може створюватись спеціально для певної предметної області, певного класу задач або навіть окремої задачі.
У цьому посібнику розглядається одна з найбільш розповсюджених мов програмування – мова Phyton. Хоча колись була найпопулярнішою мовою С, створена 1972 року як мова для системного програмування, вона отримала широке поширення у всьому світі. Сьогодні вона має багатьох наступників серед мов програмування: C++, Java, C#, C, Phyton, Scala, JavaScript, Perl тощо.
Поняття алгоритму інтуїтивно зрозуміло та часто використовується в математиці та комп’ютерних науках. Говорячи неформально, алгоритм – це довільна коректно визначена обчислювальна процедура, на вхід якої подається деяка величина або набір величин, а результатом виконання якої є вихідна величина або набір значень. Таким чином, алгоритм є послідовністю обчислювальних кроків, які перетворюють вхідні величини у вихідні. Алгоритм можна також розглядати як інструмент, який призначений для вирішення коректно поставленої обчислювальної задачі. У постановці задачі в загальних рисах визначаються відношення між входом та виходом. В алгоритмі описується конкретна обчислювальна процедура, за допомого якої можна досягнути виконання вказаних відношень. Можна навести загальні риси алгоритму:
a. Дискретність інформації. Кожний алгоритм має справу з даними: вхідними, проміжними, вихідними. Ці дані представляються у вигляді скінченних слів деякого алфавіту.
b. Дискретність роботи алгоритму. Алгоритм виконується по кроках та при цьому на кожному кроці виконується тільки одна операція.
c. Детермінованість алгоритму. Система величин, які отримуються в кожний (не початковий) момент часу, однозначно визначається системою величини, які були отримані в попередні моменти часу.
d. Елементарність кроків алгоритму. Закон отримання наступної системи величин з попередньої повинен бути простим та локальним.
e. Виконуваність операцій. В алгоритмі не має бути не виконуваних операцій. Наприклад, неможна в програмі призначити значення змінній “нескінченність”, така операція була би не виконуваною. Кожна операція опрацьовує певну ділянку у слові, яке обробляється.
f. Скінченність алгоритму. Опис алгоритму повинен бути скінченним.
g. Спрямованість алгоритму. Якщо спосіб отримання наступної величини з деякої заданої величини не дає результату, то має бути вказано, що треба вважати результатом алгоритму.
h. Масовість алгоритму. Початкова система величин може обиратись з деякої потенційно нескінченної множини.
Розглянемо для прикладу задачу сортування послідовності чисел у зростаючому порядку. Ця задача часто виникає на практиці і, фактично, буде центральною проблемою першого розділу даного курсу. Задача сортування визначається формально наступним чином.
Вхід: послідовність n чисел
Вихід: перестановка вхідної послідовності таким чином, що для всіх її членів виконується співвідношення .
Наприклад, якщо на вхід подається послідовність <31, 41, 59, 26, 11, 58>, то вивід алгоритму сортування повинен бути таким: <26, 31, 41, 41, 58, 59>. Подібна вихідна послідовність називається екземпляром задачі сортування. Взагалі, екземпляр задачі складається із входу, який необхідний для розв’язання задачі та який задовольняє усім обмеженням, які присутні в постановці задачі. В комп’ютерних науках сортування є основною операцією (у багатьох програмах вона використовується в якості проміжного кроку), в результаті чого з’явилось багато якісних алгоритмів сортування. Вибір найбільш адекватного алгоритму залежить від багатьох факторів, в тому числі й від кількості елементів для сортування, від їх порядку у вхідній послідовності, від можливих обмежень, які накладаються на членів послідовності. Кажуть, що алгоритм є коректним, якщо для кожного входу результатом його роботи є коректний вивід. Тоді коректний алгоритм розв’язує дану обчислювальну задачу. Якщо алгоритм некоректний, то для деяких входів він може взагалі не завершити свою роботу, або видати відповідь, яка відрізняється від очікуваної.
Перелічимо переваги використання алгоритмізації в програмуванні.
По-перше, алгоритми є життєво необхідними складовими для рішення будь-яких задач з різноманітних напрямків комп’ютерних наук. Алгоритми відіграють ключову роль у сучасному розвитку технологій. Тут можна згадати такі розповсюджені задачі, як:
- розв’язання математичних рівнянь різної складності, знаходження добутку матриць, обернених матриць;
- знаходження оптимальних шляхів транспортування товарів та людей;
- знаходження оптимальних варіантів розподілення ресурсів між різними вузлами (виробниками, верстатами, працівниками, процесорами тощо);
- знаходження в геномі послідовностей, які співпадають;
- пошук інформації в глобальній мережі Інтернет;
- прийняття фінансових рішень в електронній комерції;
- опрацювання та аналіз аудіо та відео інформації.
Цей список можна продовжувати й продовжувати і, власно кажучи, майже неможливо знайти таку галузь комп’ютерних наук та інформатики, де б не використовувались ті або інші алгоритми.
По-друге, якісні та ефективні алгоритми можуть бути каталізаторами проривів у галузях, які є на перший погляд далекими від комп’ютерних наук (квантова механіка, економіка та фінанси, теорія еволюції).
І, по-третє, вивчення алгоритмів це також неймовірно цікавий процес, який розвиває наші математичні здібності та логічне мислення.
Тепер розглянемо поняття ефективності алгоритму. Припустимо, швидкодія комп’ютеру та об’єм його пам’яті можна збільшувати до нескінченності. Чи була би тоді необхідність у вивченні алгоритмів? Так, але тільки для того, щоб продемонструвати, що метод розв’язку має скінченний час роботи і що він дає правильну відповідь. Якщо б комп’ютери були необмежено швидкими, підійшов би довільний коректний метод рішення задачі. Звісно, тоді найчастіше обирався би метод, який найлегше реалізувати.
Сьогодні є дуже потужні комп’ютери, але їх швидкодія не є нескінченно великою, як і пам’ять. Таким чином, час обчислення – це такий само обмежений ресурс, як і об’єм необхідної пам’яті. Цими ресурсами слід користуватись розумно, чому й сприяє застосування алгоритмів, які ефективні в плані використання ресурсів часу та пам’яті.
Алгоритми, які розроблені для розв’язання однієї та тієї самої задачі, часто можуть дуже сильно відрізнятись за ефективністю. Ці відмінності можуть бути набагато більше помітними, чим ті, які викликані застосуванням різного апаратного та програмного забезпечення.
Для прикладу розглянемо та порівняємо задачі сортування. Перший алгоритм, який буде розглядатись – сортування включенням, для своєї роботи вимагає часу, кількість якого оцінюється як c1n2, де n – розмір вхідних даних (кількість елементів у послідовності для сортування), c1 – деяка стала. Цей вираз вказує на те, як залежить час роботи алгоритму від об’єму вхідних даних. У випадку сортування включенням ця залежність є квадратичною. Другий алгоритм – сортування злиттям – потребує часу, кількість якого оцінюється як c2nlog2n. Зазвичай константа сортування включенням менше константи сортування злиттям, тобто c1<c2, але як пересвідчимось у наступних темах, ці константи не відіграють ролі у порівнянні швидкодії різних алгоритмів. Адже зрозуміло, що функція n2 зростає швидше зі збільшенням n, аніж функція nlog2n. І для деякого значення n = n0 буде досягнуто такий момент, коли вплив різниці констант перестане мати значення і надалі функція c2nlog2n буде менша за c1n2 для будь-яких n > n0.
Для демонстрації цього розглянемо два комп’ютери – А та Б. Комп’ютер А більш швидкий і на ньому працює алгоритм сортування, а комп’ютер Б більш повільний і на ньому працює алгоритм сортування методом злиття. Обидва комп’ютери повинні виконати сортування множини, яка складається з мільйона чисел. Припустимо, що комп’ютер А виконує мільярд операцій в секунду, а комп’ютер Б – лише десять мільйонів, тобто А працює в 100 разів швидше за Б. Щоб різниця стала більш відчутною, припустимо що код методу включення написаний найкращим програмістом в світі із використанням команд процесору, і для сортування n чисел за цим алгоритмом потрібно виконати 2n2 операцій (тобто c1=2). Сортування методом злиття на комп’ютері Б написано програмістом початківцем із використанням мови високого рівня і отриманий код потребує 50nlog2n операцій (тобто c2=50). Таким чином для сортування мільйона чисел комп’ютеру А буде потрібно , а комп’ютеру Б – .
Тож, використання коду, час роботи якого зростає повільніше, навіть при поганому комп’ютері та поганому компіляторі потребує на порядок менше процесорного часу! Для сортування 10 мільйонів чисел перевага сортування злиттям стає ще більш відчутною: якщо сортування включенням потребує для такої задачі приблизно 2,3 дня, то для сортування злиттям – менше 20 хвилин. Загальне правило таке: чим більша кількість елементів для сортування, тим помітніше перевага сортування злиттям. Наведений вище приклад демонструє, що алгоритми, як і програмне забезпечення комп’ютеру, являють собою технологію. Загальна продуктивність системи настільки ж залежить від ефективності алгоритму, як і від потужності апаратних засобів.
Тепер визначимо золоте правило розробників алгоритмів. Для цього розглянемо для прикладу просту задачу, яка відома усім ще з початкової школи, а також метод розв’язання цієї задачі – множення двох цілих чисел. Цю задачу можна описати наступним чином:
Вхід: 2 цілих n-розрядних числа x та y
Вихід: добуток чисел x·y
Розглянемо приклад для чисел x = 5678 та y = 1234. Результат відомого з дитинства методу множення в стовпчик буде виглядати наступним чином:
Легко зауважити, що елементарні операції, які тут використовуються, це – множення та додавання однорозрядних чисел. Припустивши, що операція множення займає більше часу аніж операція додавання для однієї пари чисел, оцінимо кількість таких елементарних операцій. Всі вони виконується в області, яка вище позначена сірим кольором. В даному прикладі кількість елементарних операцій добутку становитиме 16 = 42, а в загальному випадку становитиме n2. Тож, кількість операцій для добутку двох цілих n-розрядних чисел методом множення у стовпчик оцінюється як cn2, де c – деяка стала.
Проте чи можемо покращити цей результат, отримавши метод добутку чисел, який буде працювати швидше? Щоб мотивувати себе для пошуку такого методу, наведемо цитату з книги «Розробка та аналіз комп’ютерних алгоритмів» (Аго, Гопкрофт, Ульман, 1974): «Можливо найбільш важливим принципом для гарного розробника алгоритмів є відмова від того, щоб бути задоволеним результатом». Слідуючи цьому правилу, розглянемо ще раз детальніше природу об’єктів задачі добутку чисел. За умовою на вхід подається два n-розрядних числа. Припустимо розіб’ємо кожне число навпіл, отримавши, так звані, верхнє та нижнє півслова. Тобто, можна записати x=10n/2a+b та y=10n/2c+d, де a, b, c, d – цілі n/2-розрядні числа. Тоді добуток x·y можна представити так:
xy=(10n/2a+b)(10n/2c+d)=10nac+10n/2(ad+bc)+bd.
Таким чином ми природно підійшли до рекурсивного методу обчислення добутку двох цілих чисел, який зводить обрахунок добутку двох n-розрядних чисел до обрахунку чотирьох добутків n/2-розрядних чисел. Спробуємо з’ясувати, чи покращиться таким чином швидкість добутку двох чисел. Кожне з чисел a, b, c, d мають n/2 розрядів, а відтак добуток будь-якої їх пари (якщо використовувати для нього старий алгоритм множення у стовпчик) займатиме c(n/2)2 операцій, тобто cn2/4. Чотири таких добутки в сумі знову дадуть початковий результат: 4cn2/4 = cn2. Отже, виграш за часом не було отримано. Невже не можливо покращити результат роботи методу множення чисел у стовпчик? Насправді, можливо і відповіддю на це питання є метод множення Карацуби (1960). Якщо подивитись на формулу xy, то помітимо, що насправді важливими є не чотири добутки, а три: ac, bd та (ad + bc), тобто елементи ad та bc не цікавлять самі по собі, а лише їх сума. Чи можна отримати їх суму перемноживши лише два числа? Так:
(a+b)(c+d)=ac+ad+bc+bd=(ad+bc)+ac+bd та ad+bc=(a+b)(c+d)-ac-bd
Таким чином, суму (ad+bc) можна отримати з добутку двох n/2-розрядних числа (можливо, n/2 + 1) (a+b) та (c+d), а також добутків ac та bd, які вже маємо. І, отже, кількість рекурсивних викликів скоротились з 4 до 3. Аналіз швидкості методу множення Карацуби приводить до оцінки . Цей приклад красномовно свідчить, що простір для руху розробника алгоритмів є набагато більшим ніж може видаватись на початку.
Навчальний посібник містить матеріал для вивчення основних теоретичних засад, функціональних можливостей та практичного застосування теорії алгоритмів та основ програмування, розроблення прикладних засобів та інформаційних систем аналізу та опрацювання інформації за допомогою алгоритмів. Викладення матеріалу супроводжується значною кількістю прикладів, що полегшує його сприйняття та засвоєння. Навчальний посібник призначається для студентів, що навчаються за спеціальностями 122 «Комп’ютерні науки», 124 «Системний аналіз» та 126 «Інформаційні системи та технології» і споріднених спеціальностей, які пов’язані з вивченням чисельних методів в інформатиці та інформаційних технологій. Може бути використаний аспірантами як підґрунтя для наукових досліджень та викладачами як дидактичний матеріал, а також для самостійного вивчення та підвищення кваліфікації. Книга призначена для спеціалістів із проектування, розроблення та впровадження інтелектуальних систем опрацювання інформаційних ресурсів, науковців у галузі глобальних інформаційних системи, систем штучного інтелекту, Інтернет-технологій, фахівців з електронної комерції, Інтернет-маркетингу та Інтернет-реклами, менеджерів комплексних Web-проектів, а також для здобувачів 3-го (освітньо-наукового) рівня вищої освіти в галузі знань 12 «Інформаційні технології». Кожний розділ закінчується переліком питань для самоконтролю, прикладом тестових питань з відповідями до екзаменаційних білетів та переліком індивідуальних завдань для виконання лабораторних робіт.
Розділ 1 присвячений основам програмування, елементам обчислювальних машин та описує архітектуру комп’ютерів. Детально пояснені та описані архітектурні принципи Джона фон Неймана, машинні та високорівневі мови програмування, парадигми програмування. Приділено увагу класифікації мов програмування, а саме пояснені відмінності між системним програмуванням, структурним та процедурним програмування, модульним та об’єктно-орієнтованим програмування, а також функційним програмуванням. В розділі подано пояснення щодо середовища програмування та програмного забезпечення для Python, а саме робота в інтерактивному режимі, створення скриптів, особливості математики на Python, порядок операцій та використання коментарів в коді програми на Python. Також описано особливості написання програм на Python, пояснені етапи створення програми у файлі на Python,редагування файлів, запуск програм з файлу та робота з функцією input.
Розділ 2 описує позиційні системи числення (двійкова, вісімкова, шістнадцяткова система числення, та взаємозв’язок між ними). В третьому розділі описані типи даних в мові програмування Python (булеві, цілі, дійсні та стрічки), змінні та рядки, екрановані послідовності та їх форматування.
Розділ 4 присвячений основам алгоритмізації, зокрема, поняттям алгоритму та способи його подання, властивостям та класам алгоритмів. Описано структуру модуля в Python, багатомодульні програми, помилки, техніку налагодження (зневаджування) програм та розроблення алгоритму програми. Наведені приклади бібліотек Python як Matplotlib, NetworkX, csv, NumPy тощо.
Розділ 5 описує особливості побудови логічних виразів на Python, а розділ 6 присвячений циклам while та for в мові Python, а також розкриває важливість відступів у блоковому програмуванні. Робота з файлами описано в розділі 7. Розділ 8 описує особливості роботи з кортежами, списками та словниками. В розділі 9 розкриті питання роботи зі стеком, чергою та деком. Робота з функціями та рекурсією подана в розділі 10. Розділ 11 присвячений питанням роботи з графікою через бібліотеку turtle.
Алгоритми пошуку описані детально в розділі 12, зокрема: лінійний пошук, двійковий (бінарний) пошук елемента в масиві, пошук методом Фібоначчі, інтерполяційний пошук. Також цей розділ присвячений питанням хешування. Розділ 13 описує відомі алгоритми сортування, а саме: бульбашки, шейкерне, вставкою, метод Шелла, метод Хоара тощо. Розділ 14 описує особливості програмування з використанням класів, розділ 15 – графіка та створенні ігор через бібліотеку tkinter. Створення ігор використанням бібллотеки pygame присвячено розділ 16, роботі з масивами через біблотеку NymPy – розділ 17. Розділ 18 присвячений особливостям роботи на Python для Web через CGI.
Автори цього навчального посібника висловлюють щиру подяку фахівцям в галузі знань 12 “Інформаційні технології” за плідну співпрацю, вагомі поради та слушні зауваження при формуванні структури книги та її наповнення. Зокрема, дякуємо за підтримку:
Бісікалу О.В. – д.т.н., професору, завідувачу кафедри автоматики та інформаційно-вимірювальної техніки Вінницького національного технічного університету;
Винокуровій О.А. – д.т.н., професору, головному науковому співробітнику Проблемної науково-дослідної лабораторії АСУ Харківського національного університету радіоелектроніки;
Пелешку Д.Д. – доктору технічних наук, професору, проректору з науково- технічної роботи «IT Step University»;
Гожому О.П. – д.т.н., професору кафедри комп’ютерної інженерії Чорноморського національного університету імені Петра Могили.
Литвиненку В.І. – д.т.н., професору, завідувачу кафедри інформатики і комп’ютерних наук Херсонського технічного університету;
Литвину В.В. – д.т.н., професору, завідувачу кафедри інформаційних систем та мереж Національного університету «Львівська політехніка»;
Шароновій Н.В. – д.т.н., професору, завідувачу кафедри інтелектуальних комп’ютерних систем Національного технічного університету «ХПІ»;
Шаховській Н.Б. – д.т.н., професору, завідувачу кафедри систем штучного інтелекту Національного університету «Львівська політехніка»;
Кравцю П.О. – к.т.н., доценту кафедри інформаційних систем та мереж Національного університету «Львівська політехніка»;
Чируну Л.В. – к.т.н., доценту кафедри програмного забезпечення Львівського Національного університету імені Івана Франка;
Ришковцю Ю.В. – к.т.н., доценту кафедри інформаційних систем та мереж Національного університету «Львівська політехніка»;
Голощуку Р.О. – к.т.н., доценту кафедри соціальних комунікацій та інформаційної діяльності Інституту гуманітарних та соціальних наук Національного університету «Львівська політехніка».