Визначення алгоритму Основні поняття теорії алгоритмів

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

Поки не буде побудована в уяві або на папері чітка послідовність дій у процесі розв’язання будь-якої задачі, не можна правильно описати відповідний процес на мові програмування, тобто написати програму для виконання її на ЕОМ. Значення цього твердження зростає разом із підвищенням складності задач.

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

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

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

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

Алфавіт, як і будь-яка інша множина, може бути заданий перерахуванням його елементів. Наприклад, алфавітом A є множина A={a, bc}, алфавітом B - множина B={x, y}.

Під словом в абстрактному алфавіті розуміють будь-яку скінченну впорядковану послідовність його символів. У послідовності (ланцюжку) між символами стоїть операція зчеплення або конкатенації¹, тобто міняти місцями символи в послідовності не можна. Наприклад, в алфавіті A словами є будь-які послідовності: aac cbacb bb, а в алфавіті B: x, y, yx, xx і т. ін.

Кількість символів у слові називають довжиною цього слова. Розрізняють також порожні слова, що не містять жодного символу.

Слово p називається підсловом слова q, якщо слово q можна представити у вигляді q = pr, де r - будь-яке слово, в тому числі і порожнє. Очевидно, що таке поняття слова відрізняється від аналогічного в розмовних мовах. Тут під словом можна розуміти будь-яку послідовність символів, навіть безглузду.

При розширенні алфавіту поняття слова може істотно змінюватися. Так, наприклад, в алфавіті A={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ланцюжок символів 69+73 представляє собою два слова, сполучені знаком суми, а в алфавіті В={+, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}- це буде одне слово. Поповнюючи російський алфавіт знаками пунктуації та знаком пробілу (порожнім місцем, залишеним між сусідніми словами), можна при бажанні цілі фрази, абзаци і навіть цілі книги розглядати як окремі слова.

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

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

Нехай задані слова в алфавітах X і Y, а також відповідності між цими словами. Якщо x_i – слово в алфавіті X, а y_j – слово в алфавіті Y, то алфавітний оператор F(x_i) = y_j (або Гx_i=y_j , де символ Г означає відображення) перетворює вхідне слово x_i у вихідне слово y_j .

Слід зазначити, що алфавітний оператор тільки вказує, яке вихідне слово ставиться у відповідність деякому вхідному, тобто це свого роду позначення Y = f(х). А от як це вихідне слово отримати (за якими правилами визначити f(х)) алфавітний оператор не говорить.

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

Якщо алфавітний оператор не зіставляє із вхідним словом жодного вихідного (у тому числі і порожнього), то він вважається невизначеним на цьому слові.

Множина усіх слів, на яких алфавітний оператор визначений, називається областю його визначення.

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

У самому визначенні слова закладено можливість вважати словом і один символ, і будь-який текст. Тому існують оператори різної складності реалізації.

До найбільш простих алфавітних операторів відносяться так звані посимвольні (політерні) відображення, які співставляють символи двох різних алфавітів. Тобто, кожен символ вхідного слова алфавіту A замінюється деяким символом вихідного алфавіту B.

Більш складними є так звані кодуючі відображення. Такі відображення співставляють з кожним символом вхідного алфавіту деяку скінченну послідовність символів (слово) у вихідному алфавіті, що називається кодом. Застосування таких відображень називають кодуванням.

Тобто, при кодуванні кожен символ а_i вхідного алфавіту А зіставляється із послідовністю b_i1, b_i2 ... b_iк символів алфавіту В. Відповідне слово в алфавіті В можна назвати кодом символу а_i, якщо:

1) кожному символу відповідає тільки одне слово;

2) різним символам алфавіту А відповідають різні слова в алфавіті В;

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

Нехай задані алфавіти: A = {p, r, s, t} - вхідний і B = {a, b, c, d, e, f, g, h} - вихідний. Тоді відображення символів А символами В, тобто кодом (рис.1), є прикладом кодуючого відображення. Для побудови шуканого відображення достатньо замінити всі символи будь-якого слова a_i в алфавіті А відповідними кодами алфавіту В. Так, якщо слово a_i = sstr, то Гa_i = fghfghabcceg є кодом вихідного слова b_j.

Процес, зворотний кодуванню, тобто заміна в слові b_j кодів алфавіту В символами з А, називається декодуванням і позначається як Г^-1b_j=a_i. Наприклад, для слова b=fghfghabcceg в алфавіті В декодування Г^-1b дає слово a=sstr.

Якщо при кодуванні слова a_i отримується деяке слово b_j, а декодування дає вихідне слово a_i (Гa_i=b_j, Г^-1b_j=a_i), то має місце зворотність кодування. Умова зворотності кодуванняня інакше називається умовою взаємної однозначності відповідного кодуючого відображення. У наведеному вище прикладі зворотність існує. Але, якщо задані A={a, b, c}, B={r, s}, Га=r, Гb=s, Гс=rs і слово aabca в алфавіті А, то зворотність відсутня, оскільки Гaabca = rrsrsr, а Г^-1rrsrsr = aababa (або одне з слів acaba, aabca, acca).

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

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

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

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

Кодування дозволяє звести довільні алфавітні відображення до алфавітних відображень в деякому стандартному алфавіті, в якості якого найчастіше вибирається двійковий алфавіт, що складається з двох символів - цифр 0 і 1, тобто С = {0,1}.

При цьому довжина q-го коду l_код повязана з кількістю символів Q_симв наступним чином:

.

Тут int – найменше ціле, наприклад,

int log ₂ 31 = 5,

int log ₂ 32 = 5.

В останньому випадку 32 символи мають двійкові коди 00000 ... 11111₂.

Нехай А — довільний алфавіт, що має n літер, а В — стандартний алфавіт, що має m літер. Тоді завжди можна знайти довжину слова k, що задовольняє умові m^kn, де m^k — кількість різних слів довжини k в алфавіті, що складається з m символів, і закодувати всі символи в алфавіті А словами довжини k в алфавіті В так, щоб коди різних літер були різними. Наприклад, якщо алфавіт В двійковий, а алфавіт А — латинський (26 літер), то умова 2k >26, виконується для k>5. Тобто всі літери алфавіту А можна закодувати словами алфавіту В довжиною 5 літер: 00001, 00010 ... 11010.

Будь-яке таке кодування буде нормальним і породжує зворотне кодуюче відображення слів в алфавіті А в слова в алфавіті В.

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

Основою теорії алфавітних операторів є способи їх задання. У випадку, якщо область визначення алфавітного оператора скінченна, оператор може бути заданий таблицею відповідності (у лівому стовпчику такої таблиці виписуються всі слова, що входять в область визначення оператора, що розглядається; у правому - вихідні слова, що отримуються в результаті застосування оператора до кожного слова з лівого стовпця таблиці), наприклад, словники, шрифти і т.ін., як формула (Y = Х², тобто Х  ХХ, Х = 1, 2, ..., n) або просто переліченням правил (наприклад, правил гри у шахи).

У разі нескінченної області визначення алфавітного оператора задати його за допомогою такої таблиці неможливо. У цьому випадку оператор задається системою правил p_i (p_i  P, P = {p_i}, i = 1,2, ..., n), що дозволяє за кінцеву кількість кроків знайти вихідне слово, яке відповідає будь-якому наперед заданому вхідному слову з області визначення даного алфавітного оператора. Такі правила можуть бути задані обчислювальними та логічними процедурами, елементарними та спеціальними функціями або діями, які описуються словесно у деякому абстрактному алфавіті.