Формалізація, алгоритмізація та програмування обчислювальних процесів

Наука вся -
лише море помилок,
де немає дна,
а правди немає й тіні

«Наука вся - лишь море заблуждений, где нету дна, а правды нет и тени»

 

«Складні проблеми завжди мають прості, легкі для розуміння невірні розв'язання» (закон Гросмана)

Формалізація алгоритму

А

лгоритм - послідовність формальних дій по перетворенню інформації,

виконання яких призводить до розв'язання поставленої задачі.

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

Абстрактним алфавітом [1] називається скінчена множина символів (це можуть бути літери якоїсь природної мови, цифри, спеціальні символи і т.і.), наприклад: A = {α, φ, γ, δ} або В = {β, λ, π, τ}.

Словом алфавіту називається скінчена упорядкована послідовність символів, наприклад: ai = αγφ або bj = πλβ. Порожнє слово не містить символів алфавіту. Кількість символів у слові називається довжиною слова. Слово bi називається підсловом слова ai, якщо ai = bic, де c - будь-яке слово (у тому числі і порожнє).

Оператором (відображенням) алфавіту називається функція, що задає відповідність між одними словами алфавіту («вхідного») і іншими словами цього ж або іншого алфавіту («вихідного»). Кажуть, що оператор Гai=bj переробляє слово ai вхідного алфавіту A у слово bj вихідного алфавіту В. Однозначним оператором алфавіту називається оператор, який кожне слово вхідного алфавіту відображає в єдине слово вихідного алфавіту. Якщо не існує відображення деякого слова ai вхідного алфавіту в слово bj вихідного алфавіту, то кажуть, що оператор на слові ai не визначено. Сукупність слів, на яких оператор визначено, називають його областю визначення.

Кодуючим оператором Гai=bj називають відображення кожного символу вхідного алфавіту у слово («код») вихідного алфавіту. Нехай, наприклад, для алфавітів А і В визначено кодуючі оператори: Гα=βλτ, Гφ=λπ, Гγ=τλ, Гδ=βτ. Тоді слово «αφγ» алфавіту А відображається у код «βλτλπτλ» алфавіту В. Процес, зворотний кодуванню, називається декодуванням і позначається Г-1 bj=ai. Наприклад, для слова «βττλβτλ» алфавіту В декодування дає слово «δγα» алфавіту А.

Якщо оператор Гai=bj дає слово bj, а сполучений оператор Г-1 bj=ai дає слово ai, то кажуть, що кодуючі оператори взаємно однозначні і має місце зворотність кодування. Проте не всі операції кодування зворотні. Нехай, наприклад, для алфавітів А и В визначено кодуючі оператори: Гα=β, Гφ=λ, Гγ=βλ, Гδ=βτ. Тоді кодування слова «αφγ» алфавіту А дасть код «βλβλ» алфавіту В, але декодування дає неоднозначні варіанти слів: «γγ», «αφγ», «γαφ» алфавіту А.

Таким чином, для зворотності кодування повинні виконуватися умови:

Œ коди різних символів вхідного алфавіту повинні бути різними;

 код будь-якого символу вхідного алфавіту не може збігатися з жодним із підслів кодів інших символів цього ж алфавіту.

Кодування, при якому всі коди мають однакову довжину, називається нормальним кодуванням.

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

Важливим теоретичним аспектом формалізації операторів алфавіту є засоби іх задання. У тому випадку, коли область визначення оператора алфавіту є скінченою, то оператор може бути задано таблицею відповідності з колонками «вхідне слово» і «вихідне слово». Якщо ж область визначення оператора алфавіту є нескінченою, то оператор задається системою правил, яка дозволяє за скінчену кількість кроків знайти в області визначення оператора вихідне слово, відповідне заданому вхідному слову.

Проте, між операторами алфавіту і алгоритмами існує суттєва різниця, яка полягає у тому, що:

- в операторі алфавіту суттєвою є лише відповідність між словами вхідного і вихідного алфавітів, а не засіб встановлення цієї відповідності;

