Алгоритмічні проблеми
Навчаючи арифметиці в початковій школі, ми познайомилися з додаванням і множенням двох чисел. Нам у явній формі не говорили, що в будь-якої пари чисел існують добуток і сума, а вказали способи і правила їхнього знаходження. Такі способи і правила є прикладами алгоритмів, і обчислювальних (ефективних) процедур. Їхнє застосування не вимагає чи винахідливості чи кмітливості, учню необхідно було тільки слідувати інструкціям учителя.
Більш загально, алгоритм, чи ефективна процедура, – це механічне правило чи автоматичний метод, чи програма для виконання деяких математичних операцій. Приведемо ще кілька прикладів операцій, для яких легко можна вказати алгоритми:
(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.
Функція
називається
ін’єктивною,
якщо з х, у
Dom (f) і х
у
випливає f(х)
f
(у). Для ін’єктивної
функції f через
f -1 позначається
функція, зворотня
до f, тобто така
єдина функція
g, що Dom (g)=Ran (f) g (f(x))=x для
всіх х
Dom
(f). Функція f
з А в В називається
сюр’єктивною,
якщо Ran(f)=B.
Якщо f:
A
В и функція
f ин’єктивна
(сюр’єктивна),
то f називається
ін'єкцією (з
А в В) (сюр’єкцією
(з А в В)). Функція,
що є одночасно
ін'єкцією і
сюръекцией,
називається
биекцией.
Припустимо,
що f є функцією,
а Х – множина.
Обмеженням
f на Х називається
функція з областю
визначення
Х
Dom(f),
значення якої
в кожному х
Х
Dom (f) дорівнює
f(x).
Обмеження
f на Х позначається
через f|X. Ran (f|X)
позначається
через f(X). Якщо
Y – множина, то
прообразом
Y відносно f
називається
множина f-1(Y)={x|f(x)
Y}.
(Помітимо, що
прообраз визначений
навіть тоді,
коли функція
не ин’єктивна.)
Якщо f,
g-функції, то
будемо говорити,
що g продовжує
f, коли Dom (f)
Dom (g) і f(х) = g (х) для
всіх х
Dom (f); у коротшому
запису: f=g/Dom(f).
Це відношення
функцій f, g
записується
як f
g.
Композиція
двох функцій
f і g є функція
з областю визначення
{x/x
Dom(g)
і g(x)
Dom(f)},
значення якої,
коли вона визначена,
є f (g(x)). Цю функцію
позначають
через f
g.
Через f0 позначаємо ніде не визначену функцію; тобто Dom(f0)=Ran(f0)=0. Очевидно, що f0=g|0 для будь-якої функції g.
В обчисленнях
нам часто будуть
зустрічатися
функції чи
вирази, що включають
функції, що не
усюди визначені.
У таких випадках
дуже зручне
наступне позначення.
Нехай a(x) і b(х) –
вирази, що
включають
змінні х=(х1,…,
хn). Тоді
запис а(x)
b(x)
означає, що для
кожного х
вираження а(x)
і b(x) або одночасно
визначені і
рівні, або обидва
не визначені.
Так, наприклад,
для функцій
f і g запис
f(x)
g(x)
означає, що
f=g; і для довільного
числа y запис
f(x)
y означає, що
f(x) визначена
і дорівнює y
(оскільки y
завжди визначене).
Функції від натуральних чисел. У більшій частині цієї книги ми будемо мати справу з функціями від натуральних чисел, тобто з функціями з Nn в N для різних п, здебільшого для п = 1 чи 2.
Функція
f з Nn в N називається
п-місною функцією.
Значення f на
п-кі (x1,…,
хn)
Dom
(f) записується
як f(x1,…, xn)
чи f(x), якщо x
представляє
(x1,…, xn).
У багатьох
книгах і статтях
термін часткова
функція
використовується
для позначення
функції з Nn
у N, область
визначення
якої не обов'язково
збігається
з Nn. Для нас
слово функція
означає часткову
функцію. Проте
при нагоді ми
будемо писати
«часткова
функция», щоб
підкреслити
її можливу «не
усюди визначеність».
Тотальною
функцією з
Nn у N ми називаємо
функцію з Nn
у N), область
визначення
якої є всі Nn.
l
Ми затушовуємо
розходження
між функціями
і їхнім значеннями
в різних крапках,
особливо у
випадку теоретико-числових
функцій у двох
досить стандартних
і недвозначних
ситуаціях.
По-перше, ми
допускаємо
такі фрази як
«Нехай f(x1,…,
xn) – функція…»,
що означає, що
f є n-місною
функцією. По-друге,
ми часто описуємо
функцію в термінах
її значення,
що задається
деякою формулою.
Наприклад,
«функція х2»
означає «одномісна
функція f, значення
якої в кожному
х
N є х2»; аналогічно
«функція х
+ у» означає
«двомісна
функція», значення
якої в кожній
парі (х, у)
N2 є х+ у.
Функцію,
тотожно рівну
0 на N, ми позначаємо
через 0, і взагалі
для т
N функцію N
N,
значення якої
усюди дорівнює
т, ми позначаємо
жирним символом
т.
3. Відношення і предикати
Якщо А – множина, то властивість М(х1,…, хn), що виконується на деяких n-ках з Аn і не виконується (чи помилкове) на всіх інших n-ках з An, називається п-місним відношенням, чи предикатом на А.
Наприклад, властивість х<у є двомісне відношення (чи предикат) на N; 2 < 3 виконується (чи істинно), тоді як 9 < 5 не виконується (чи хибно). Інший приклад: кожна n-місна функція f з Nn у N приводить до (п + 1) – місцевого предиката М (х, у), що задається умовою:
М (x1,…,
хn, у), якщо
і тільки якщо
f (x1,…, xn)
у.
Відношення еквівалентності і порядку. (Читач, не знайомий з цими поняттями, може при бажанні відкласти читання цього параграфа доти, поки він не буде потрібен в гл. 9.) У гл. 9 ми зустрінемося із двома спеціальними видами відносин на множині А.
(a) Бінарне
відношення
R на множині
А називається
відношенням
еквівалентності,
якщо для всіх
х, у, z
А
виконуються
три наступні
властивості:
(i) (рефлективність) R (х, х);
(іі) (симетрія)
R (х, y)
R (у, х);
(iii) (транзитивність) якщо R (x, y) і R (у, z), то R (х, z). Говорячи, що х, y еквівалентні (у деякому спеціальному змісті), ми маємо на увазі відношення R (х, у). Потім ми визначаємо клас еквівалентності х як множина {у | R (х, у)}, що складається з всіх елементів, еквівалентних х.
(b) Двомісне
відношення
R на множині
А називається
частковим
порядком, якщо
для всіх х, у,
z
A.
(i) (іррефлексивность) не R (х, х);
(іі) (транзитивність) якщо R (х, у) і R (y, z), те R (x, z).
Частковий порядок звичайно позначається символом <, і ми віддаємо перевагу запису х < у запису < (х, у). Часто визначають частковий порядок, вводячи спочатку предикат < (позначающий < чи =) із властивостями:
(i) х
х;
(ii) якщо
x
y
і у
х,
те х=у;
(iii) відношення
транзитивно,
а потім визначаючи
х < у як х
у и х
у.
4. Логічні позначення
Ми скрізь
вживаємо стандартні
логічні позначення.
Символ
позначає
еквівалентність
по визначенню,
означає логічне
слідування,
а
позначає «випливає
з». Символи
,
використовуються
в значенні «для
всіх» і «існує»
відповідно.
3. Операторні та предикатні алгоритми – І
(Рекурсивні функції на області натуральних чисел N)
Розглянемо математичне визначення [1,2] класів функцій та предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).
1. Введемо зчисленні множини символів або послідовностей символів (слів, ідентифікаторів і т. п.) із довільної конструктивної множини:
а) індивідні: x, y, z, x0, y0, z0, x1, y1, z1,… xj, yj, zj,…;
б) функціональні: f, g, h, f0, g0, h0, f1, g1, h1,… fj, gj, hj,…;
в) предикатні: P, Q, R, P0, Q0, R0, P1, Q1, R1,… Pj, Qj, Rj,…;
г) константи: a, b, c, a0, b0, c0, a1, b1, c1,… aj, bj, cj,…;
д) мітки: q, i, j, q0, i0, j0, q1, i1, j1,… qk, ik, jk,…
Кожній функціональному та предикатному символу U однозначно ставиться у відповідність натуральне число n, яке називається арністю даного символа. Цей символ позначається через U(n), або U (x1, x2., xn) та т. п., і називається n-арним символом. Вважається, що ідеалізований об'єкт – 0-арний функціональний символ U(0) співпадає з символом константи.
Схемою оператора присвоювання називається вираз виду:
z(i) = f(m) (x(1)., x(m)). (1)
Схемою оператора пересилки називається вираз виду:
z(k) = y(j) (2)
Схемою прісвоювання константи називається вираз виду:
z(k) = a, або z(k) = fj(0) (3)
Схемою умови називається вираз виду:
P(s) (x(1)..x(s)) (4)
Схемою програми (СП) S називатимемо об'єкт виду
q0 Ф[0] (i0, j0)
q1 Ф[1] (i1, j1)
……………. (5)
qs Ф[s] (is, js)
В (1) Qs = Qs1 u Qs2, де Qs1 = q0, q1..qs, і
Qs2=i0, j0., is, js – підмножини множин міток. Як правило, якщо не вказане уточнення, будемо вважати, що qi – qj, якщо i – j, (qi, qj належать Q1). Мітки із Q1 називаються мітками передачі управління, а мітки із (Qs – Qs1) – кінцевими мітками.
Для всіх k є [0_s], Ф[k] – це одна із схем (1) – (4).
Сукупність всіх індивідних змінних СП (5) називається пам "яттю схеми S. Сукупність константанктних, функціональних, предикатних символів і пам" яті S називається сигнатурою, або базисом, схеми S.
Конструкція вигляду
qr Ф[r] (ir, jr)
із (5) називається схемою команди.
Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду:
SA= (x1, x2., xn; S; y), (6)
де x1., xn, y – змінні, S – СП вигляду (5).
Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду:
SP= (x1, x2., xn; S; q [.t.], q [.f.]), (7)
де x1., xn, – змінні, S – СП вигляду (5), а q [.t.], q [.f.]) – кінцеві мітки СП S.
Зауважимо, що пам "яттю алгоритмів (6), (7) називається об" єднання пам"ятті S і змінних