Алгоритмічні проблеми (стр. 1 из 7)
1. Алгоритмічні проблеми
Навчаючи арифметиці в початковій школі, ми познайомилися з додаванням і множенням двох чисел. Нам у явній формі не говорили, що в будь-якої пари чисел існують добуток і сума, а вказали способи і правила їхнього знаходження. Такі способи і правила є прикладами алгоритмів, і обчислювальних (ефективних) процедур. Їхнє застосування не вимагає чи винахідливості чи кмітливості, учню необхідно було тільки слідувати інструкціям учителя.
Більш загально, алгоритм, чи ефективна процедура, – це механічне правило чи автоматичний метод, чи програма для виконання деяких математичних операцій. Приведемо ще кілька прикладів операцій, для яких легко можна вказати алгоритми:
(1.1) (а) по даному п знайти n-e просте число;
(b) диференціювання полінома;
(c) знаходження найбільшого загального дільника двох натуральних чисел (алгоритм Евклида);
(d) для двох даних чисел х, у вирішити, чи є х кратним у.
Неформально і схематично алгоритм представлений на мал. 1а. На вхід подається інформація чи об'єкт, що підлягає обробці (наприклад, поліном у прикладі (1.1) (b), пари натуральних чисел у прикладах (1.1) (с) і (d)), а виходом є результат обробки операції над входом (так, для (1.1) (b) це похідна полінома, а для (1.1) (d) – відповідь «так» чи «ні»). Вихід виробляється автоматично чорним ящиком-який може бути комп'ютером або школярем, що діє по інструкції, чи навіть дуже розумним добре тренованим собакою. Алгоритм є процедура (чи спосіб обчислення), здійснювана чорним ящиком для одержання виходу з входу.
Якщо алгоритм, чи ефективна процедура, використовується для обчислення значень числової функції, то ця функція називається ефективно вычислимой, чи алгоритмічно вычислимой, чи просто вычислимой. Наприклад, функції ху,
 |  |
НОД (х, у)= найбільший загальний дільник чисел х и у и f(n)= просте число вираховувані в неформальному змісті, як уже відзначалося вище.
Розглянемо, з іншого боку, наступну функцію:
 |
1, якщо в десятковому розкладанні числа pi знайдеться
g(n)== рівно п підряд йдущих цифр 7;
0 у противному випадку.
алгоритм предикативний операторний знання
Більшість математиків вважають, що g є цілком «законною» функцією. Але чи вираховувана функція g? Існує механічна процедура для послідовного породження цифр у десятковому розкладанні pi, тому напрошується «процедура» для обчислення функції g. «При заданому п почніть обчислювати десятковий розклад pi по одній цифрі за один такт часу і відзначайте появу сімок. Якщо на якому-небудь кроці з'явиться відрізок, що складається рівно з п сімок, зупините процес обчислення і покладете g(n)=0. Якщо такий відрізок не буде обнаружен, то покладете g(n)=0».
Недоліком цієї «процедури» є та обставина, що якщо для деякого п не існує відрізка з п – сімок, тоді ні на якому кроці процесу ми не можемо зупинитись і зробити висновок про те, що цей факт має місце. На кожному даному кроці ми можемо очікувати, що така послідовність сімок може зустрітися в ще недослідженній нескінченній частині розкладання pi. Таким чином, ця «процедура» буде продовжуватися нескінченно довго для усякого входу п, такого, що g(n)=0; тому вона не є ефективною процедурою. (Можливо, що існує ефективна процедура для обчислення g, заснована, імовірно, на деяких теоретичних властивостях числа pi. В даний час, однак, така процедура невідома.)
Цей приклад виявляє дві характерні риси поняття ефективної процедури, а саме що така процедура відбувається за деяку послідовність кроків (кожен крок виконується за кінцевий час) і що кожен вихід з'являється після кінцевого числа кроків.
Дотепер ми неформально описували поняття алгоритму (чи ефективної процедури) і зв'язаного з ним поняття обчислюваної функції. Ці поняття мають потребу в уточненні, перш ніж вони стануть основою для математичної теорії обчислюваності.
Визначення будуть дані в термінах простого «ідеалізованого комп'ютера», що виконує програми. Ясно, що процедури, що можуть бути пророблені реальним комп'ютером, є прикладами ефективних процедур. Однак кожен окремий реальний комп'ютер обмежений як величиною чисел, що надходять на вхід, так і розміром доступного робочого простору (для запам'ятовування проміжних результатів); саме в цьому відношенні наш «комп'ютер» буде ідеалізованим відповідно до неформальної ідеї алгоритму. Програми нашої обчислювальної машини будуть кінцевими, і ми скажимо, щоб обчислення, що завершуються, виконувалися за кінцеве число кроків. Входи і виходи ми обмежимо натуральними числами; це не є істотним обмеженням, оскільки операції, що включають інші види об'єктів, можуть бути закодовані як операції над натуральними числами. (Більш докладно ми зупинимося на цьому в § 5.)
2. Необхідні поняття, факти і нотація із інших математичних дисциплін
Тут дано огляд математичних понять і роз'яснимо позначення і терміни, що будуть використані надалі.
1. Множини
Для позначення множин звичайно будуть використовуватися прописні букви А, В, С…. Тут х 
А позначає, що х є елементом множини А чи належить множині А, а х 
А означає, що х не належить множині А. Позначення {х/… х…}, де…х… є деяке твердження, що включає х, означає множину всіх об'єктів х, для яких…х… вірно. Так, {х/х є парним натуральним числом} є множина {0,2, 4,6,…}.
Якщо А, В суть множини, то запис A
В означає, що Аміститься (як частина) в В (чи А є підмножиною В); запис А 
В означає, що А В, але А 
В (тобто А є власною підмножиною В). Об'єднання множин А, В, є множина {х| х А чи х В (чи відразу двом множинам А, В)} і позначається А U В; перетин А, В є множина {х/х А і х В} і позначається через А 
В. Різниця (чи відносне доповнення) множин А, В є множина {х / х А і х В} і позначається А\В.Порожня множина позначається через 0. Стандартний символ N позначає множину натуральних чисел {0, 1, 2, 3,…}. Якщо А – множина натуральних чисел (тобто А
N), то А позначає доповнення до А до N, тобто N\А. Через N+ позначається множина додатніх натуральних чисел {1,2,3,…}, а множина цілих чисел позначається через Z.Упорядкована пара елементів х, у позначається (х, у); таким чином, (х, у) (у, х). Картезіанським, чи декартовым, добутком множин А и В називається множина {(х, у)/х А, у В}, і позначається вона через А 
В.
Більш узагальнено, запис (х1…, хn) позначає упорядкований n-набір (п-ку) елементів х1,…, хn; часто цей n-набір позначається однією жирною буквою х. Якщо А1,…, Аn суть множини, те А1
… Аn позначає множину n-ок {(х1,…, хn)/х1 А1 і х2 А2…хn Аn}. Добуток А А … А (п разів) скорочено позначають як Аn; а А1 означає просто А.2. Функції
Ми припускаємо, що читач знайом з основним поняттям функції і розходженням між функцією f і окремим значенням f(х) на даному х, на якому функція визначена. Областю (визначення) функції f називається множина {x/f(x) визначена} і позначається Dom(f); ми будемо говорити, що f (х) не визначена, якщо x Dom(f). Множина {f (х) | х
Dom (f)} називається множиною значень, чи образом (range), функції f і позначається через Ran (f). Якщо А и В – множиниі, то будемо говорити, що f є функція з A в В, якщо Dom (f) A и Ran(f) В. Коли Dom(f)=A, буде застосовуватися позначення f: A 
r.