- •Алгоритмізація і програмування процедур обробки інформації Навчально-методичний посібник для самостійного вивчення дисципліни Рекомендовано Міністерством освіти України
- •Алгоритмізація і програмування процедур обробки інформації Навчально-методичний посібник для самостійного вивчення дисципліни
- •Тема 1. Введення в теорію алгоритмів 6
- •Тема 2. Форми та засоби представлення алгоритмів 14
- •Тема 3. Алгоритмічні системи 23
- •Тема 4. Класифікація задач і процесів обробки інформації 44
- •Тема 5. Типи алгоритмічних процесів та принципи їх побудови 49
- •Тема 6. Алгоритми обробки соціально- економічної інформації 88
- •Тема 7. Визначення та короткий огляд мов програмування 123
- •Тема 8. Технологія програмування 133
- •Типова програма
- •Дисципліни «Алгоритмізація і програмування
- •Процедур обробки інформації»
- •Частина і
- •Тема 4. Класифікація задач і процесів обробки інформації
- •Тема 5. Типи алгоритмічних процесів та принципи їх побудови
- •Тема 6. Алгоритми обробки соціально-економічної інформації
- •Тема 7. Визначення та короткий огляд мов програмування
- •Тема 8. Технологія програмування
- •Навчально-методичне забезпечення
- •1.1. Методичні вказівки до вивчення теми
- •1.1.1. Визначення та властивості алгоритму
- •1.1.2. Алфавітні оператори
- •1.1.3. Характеристики алгоритму
- •1.2. Практичне заняття
- •1.3. Термінологічний словник
- •1.4. Завдання для перевірки знань
- •Тема 2. Форми та засоби представлення алгоритмів
- •2.1.1. Словесна форма
- •2.1.2. Словесно-формульна форма
- •2.1.3. Граф-схеми
- •2.1.4. Блок-схеми
- •2.1.5. Операторні схеми
- •2.1.6. Ніро-схеми
- •2.1.7. Таблиці рішень
- •2.2. Термінологічний словник
- •2.3. Практичні заняття
- •2.4. Задачі
- •3.1. Методичні вказівки до самостійного вивчення теми
- •3.1.1. Визначення алгоритмічної системи
- •3.1.2. Рекурсивні функції
- •3.1.3. Нормальні алгоритми Маркова
- •3.1.4. Машини Поста
- •3.1.5. Машини Тьюринга
- •3.1.6. Абстрактні автомати
- •3.1.7. Формальні граматики
- •3.1.8. Алгоритмічні основи еом
- •3.2. Термінологічний словник
- •3.3. Навчальні завдання
- •3.4. Завдання для перевірки знань
- •Тема 4. Класифікація задач і процесів обробки інформації
- •4.1. Методичні вказівки до самостійного вивчення теми
- •Науково-технічні задачі
- •Задачі обробки спискових структур
- •Задачі обробки символьної інформації
- •Інформаційно-пошукові задачі
- •Задачі моделювання та ділові ігри
- •Економічні задачі
- •4.2. Питання для перевірки знань
- •Тема 5. Типи алгоритмічних процесів та принципи їх побудови
- •5.1. Методичні вказівки до вивчення теми
- •5.1.1. Лінійні алгоритми (5.1)
- •5.1.2. Розгалужені алгоритми (5.2)
- •5.1.3. Прості циклічні процеси з параметром (5.5)
- •5.1.4. Ітераційні циклічні процеси ( 5.6 )
- •5.1.5. Складні циклічні процеси (5.7)
- •5.2. Термінологічний словник
- •5.3. Плани практичних занять
- •Запитання для перевірки знань
- •Запитання для перевірки знань
- •Приклади задач
- •Запитання для перевірки знань
- •Приклади задач
- •Запитання для перевірки знань
- •Приклади задач
- •Запитання для перевірки знань
- •5.4. Навчальні завдання Завдання до 1-го заняття
- •Завдання до 2-го заняття
- •Завдання до 3-го заняття
- •Завдання до 4-го заняття
- •Завдання до 5-го заняття
- •5.5. Завдання для перевірки знань
- •Тема 6. Алгоритми обробки соціально-економічної інформації
- •6.1. Методичні вказівки до вивчення теми
- •6.1.1. Створення та контроль наборів даних (6.1)
- •6.1.2. Коригування наборів даних (6.2)
- •6.1.3. Сортування наборів даних (6.3)
- •6.1.4. Розрахунки підсумків на основі окремого запису (6.4)
- •Список працюючих жінок
- •6.1.5. Розрахунки підсумків на основі всіх записів (6.5)
- •Про середню заробітну плату
- •6.1.6. Розрахунки проміжних підсумків на основі частини записів (6.6)
- •6.1.7. Обробка запитів з використанням довідників (6.7)
- •Список підприємств
- •6.1.8. Розрахунки підсумків на основі багатьох запитів з використанням декількох вхідних файлів (6.8)
- •6.2. Плани практичних занять Заняття 1.
- •Заняття 2
- •Запитання для перевірки знань
- •Наявна кількість матеріалу____________
- •Запитання для перевірки знань:
- •Поділ працівників за статтю
- •Поділ працівників за неперервним стажем роботи
- •Поділ заробітної плати за розрядами робіт
- •Списки робітників, молодших за 20 років
- •Запитання для перевірки знань:
- •Список підприємств, що замовили
- •Перелік матеріалів
- •Справка про попит / пропозицію на
- •Сума затрат на матеріали
- •Результат обліку матеріалів на складах
- •Перелік матеріалів на складах
- •6.3. Термінологічний словник
- •6.4. Навчальні завдання
- •Тема 7. Визначення та короткий огляд мов програмування
- •7.1. Методичні вказівки до самостійного вивчення теми
- •7.1.1. Визначення мови програмування
- •7.1.2. Вимоги до мов програмування
- •7.1.5. Програмні інтерфейси та інструментальні засоби розробки програмних продуктів
- •7.2. Термінологічний словник
- •7.3. Запитання для самоконтролю засвоєння теми
- •Тема 8. Технологія програмування
- •8.1. Методичні вказівки до самостійного вивчення теми
- •8.1.1. Способи розробки програм
- •8.1.2. Основні технологічні етапи розробки програм
- •8.1.4. Розробка проекту програми
- •8.1.5. Написання програми
- •8.1.6. Налагодження програми
- •8.1.8. Супроводження програми
- •8.2. Запитання для самоконтролю засвоєння теми
1.1.3. Характеристики алгоритму
З поняттям алгоритму пов’язані такі поняття, як область його завдання, складність, еквівалентність, алгоритмічна розв’язність та ін.
Область завдання алгоритму — це множина даних, до яких алгоритм застосовний. Якщо алгоритм припиняється без результату або продовжується необмежено довго, то говорять про незастосовність алгоритму до цих вхідних даних.
Складність алгоритму — це величина, яка характеризує довжину опису алгоритму. А для оцінки складності обчислень, що виконуються в даному алгоритмі, використовується так звана сигналізуюча функція.
Під алгоритмічною розв’язністю масової проблеми розуміють можливість побудови алгоритму розв’язку всіх задач даного класу.
Існують класи задач, для розв’язання яких не існує одного універсального способу. Це алгоритмічно нерозв’язувані проблеми. Це не означає, що неможливо розв’язати окремі задачі даного класу. В кожному окремому випадку суттєво використовуються особливості вхідних даних, тобто порушується властивість масовості алгоритму. Для визначення алгоритмічного розв’язку якогось класу задач необхідно або побудувати алгоритм розв’язку, або довести неможливість побудови такого алгоритму, тобто довести, що проблема є алгоритмічно нерозв’язуваною.
Наприклад, алгоритмічно розв’язна проблема — доведення тотожностей в алгебрі (відомі правила перетворення алгебраїчних виразів), у той самий час розв’язання диференційних рівнянь — проблема алгоритмічно нерозв’язна. Є проблеми, про які невідомо, чи є вони алгоритмічно розв’язні чи нерозв’язні. Це свідчить про те, що на даний час вчені не в змозі побудувати алгоритм або довести неможливість його побудови, бо то є задачі одного рівня складності.
У практиці, однак, найчастіше буває так, що для будь-якого класу задач, для якого доведена неможливість існування алгоритму, який розв’язує всі задачі цього класу, завжди можна побудувати алгоритм, що розв’язує майже всі такі задачі. Термін «майже всі» використано в тому розумінні, що ймовірність зустріти на практиці конкретну задачу розглядуваного класу, що не розв’язується за допомогою побудованого алгоритму, достатньо мала.
1.2. Практичне заняття
Засвоєння основних понять теми:
1. Поняття алгоритму.
2. Основні властивості алгоритму.
3. Поняття припустимої операції та як воно пов’язане з типом даних.
4. Еквівалентність алгоритмів.
5. Алгоритмічна розв’язність проблеми.
6. Абстрактні алфавіти.
7. Загальний спосіб представлення інформації.
8. Алфавітний оператор (відображення) як узагальнена операція перетворення інформації.
9. Типи алфавітних операторів.
10. Зв’язок між алфавітним оператором та алгоритмом.
11. Область завдання алгоритму.
12. Які алгоритмічно розв’язні чи нерозв’язні проблеми відомі на даний час?
13. Як розв’язуються алгоритмічно нерозв’язні проблеми?
14. Які існують відображення?
15. Які відображення найбільш використовувані?
16. Поняття спряжених операторів, його використання.
17. Системи кодування, що застосовуються в ЕОМ.
18. Алфавітні проблеми, проблеми кодування та обробки інформації у різних алфавітах.
19. Еквівалентність алфавітних операторів.