Алгоритмiчнi проблеми

1. Алгоритмiчнi проблеми

Навчаючи арифметицi в початковiй школi, ми познайомилися з додаванням i множенням двох чисел. Нам у явнiй формi не говорили, що в будь-якоi пари чисел iснують добуток i сума, а вказали способи i правила iхнього знаходження. Такi способи i правила i прикладами алгоритмiв, i обчислювальних (ефективних) процедур. РЗхнi застосування не вимагаi чи винахiдливостi чи кмiтливостi, учню необхiдно було тiльки слiдувати iнструкцiям учителя.

Бiльш загально, алгоритм, чи ефективна процедура, тАУ це механiчне правило чи автоматичний метод, чи програма для виконання деяких математичних операцiй. Приведемо ще кiлька прикладiв операцiй, для яких легко можна вказати алгоритми:

(1.1) (а) по даному п знайти n-e просте число;

(b) диференцiювання полiнома;

(c) знаходження найбiльшого загального дiльника двох натуральних чисел (алгоритм Евклида);

(d) для двох даних чисел х, у вирiшити, чи i х кратним у.

Неформально i схематично алгоритм представлений на мал. 1а. На вхiд подаiться iнформацiя чи об'iкт, що пiдлягаi обробцi (наприклад, полiном у прикладi (1.1) (b), пари натуральних чисел у прикладах (1.1) (с) i (d)), а виходом i результат обробки операцii над входом (так, для (1.1) (b) це похiдна полiнома, а для (1.1) (d) тАУ вiдповiдь ВлтакВ» чи ВлнiВ»). Вихiд виробляiться автоматично чорним ящиком-який може бути комп'ютером або школярем, що дii по iнструкцii, чи навiть дуже розумним добре тренованим собакою. Алгоритм i процедура (чи спосiб обчислення), здiйснювана чорним ящиком для одержання виходу з входу.

Якщо алгоритм, чи ефективна процедура, використовуiться для обчислення значень числовоi функцii, то ця функцiя називаiться ефективно вычислимой, чи алгоритмiчно вычислимой, чи просто вычислимой. Наприклад, функцii ху,