- в алгоритмі ж, навпаки, суттєвим є засіб задання відповідності між словами вхідного і вихідного алфавітів.

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

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

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

А

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

Алгоритм, відповідно до якого розв'язання поставленої задачі зводиться до логічних дій, називається логічним алгоритмом. Прикладом логічного алгоритму є алгоритм пошуку мінімального елемента множини.

Будь-який алгоритм повинен мати властивість дискретності у часі перетворення даних, тобто він повинен являти собою послідовність «кроків», кожний із який в окремі моменти часу виконує дії, спрямовані на досягнення поставленої мети.

Алгоритм може мати такі властивості:

Ø детермінованість, тобто повторна відтворюваність результатів для однакових вхідних даних (за звичай у теорії алгоритмів розглядаються лише алгоритми з однозначними операторами алфавіту; такі алгоритми називають детермінованими);

Ø масовість, тобто можливість застосування алгоритму для однотипних вхідних даних; алгоритм повинен перетворювати абстрактні дані, а не константи (мало коштує алгоритм, що тільки і «вміє», що підраховувати суму «2+2»; він повинен «уміти» підраховувати суму у загальному вигляді, тобто «a+b»);

Ø результативність, тобто одержання результатів за скінчену кількість «кроків». Для складання «кубика Рубіка», наприклад, методом простого перебору варіантів навіть на швидкодіючому комп'ютері потрібно декілька тисяч років(!), проте відомі алгоритми досягнення того ж результату за лічені секунди. Із властивості результативності випливає поняття області придатності алгоритму, тобто множини вхідних даних, для яких алгоритм є результативним;

Ø збіжність, тобто можливість досягнення наперед заданої точності розрахунку.

У загальному випадку ще розрізняють випадкові й адаптивні алгоритми.

Алгоритм називається випадковим, якщо які-небудь його «кроки» передбачають можливість випадкового вибору можливих дій. Прикладами випадкових алгоритмів можуть служити алгоритми деяких ігор - «гадалок». Алгоритм називається адаптивним, якщо він змінює склад «кроків» та (або) методи переробки інформації. Результат роботи адаптивного алгоритму залежить не тільки від вхідних даних, але і від передісторії роботи алгоритму.

«Ускладнювати просто. Спрощувати складно»   (закон Мейера)

 

Алгоритмічні системи

У

теорії алгоритмів значна увага приділяється засобам задання алгоритмів, що називаються алгоритмічними системами. Алгоритмічна система характеризується універсальністю, тобто дозволяє задати алгоритм, еквівалентний будь-якому наперед заданому алгоритму. При описуванні алгоритмічних систем використовуються спеціальні формалізовані засоби прикладної теорії алгоритмів, що можна розділити на два напрямки: «алгебраїчна теорія алгоритмів» і «геометрична теорія алгоритмів».

«Алгебраїчна теорія алгоритмів» розглядає алгоритми як лінійні тексти. До цього напрямку відносять теорії рекурсивних функцій, машини Тюрінга, операторні системи Ван-Хао і Ляпунова, логічні схеми алгоритмів Янова та ін.

«Геометрична теорія алгоритмів» розглядає алгоритми як множини, між якими вводяться зв'язки, що носять характер відображень або бінарних відношень. При цьому значне місце займає геометрична інтепретація об'єктів у вигляді графів, вершини яких задають елементи множини, а ребра - відношення між ними. При цієї інтепретації відображення задаються у вигляді розмітки вершин або ребер графа. До цього напрямку відносяться: представлення нормальних алгоритмів Маркова у вигляді граф-схем, запропонованих Калужиним, блок-схемний метод алгоритмізації та ін.

 

Р

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

Поняття рекурсивних функцій тісно пов’язане із поняттям обчислюємих функцій. Чисельні функції, значення яких можна розрахувати за допомогою алгоритму, називають обчислюємими функціями.

Якщо деяким елементам множини Х поставлені в однозначну відповідність елементи множини Y, то кажуть, що задано частково визначену функцію Y(Х); при цьому сукупність елементів X називають областю визначення функції Y, а сукупність елементів Y - областю значень функції Y. Якщо область визначення функції Y(Х) збігається із множиною X, то функцію називають усюди визначеною.

Гьодель вперше описав клас рекурсивних функцій як клас усіх числових функцій деякої формальної системи. Виходячи з інших передумов, Чорч у 1936 році вивів той же клас числових функцій і сформулював гіпотезу про те, що «клас рекурсивних функцій тотожний класу усюди визначених обчислюємих функцій».Оскільки поняття обчислюємої функції точно не визначається, то і гіпотезу Чорча довести не можна.

Кліні ввів поняття частково рекурсивної функції і висловив гіпотезу про те, що «усі частково визначені функції, які можна обчислити за допомогою алгоритмів, є в той же час і частково рекурсивними». Ця гіпотеза також відома, як і гіпотеза Чорча. Проте математичні дослідження останніх 30 років виявили повну доцільність вважати поняття частково рекурсивної функції науковим еквівалентом поняття обчислюємої частково визначеної функції.

Надалі під тезою Чорча будемо розуміти гіпотезу Чорча у тому розширеному вигляді, що був доданий до неї Кліні: «Функція є рекурсивною, якщо вона є обчислюємою». У силу тези Чорча питання про обчислюваність функції різвнозначне питанню про її рекурсивність; при цьому математичними методами можна довести алгоритмічну нерозв'язність деякої задачі, якщо функція, що розв’язує задачу, не рекурсивна.

Застосування рекурсивних функцій у теорії алгоритмів базується на ідеї Канторової нумерації слів у довільному алфавіті послідовними натуральними числами. Найпростіше таку нумерацію можна здійснити розташуванням слів у порядку зростання їхніх довжин, а слів, що мають однакову довжину, - у лексикографічному порядку. Після нумерації вхідних і вихідних слів у довільному операторі алфавіту цей оператор перетворюється у функцію Y = f (X), де і аргумент, і функція приймають ненегативні цілочисельні значення (функція f (X) може бути частково визначеною). Такі функції називаються арифметичними.

Елементарними арифметичними функціями виявляються:

Œ функції, тотожно рівні нулю:

