1.3. Термінологічний словник

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

Абстрактний алфавіт — скінченна сукупність об’єктів довільної природи, які називають символами алфавіту.

Слово — будь-яка скінченна впорядкована послідовність символів абстрактного алфавіту.

Алфавітний оператор (відображення) — відповідність між словами в одному чи різних алфавітах.

Властивості алфавіту:

— детермінованість — однозначна визначеність результату кожної операції, не залежна від виконавця;

— дискретність — розчленованість алгоритму на окремі операції;

— масовість — можливість застосування до будь-яких вхідних даних задач виділеного класу;

— результативність — скінченність процесу перетворення інформації.

1.4. Завдання для перевірки знань

1. Визначення алгоритму.

2. Основні властивості алгоритму.

3. Область завдання алгоритму.

4. Алгоритмічна розв’язність проблеми.

5. Визначення абстрактного алфавіту.

6. Слово в абстрактному алфавіті.

7. Визначення алфавітного оператора.

8. Типи відображень в абстрактних алфавітах.

9. Кодуючі відображення.

10. Спряжені оператори.

11. Взаємозв’язок між алгоритмом та алфавітним оператором.

12. Поняття еквівалентності алгоритмів та алфавітних операторів.

Тема 2. Форми та засоби представлення алгоритмів

2.1. Методичні вказівки до вивчення теми

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

Розглянемо на прикладі однієї задачі різні форми представлення алгоритму її розв’язання.

Задача. Дано два вектори А = (а₁, а₂, ..., а_n), та В = (b₁, b₂, ..., b_n). Знайти вектор С, елементи якого обчислюються за формулою с_i = а_i + b_i.

2.1.1. Словесна форма

Словесний опис — це найстаріша форма представлення алгоритму. В ньому формальні правила перетворення інформації формулюються, нумеруються та вказується послідовність їх виконання. Така форма є прийнятною для досить простих або, навпаки, складних задач, розв’язання яких можна скласти з готових блоків (процедур обробки інформації), а за допомогою словесного опису вказати порядок їх виклику. Згадайте: алгоритми Евкліда були представлені саме у цій формі.

Розв’язання:

1. Покладемо i дорівнює 1 та перейдемо до наступного правила.

2. Покладемо с_i дорівнює а_i + b_i та перейдемо до наступного правила.

3. Перевіримо, чи i дорівнює n. Якщо так, то обчислення припиняємо. Якщо ні, то збільшуємо i на 1 та перейдемо до правила 2.

2.1.2. Словесно-формульна форма

Це форма, яка використовує загальноприйняті математичні позначення, коментарі до них, що пояснюють дії та їх послідовність, яка визначається за допомогою міток.

Розв’язання:

Для визначення порядку введемо мітки Q₁, Q₂, ..., якщо не вказано, до якої мітки переходити, то це перехід до наступної дії.

i = 1

Q₁ : c_i = а_i + b_{i .}

Якщо i = n, то перейти до Q₃ , інакше — до Q₂.

Q₂ : i = i + 1. Перейти до Q₁.

Q₃ : Закінчити обчислювання.