- •Алгоритмізація і програмування процедур обробки інформації Навчально-методичний посібник для самостійного вивчення дисципліни Рекомендовано Міністерством освіти України
- •Алгоритмізація і програмування процедур обробки інформації Навчально-методичний посібник для самостійного вивчення дисципліни
- •Тема 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. Запитання для самоконтролю засвоєння теми
3.1.7. Формальні граматики
У формальних граматиках ланцюги символів інтерпретуються як мовні об’єкти різних рівнів: словоформи, словосполучення, фрази.
Словоформа складається з ланцюга морфем. Морфема — найменша граматична частина слова (префікс, корінь, суфікс, закінчення).
Граматична мова — скінченна множина правил побудови об’єктів, їх аналізу та перетворень. Теорія формальних граматик сформульована у 50-ті роки американським лінгвістом М. Хомським, хоча основи, на яких вони базуються, були винайдені значно раніше. У теорії алгоритмів це системи, що знаходяться між скінченними абстрактними автоматами та нескінченними машинами Тьюринга.
Хоча спочатку вони призначалися для вирішення суто лінгвістичних проблем природних мов, з’ясувалося, що формальні граматики ще більш пристосовані до алгоритмічних мов, які простіші за структурою, легше формалізуються, ніж природні мови.
Отже, формальні граматики являють собою клас алгоритмічних систем, що відрізняється від усіх інших.
Кожна граматика — це впорядкована четвірка символів G={VT,VH,P,S}, де VT та VH — відповідно термінальний та нетермінальний словники.
Термінальний словник — сукупність елементів, з яких будуються ланцюжки, породжувальні граматикою, так би мовити, предметна область граматики G (термінальні символи).
Нетермінальний словник — сукупність символів, якими позначено класи або ланцюжки вхідних елементів, тобто словник синтаксичних типів граматики (нетермінальні символи).
V = VT U VH — словник граматики G, VT VH = .
У процесі перетворення ланцюжок може містити термінальні та нетермінальні символи одночасно.
S — початковий, виділений нетермінальний символ, що означає клас усіх мовних об’єктів, для опису яких призначена граматика. Символ S називають метою граматики.
P — правила підстановок граматики G: à , де ланцюжок має хоч б один символ VH .
Множина ланцюжків, що виводяться в граматиці G, є мова, породжена цією граматикою, і позначається L(G). До L(G) належать всі ланцюжки, що складені з термінальних символів.
Синтаксис мови — правила побудови речень у мові, або правила побудови конструкцій мови.
Семантика — тлумачення або пояснення цих конструкцій, тобто правила використання синтаксису, або правила надання мовній конструкції певного смислу.
Вимоги до граматики:
1) приписування кожному реченню мови його структурного опису (з яких елементів побудовано речення, який порядок їх розміщення);
2) граматика повинна бути скінченною.
Звичайні граматики природних мов задають множину правил побудови речень, формальні граматики — деякий спосіб вивчати та описувати множину правил.
Різниця між формальною граматикою та граматикою природної мови полягає в тому, що у формальній граматиці G всі твердження формулюються у термінах невеликої кількості чітко визначених елементарних символів та операцій, причому нема ніяких виключень із правил.
Будь-який ланцюжок символів, побудований за правилами синтаксису формальної граматики, є правильним і має певний єдиний смисл, визначений семантичними правилами.
Класифікація формальних граматик.
Розрізняють розпізнавальні, породжувальні та перетворювальні формальні граматики, контекстовільні та контекстозалежні і т.д.
Розпізнавальна граматика — якщо для будь-якого ланцюжка символів вона може вирішити, чи є він правильним чи ні, і якщо так, то як він побудований.
Породжувальна граматика — якщо вона може побудувати будь-який правильний ланцюжок символів, даючи вказівки щодо його побудови, і не будує жодного неправильного ланцюжка.
Перетворювальна граматика — якщо для будь-якого правильно побудованого ланцюжка вона вміє побудувати відображення у вигляді знов-таки правильного ланцюжка, задаючи вказівки щодо порядку проведення відображень.
Контекстовільні граматики: правила підстановок застосовуються до ланцюжків символів (до окремих сполучень символів, до окремих символів) незалежно від тих символів, які їх оточують (від контексту), і при виконанні підстановок цей контекст залишається без змін.
Контекстозалежні граматики: до ланцюжків символів застосовуються різні правила підстановок залежно від їх контексту. Наприклад, при перекладі текстів з однієї мови спілкування на іншу використовуються правила контекстозалежних граматик, бо одному й тому самому слову у різних контекстах будуть ставитись у відповідність різні слова іншої мови. Водночас мови програмування побудовано за правилами контекстовільних граматик, і кожна конструкція такої мови завжди має один і той самий зміст, смисл і тлумачення, тому при перекладі (трансляції) на будь-яку іншу мову програмування та мову комп’ютерних команд (ЕХЕ-модулі), в першу чергу за правилами перетворювальних граматик можна отримати тільки один варіант вихідного тексту, з одним ланцюжком символів вхідного тексту, незалежно від контексту, зіставити один і той самий вихідний ланцюжок.
Дві граматики називають слабо еквівалентними, якщо вони породжують одну й ту саму мову, тобто одну й ту саму множину термінальних ланцюжків.
Дві граматики називають сильно еквівалентними, якщо вони породжують одну й ту саму мову та однаковим ланцюжком приписують однакові виводи (однакові алгоритми).
Формальні граматики є складовою частиною науки, що відокремилась від теорії алгоритмів, — математичної лінгвістики, яка вив-чає природні мови, їх розвиток та вживання за допомогою законів математики, а також є основою створення мов програмування.
Наведемо приклад формальної породжувальної граматики, за правилами якої будуються речення певної конструкції.
Нехай маємо граматику
G = {VT, VH, P, S},
де VH = {S, B, C, D, E, F, K} — нетермінальний словник, символи якого означають:
S — речення (виділений символ);
B — група підмета;
C — група присудка;
D — іменник;
E — прикметник;
F — дієслово;
K — прислівник.
Термінальний словник
VT = {a, b, c, d, e, f, i, j, k, e, m, n, p, r, t}, символи якого означають:
а — пес в — сніг с — малюк d — комар |
е — білий f — пухнастий i — веселий j — бігає |
к — кусає е — стрибає m — сміється n — падає |
p — швидко r — голосно t — тихенько |
Правила підстановок:
P = {SàBC, BàED, CàKF, Eàe, Eàf, Eài, Dàa, Dàb,
Dàc, Dàd, Kàp, Kàr, Kàt, Fàj, Fàk, Fàl, Fàm,Fàn}.
Таку граматику можна представити у вигляді графа (рис. 3.5):
Рис. 3.5. Граф
породжувальної граматики
— веселий пес швидко бігає;
— білий сніг тихенько падає;
— пухнастий комар голосно сміється
та багато інших. З точки зору породжувальної граматики всі ці речення є правильними, тобто побудованими за правилами синтаксису даної граматики. Інша справа, що останнє речення не має смислу в український мові, отже, не належить їй, тільки у формальних мовах існує взаємнооднозначна відповідність між породженими текстами (ланцюжками) та смислами.