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

ЛЕКЦІЯ 1

ПЛАН

1. Зміст дисципліни "Теорія алгоритмів", її зв’язок із іншими дисциплінами.

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

3. Відносні алгоритми.

4. Поняття числення, його зв’язок із поняттям алгоритму.

5. Поняття формальної системи.

1. Зміст дисципліни "Теорія алгоритмів", її зв’язок із іншими дисциплінами

Теорія алгоритмів як окремий розділ математики, що вивчає загальні властивості алгоритмів, виникла в 30-их роках ХХ століття. Необхідність точного математичного коректування інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв’язку багатьох масових проблем, у першу чергу пов’язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул і формул першопорядкового числення предикатів, 10-а проблема Гільберта про розв'язність діофантових рівнянь й ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою постала проблема знаходження адекватних формальних моделей алгоритму й дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції.

Першими формальними моделями алгоритмічно обчислюваних функцій були l- означувані функції (А.Чорч, 1932) та загальнорекурсивні функції (К.Гедель, 1934). Вказані класи визначались як функції, графіки котрих породжуються відповідно численням l-конверсій і численням Ербрана-Геделя. В 1936 році С. Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, увівши поняття частково рекурсивної функції, та описав клас таких функцій у чисто функціональних термінах. У 1943 році Е. Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем).

Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини й обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тьюрінга (А.Тьюрінг, Е.Пост, 1936). Із пізніших моделей відзначимо нормальні алгоритми (А.Марков, І952) та регістрові машини (Д.Шепердсон, Г.Стерджіс, 1963).

У 1936 р. А.Чорч і С.Кліні довели збіжність класів загальнорекурсивних та l-означуваних функцій. На основі цього факту й аналізу ідей, які привели до вказаних понять, А.Чорч висунув тезу про збіжність класу АОФ із класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведена А.Тьюрінгом у 1937 р. збіжність класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тьюрінга, стала ще одним підтвердженням тези Чорча. Пізніше такі збіжності були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.

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

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

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

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

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

Указане формулювання можна розглядати тільки як пояснення, а не як визначення, тому що поняття алгоритму в силу його первісності не можна виразити через інші поняття математики. Наведене поняття можна далі уточнити, явно виділивши характерні властивості алгоритму, до яких звичайно відносять:

І) фінітність - алгоритм є скінченним об'єктом, що виступає необхідною умовою його механічної реалізовності;

2) масовість - початкові дані для алгоритму можна вибирати із певної (можливо, нескінченної) множини даних; це означає, що алгоритм призначений не для однієї конкретної задачі, а для класу однотипних задач;

3) дискретність - розчленованість процесу виконання алгоритму на окремі кроки; це означає, що алгоритмічний процес здійснюється в дискретному часі;

4) елементарніст ь - кожен крок алгоритму має бути простим, елементарним, можливість виконання якого людиною або машиною не викликає сумнівів;

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

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

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

Для опису алгоритму необхідно вказати множину його початкових даних та множину даних, до яких належать результати. Ці множини називають також множиною вхідних даних і множиною вихідних даних алгоритму. Алгоритм із множиною вхідних даних X та множиною вихідних даних Y називають X-Y-алгоритмом.

Нехай алгоритм À має множину вхідних даних X. Областю застосування алгоритму À називають підмножину D Í X таку, що до кожного d Î D алгоритм À застосовний. Якщо À видає результат b при роботі над вхідним даним d, це позначатимемо b =À(d).

Кожний X-Y- алгоритм À визначає функцію f: Х → Y, узагалі кажучи, часткову, задану наступним чином.

Для кожного елемента d Î Х маємо f (d)=À(d), якщо d Î D, тобто À до d застосовний. Якщо d Ï D, то f (d) не визначене, тобто À до d незастосовний.

Кажуть, що такий алгоритм À обчислює функцію f.

Функція називається алгоритмічно обчислюваною (скорочено АОФ), якщо існує алгоритм, який її обчислює.

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

Множина L називається алгоритмічно розв'язною відносно множини U, якщо існує алгоритм, який дозволяє для кожного x Î U визначати, x Î L чи x Ï L.

Кожна алгоритмічно розв'язна непорожня множина є алгоритмічно перелічною. Справді, нехай L розв'язна відносно U за допомогою алгоритму À. Укажемо алгоритм Â, який перелічує L. Зафіксуємо довільний елемент b Î L. На вхід Â подаємо довільний х Î U і запускаємо À над х. Якщо x Î L, то Â видає х як результат; якщо x Ï L, то Â видає b як результат.

Поиск по сайту: