Рекомендовано Міністерством освіти України
Київ 2000
ББК 65в6 Розповсюджувати та тиражувати
Є 41 без офіційного дозволу КНЕУ заборонено
Рецензенти:
Г. В. Лавінський, д-р техн. наук, проф. (УКРАНАЛІТ);
Т. О. Терещенко, канд. екон. наук, доц.
(Київ. нац. екон. ун-т)
Єжова Л. Ф.
Є 41Алгоритмізація і програмування процедур обробки інформації: Навч.-метод. посібник для самост. вивч. дисц. — К.: КНЕУ, 2000. — 152 с.
ІSBN 966–574–133–0
Курс «Алгоритмізація і програмування процедур обробки інформації» має на меті сформувати в студентів науково обґрунтовані погляди на сучасні технологічні процеси в інформаційній галузі. Навчально-методичний посібник допоможе студентам: ознайомитися з основними поняттями теорії алгоритмів, з найбільш поширеними алгоритмічними системами; засвоїти принципи організації алгоритмічних процесів та форми їхньої реалізації; ознайомитися з основними поняттями проектування автоматизованих комплексів задач; навчитися будувати базові алгоритми процесів пошуку, передавання, обробки інформації в різних інформаційних технологіях; навчитися здійснювати аналіз та контроль алгоритму на різних етапах життєвого циклу програмного продукту; ознайомитися з основними мовами опису алгоритмів, особливостями програмування, принципами організації та реалізації програм; складати супровідну проектну документацію.
Для студентів економічних вищих навчальних закладів і факультетів.
ББК 65в6
ІSBN 966–574–133–0 ã Л. Ф. Єжова, 2000
ã КНЕУ, 2000
Навчальне видання
ЄЖОВА Людмила Федорівна
Алгоритмізація
і програмування
процедур обробки
інформації
Навчально-методичний посібник
для самостійного вивчення дисципліни
Редактор Л. Мержвинська
Художник обкладинки О. Стеценко
Технічний редактор Т. Піхота
Коректор А. Невзгляд
Комп’ютерні верстка та графіка Т. Матвієнко
Комп’ютерний набір О. Іваненко, О. Бабич,
О. Баранівської, О. Костюк, Н. Коломієць
Підписано до друку 3.02.2000. Формат 60´84/16. Папір офсет. № 1.
Гарнітура Тип Таймс. Друк офсетний. Умовн. друк. арк. 8,84.
Умовн. фарбовідб. 8,95. Обл.-вид. арк. 10,53. Наклад 1500 прим. Зам. № 9-1738
Видавництво КНЕУ
03680, м. Київ, проспект Перемоги, 54/1
тел. (044) 458–00–66; тел./факс (044) 446–64–58
E-mail: publish@kneu.kiev.ua
ЗМІСТ
Вступ ........................................................................................... 3
Типова програма дисципліни
«Алгоритмізація і програмування
процедур обробки інформації»
Частина І...................................................................................... 5
навчально-методичне забезпечення................................. 6
Тема 1. Введення в теорію алгоритмів ...................................... 6
1.1. Методичні вказівки до вивчення теми .............................. 6
1.1.1. Визначення та властивості алгоритму ............................... 6
1.1.2. Алфавітні оператори ........................................................ 10
1.1.3. Характеристики алгоритму ............................................... 12
1.2. Практичне заняття............................................................. 13
1.3. Термінологічний словник ................................................. 13
1.4. Завдання для перевірки знань ........................................... 14
Тема 2. Форми та засоби представлення алгоритмів ................ 14
2.1. Методичні вказівки до вивчення теми .............................. 14
2.1.1. Словесна форма ................................................................ 15
2.1.2. Словесно-формульна форма .............................................. 15
2.1.3. Граф-схеми ...................................................................... 15
2.1.4. Блок-схеми ....................................................................... 16
2.1.5. Операторні схеми ............................................................. 17
2.1.6. HIPO-схеми ...................................................................... 18
2.1.7. Таблиці рішень ................................................................. 20
2.2. Термінологічний словник ................................................. 20
2.3. Практичні заняття ............................................................. 21
2.4. Задачі ............................................................................... 21
Тема 3. Алгоритмічні системи .................................................... 23
3.1. Методичні вказівки до самостійного вивчення теми ......... 23
3.1.1. Визначення алгоритмічної системи .................................. 23
3.1.2. Рекурсивні функції .......................................................... 24
3.1.3. Нормальні алгоритми Маркова ......................................... 26
3.1.4. Машини Поста ................................................................. 29
3.1.5. Машини Тьюринга ........................................................... 30
3.1.6. Абстрактні автомати ......................................................... 32
3.1.7. Формальні граматики ....................................................... 35
3.1.8. Алгоритмічні основи ЕОМ ............................................... 38
3.2. Термінологічний словник ................................................. 40
3.3. Навчальні завдання ........................................................... 41
3.4. Завдання для перевірки знань ........................................... 43
Тема 4. Класифікація задач
і процесів обробки інформації ........................................ 44
4.1. Методичні вказівки до самостійного вивчення теми ......... 44
4.2. Питання для перевірки знань ............................................ 48
Тема 5. Типи алгоритмічних процесів
та принципи їх побудови ................................................ 49
5.1. Методичні вказівки до вивчення теми .............................. 49
5.1.1. Лінійні алгоритми (5.1)..................................................... 49
5.1.2. Розгалужені алгоритми (5.2)............................................. 50
5.1.3. Прості циклічні процеси з параметром (5.5)...................... 55
5.1.4. Ітераційні циклічні процеси (5.6)...................................... 59
5.1.5. Складні циклічні процеси (5.7)......................................... 62
5.2. Термінологічний словник ................................................. 65
5.3. Плани практичних занять ................................................. 66
Заняття 1. Лінійні та розгалужені алгоритмічні процеси ............ 66
Заняття 2. Прості циклічні алгоритмічні процеси ....................... 69
Заняття 3. Алгоритмізація обробки одновимірних масивів ......... 72
Заняття 4. Алгоритмізація обробки двовимірних масивів ........... 76
Заняття 5. Ітераційні циклічні процеси ...................................... 79
5.4. Навчальні завдання ........................................................... 82
5.5. Завдання для перевірки знань ........................................... 85
Тема 6. Алгоритми обробки соціально-
економічної інформації .................................................. 88
6.1. Методичні вказівки до вивчення теми .............................. 88
6.1.1. Створення та контроль наборів даних (6.1)........................ 90
6.1.2. Коригування наборів даних (6.2)....................................... 96
6.1.3. Сортування наборів даних (6.3)......................................... 99
6.1.4. Розрахунки підсумків на основі окремого запису (6.4)...... 99
6.1.5. Розрахунки підсумків на основі всіх записів (6.5)............. 102
6.1.6. Розрахунки проміжних підсумків
на основі частини записів (6.6)......................................... 104
6.1.7. Обробка запитів з використанням довідників (6.7)............ 109
6.1.8. Розрахунки підсумків на основі багатьох запитів
з використанням декількох вхідних файлів (6.8)........................... 112
6.2. Плани практичних занять ................................................. 114
Заняття 1. Тема: «Робота з файлами. Створення
та ведення наборів даних» ........................................................... 114
Заняття 2. Тема: «Розрахунки підсумків на основі
окремих записів або всіх записів файла» ...................................... 116
Заняття 3. Тема: «Розрахунки підсумків
на основі частини записів» .......................................................... 117
Заняття 4. Тема: «Сумісне використовування декількох файлів» 119
6.3. Термінологічний словник ................................................. 121
6.4. Навчальні завдання ........................................................... 121
Тема 7. Визначення та короткий огляд
мов програмування ........................................................ 123
7.1. Методичні вказівки до самостійного вивчення теми ......... 123
7.1.1. Визначення мови програмування ..................................... 123
7.1.2. Вимоги до мов програмування ......................................... 124
7.1.3. Класифікація мов програмування та напрямки їх розвитку ...... 126
7.1.4. Питання стандартизації мов програмування та мобільності
програмних продуктів ................................................................ 129
7.1.5. Програмні інтерфейси та інструментальні засоби
розробки програмних продуктів ................................................. 130
7.2. Термінологічний словник ................................................. 132
7.3. Запитання для самоконтролю засвоєння теми .................... 132
Тема 8. Технологія програмування ............................................ 133
8.1. Методичні вказівки до самостійного вивчення теми ......... 133
8.1.1. Способи розробки програм ............................................... 133
8.1.2. Основні технологічні етапи розробки програм ................. 134
8.1.3. Формулювання вимог до предмета розробки
та формування специфікацій ....................................................... 134
8.1.4. Розробка проекту програми .............................................. 135
8.1.5. Написання програми ........................................................ 137
8.1.6. Налагодження програми ................................................... 138
8.1.7. Використання інтерактивних методів у розробці
та налагодженні програм ............................................................ 140
8.1.8. Супроводження програми ................................................ 142
8.2. Запитання для самоконтролю засвоєння теми .................... 145
Поточний та підсумковий контроль.......................................... 145
Література.................................................................................. 147
ВСТУП
Курс «Алгоритмізація і програмування процедур обробки
інформації» продовжує спеціальну підготовку студентів, він пов’язаний з курсами вищої математики, дискретного аналізу, обчислювальних машин, систем і мереж, моделей і структур даних та іншими.
Курс має на меті сформувати у студентів науково обґрунтовані погляди на сучасні технологічні процеси в інформаційній галузі, допомогти здобути теоретичні знання та виробити практичні навички з алгоритмізації та програмування цих процесів.
Поняття алгоритму є не тільки центральним поняттям теорії алгоритмів, не тільки одним із головних понять математики взагалі, але й одним із головних понять сучасної науки. Більш того, із вступом світового суспільства в еру інформатики алгоритми стають одним із найголовніших факторів цивілізації.
Прийняття рішень на будь-якому рівні управління об’єктами чи процесами у всіх галузях діяльності людини завжди складається з таких етапів:
— формування цілей;
— визначення основних властивостей очікуваних результатів;
— опис вхідної інформації;
— побудова алгоритму перетворення вхідної інформації у вихідну із заданими властивостями.
І якщо перші три етапи виконує фахівець відповідної галузі, четвертий етап виконує спеціаліст з обробки інформації.
Від того, які характеристики має інформація, як вона організована та зберігається, чи змінюється вона у часі, чи може змінюватись її структура і т.ін., залежить і процес її обробки і алгоритм цього процесу.
На сучасному рівні розвитку організації процесів управління практично відсутні окремі поодинокі задачі обробки інформації. Найчастіше це комплекси задач, пов’язаних між собою спільною інформаційною базою.
Невпинна автоматизація технологічного процесу розробки комплексів прикладних програм підтримки функціонування інформаційних систем, об’єктів управління іде шляхом перерозподілу робіт і функцій між фахівцями відповідної галузі, постановниками задач, проектувальниками систем, програмістами, користувачами та супровідниками програм.
Рівень інформатизації цих робіт і функцій (визначення й формального опису їх складових частин і взаємозв’язку між ними) зумовлює рівень автоматизації. І якщо раніше процес опису алгоритму на мові програмування та налагодження програми вважався найбільш творчим процесом і левова доля витрат часу припадала саме на нього, то тепер цей технологічний етап перетворився на суто технічний, майже рутинний.
Найбільшу увагу приділяють структурному опису даних, їх взаємозв’язку, напрямкам інформаційних потоків, алгоритмам зв’язку функцій обробки.
Курс «Алгоритмізація та програмування процедур обробки інформації» складається з двох розділів: «Основи алгоритмізації процедур обробки інформації» та «Технологія програмування з використанням інтегрованої системи TURBO-C».
У ході вивчення першого розділу перед студентами ставляться такі задачі:
— ознайомитися з основними поняттями теорії алгоритмів, з найбільш поширеними алгоритмічними системами;
— засвоїти принципи організації алгоритмічних процесів та форми їх представлення;
— ознайомитися з основними поняттями проектування автоматизованих комплексів задач;
— засвоїти базові алгоритми проектування процесів пошуку, передавання, обробки, організації інформації у різних інформаційних технологіях;
— навчитися проводити аналіз та контроль алгоритмів на різних технологічних етапах життєвого циклу програми;
— ознайомитися з основними мовами опису алгоритмів, особливостями програмування, принципами організації та реалізації програм;
— вміти складати супроводжувальну проектну документацію.