On (x1, x2,..., xn) = 0 (" xi ³ 0)

 тотожні функції, що повторюють значення своїх аргументів:

Iin (x1, x2,..., xn) =xi (i Î [1;n]; n=1, 2,...)

Ž функції безпосереднього слідування:

S1(x) = x + 1

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

Прийом суперпозиції полягає у підстановці одних арифметичних функцій замість аргументів інших арифметичних функцій.

Нехай, наприклад, задано {fi (x1, x2,..., xm)}n (iÎ[1;n]) і f (x1, x2,..., xn). Тоді суперпозиція дасть нову функцію g (x1, x2,..., xm) = f (f1 (x1, x2,..., xm),..., fn(x1, x2,..., xm)).

Для конкретного прикладу: якщо задані функції f(x) = 0 і g(x) = x + 1, то: h(x) = g(f(x)) = 0 + 1 = 1.

Суперпозиція позначається як Sn+1, де n+1 - кількість функцій.

Прийом примітивної рекурсії дозволяє будувати функцію f від n+1 аргументу по двох вхідних функціях: функції g від n аргументів і функції h від n+2 аргументів, якщо:

 

f (x1, x2,..., xn, 0) = g (x1, x2,..., xn);

f (x1, x2,..., xn, y + 1) = h (x1, x2,..., xn, y, f (x1, x2,..., xn, y)).

 

Це означає, що значення f (x1, x2,..., xn, m+1) можна розрахувати за допомогою ітераційної рекурсивної процедури:

b0 = g (x1, x2,..., xn)

b1 = h (x1, x2,..., xn, 0, b0)

b2 = h (x1, x2,..., xn, 1, b1)

....................................................

bm+1= h (x1, x2,..., xn, m, bm)

===========================

f (x1, x2,..., xn, m+1) = bm+1

Прийом найменшого кореня дозволяє визначити нову арифметичну функцію f (x1, x2,..., xn) від n аргументів за допомогою раніше побудованої арифметичної функції g (x1, x2,..., xn, y) від n+1 аргументів.

Для будь-якого заданого набору значень змінних x1 = a1,..., xn= an у якості значення f (a1, a2,..., an) обумовленої функції приймається найменший цілий ненегативний корінь у = а рівняння g (x1, x2,..., xn, y) = 0. У випадку неіснування цілих ненегативних коренів цього рівняння функція f(x1, x2,..., xn) вважається невизначеною на відповіднім наборі значень змінних.

Арифметичні функції, що можуть бути побудовані з елементарних арифметичних функцій за допомогою конструктивних прийомів суперпозиції, примітивної рекурсії і найменшого кореня, називають частково рекурсивними функціями. Якщо такі функції до того ж усюди визначено, то вони називаються загальнорекурсивними функціями.

Практично поняття частково рекурсивних функцій використовується для доказу алгоритмічної можливості (або неможливості) розв'язання задач. Використання ж таких функцій для утворення конкретного алгоритму є практично недоцільним через складність процесу алгоритмізації.

Блок-схемний метод алгоримізації передбачає розподіл усього обчислювального процесу на окремі кроки, які позначаються графічними зображеннями - «блоками». Блок-схемою алгоритму називається стандартизоване (див. ГОСТ 19.701-90) графічне зображення алгоритму, кожному кроку якого відповідає блок. Звичайне співвідношення розмірів сторін блоку таке, що його довжина становить дві його висоти. Усі блоки, окрім блоків «Початок» і «Кінець», нумерують по струмах зверху-донизу і зліва-направо арабськими цифрами; номер ставлять ліворуч над блоком чи у розриві верхньої лініі блоку.

У блок-схемі може бути присутнім тільки один блок «Початок», з якого починається абиякий алгоритм, і не менше одного блока-термінатора «Кінець», яким завершується виконання алгоритму:

 

Блоки «Введення» і «Виведення» використовуються для введення значень даних, список ідентифікаторів яких вони містять усередині, із зовнішніх пристроїв (клавіатури, файлу на дисці і т.і.) або виведення значень розрахункових даних на зовнішні пристрої (монітор, принтер, файл на дисці і т.і.):

 

Блок «Процес» (див. подальший малюнок, ліворуч) використовується для обчислення даних за формулою, яку записано усередині блоку. Блок «Визначений процес» (див. подальший малюнок, праворуч) використовується для виклику на виконання підпорядкованого алгоритму:

 

 

Блок «Рішення» містить усередині умову, яка піддається сумніву; цей блок застосовується для організації розгалужень алгоритму.

 

 

Блок «Межа циклу» (типу «початок циклу» - ліворуч, типу «кінець циклу» - праворуч) застосовується для організації й обмеження циклів. Ініціююче значення параметру циклу (наприклад, X = Xn), його кінцеве значення (Xk), крок збільшення чи зменшення (DX), або умова завершення циклу (X £ Xk) записуються усередині початкового чи кінцевого блоку у залежності від типу циклу:

 

 

Блок «Модифікація» застосовується для організації ітераційного циклу з передумовою і параметром, що змінюється з деяким кроком. Ініціююче значення, кінцеве значення і крок збільшення чи зменшення параметру циклу записують усередині блоку. Наприклад, запис X=Xn;Xk;DX позначає зміну параметру X від початкового значення Xn до кінцевого значення Xk із кроком DX:

 

 

Блоки у блок-схемі, як правило, мають один горизонтальний розмір, можуть викреслюватися у будь-якій орієнтації і з'єднуються лініями потоку. Ці лінії повинні бути спрямовані до центру блоку і, за звичай, підходять до нього зверху або ліворуч, а виходиять з нього знизу або праворуч. Лінії потоку закінчуються стрілкою, якщо блоки, що з'єднуються, виконуються у напрямках «ліворуч» чи «нагору», або ж лінія потоку перетерплює злам. Декілька ліній потоку можуть з'єднуватися в одну, причому місце з'єднання звичайно зсовується:

ТЕМА 8