Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерні науки
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2002
Тип роботи:
Конспект лекцій
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
К
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
В.О.Костовський
«ТЕОРІЯ АЛГОРИТМІВ ТА МАТЕМАТИЧНІ ОСНОВИ ПРЕДСТАВЛЕННЯ ЗНАНЬ»
М е т о д и ч н i в к а з i в к и д о к у р с у л е к ц і й
для студентів бакалаврату базового напрямку
“Комп‘ютнрні науки”
Кафедра “Автоматизовані системи управління”
Курс ІV
Львів -2002
Конспект лекцій по ТА МОПЗ - 2002/2003
Методичні вказівки склав
Доцент кафедри АСУ В.О.Костовський
(вчене звання, посада викладача)
(підпис)
(прізвище, ініціали)
"___"____________2002 р.
Методичні вказівки розглянуті та схвалені на засіданні кафедри
«Автоматизовані системи управління»
(найменування кафедри, за якою закріплена дисципліна)
Протокол №___ від "___"________________2002 р.
Завідувач кафедри
Рашкевич Ю.М.
(підпис)
(прізвище, ініціали)
ВСТУП
Ці методичні вказівки до курсу лекцій з курсу «Теорія алгоритмів та математичні основи представлення знань» (ТА МОПЗ) розроблені з метою полегшення вивчення студентами основних тем даного курса відповідно до програми з ТА МОПЗ. При викладі сутевим чином використовуються підходи робіт [1,2,3].
Тема "Алгоритмічні проблеми"
§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.)
ЛІТЕРАТУРА ДО ТЕМИ
1.Вітенько І.В. Конструктивні операції. Ужгород,1972.
2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.,Мир, 1983.
Тема " Необхідні поняття, факти і нотація із інших математичних дисциплін"
Тут дано огляд математичних понять і роз'яснимо позначення і терміни, що будуть використані надалі.
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 (х) не визначена, якщо xDom(f). Множина {f (х) | х Dom (f)} називається множиною значень, чи образом (range), функції f і позначається через Ran (f). Якщо А и В- множиниі, то будемо говорити, що f є функція з A в В, якщо Dom (f)A и Ran(f)В. Коли Dom(f)=A, буде застосовуватися позначення f : Ar.
Функція називається ін’єктивною, якщо з х, у 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/xDom(g) і g(x)Dom(f)}, значення якої, коли вона визначена, є f(g(x)). Цю функцію позначають через fg.
Через 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 функцію NN, значення якої усюди дорівнює т, ми позначаємо жирним символом т.
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) якщо xy і ух, те х=у;
(iii) відношення транзитивно, а потім визначаючи х < у як х у и х у.
4. Логічні позначення
Ми скрізь вживаємо стандартні логічні позначення. Символ позначає еквівалентність по визначенню, означає логічне слідування, а позначає « випливає з». Символи, використовуються в значенні «для всіх» і «існує» відповідно.
ЛІТЕРАТУРА ДО ТЕМИ
1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.,Мир, 1983.
2. Мальцев А.И. Алгоритмы и рекурсивные фукции.-М.,Наука, 1965.
Тема " Операторні та предикатні алгоритми - І"
(Рекурсивні функції на області натуральних чисел 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 і змінних x1,..,xn,y, і x1,..,xn називаються вхідними змінними, а y - вихідною змінною .
Ми визначили СП, СОА і СОП як деякі формальні, синтаксичні конструкції. Яка ж семантика (сенс) цих конструкцій ? Як із них отримати справжні алгоритми (програми) ?
Семантика схем задається за допомогою інтерпретацій. Інтерпретація схеми алгоритму W задається парою (D,I), де D -
множина довільної природи, а I - це певне відображення, яке : а) кожному символу змінної z із пам"яті W ставить у відповідність елемент I(z) із множини D; б) кожному символу константи b із сигнатури W ставить у відповідність елемент I(b) із D; в) кожному m-арному функціональному f(m) (предикатному P(m)) символу співставляє, відповідно, всюдиозначені функцію I(f(m)) : Dm ->D, або предикат I(P(m)) -> .t.,.f..
2. Нижче в данному розділі будемо розглядати тількі підклас схем алгоритмів KS-1, які містять тільки два функціональні унарні символи f,g, один константний символ b і один унарний предикатний символ p. Також обмежимо клас інтерпретацій, поклавши, що в цьому класі KI-1 D завжди співпадає з множиною натуральних чисел N (D=N), а відображення I задовільняє наступним вимогам:
1) I(b) = 0;
2) I(f(x)) = I(x) + 1;
I(x) - 1, коли x>0
3) I(g(x)) = I(x) -^ 1 =
0 , коли x=0
(8)
.t., коли I(x) =0;
4) I(p(x)) = P0(x)) = *
.f., коли I(x) > 0.
5) I(xi) єN для всіх вхідних змінних СОА і СПА виду (6),(7), і I(y) = 0 для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів.
Опишемо формально функціонування алгоритму A виду (6) .
Нехай M(A) = z1,z2,..zn,..zm - пам'ять алгоріму A, де zi = xi при 1<= i <= n, і zm = y. Через Q(A) позначимо всі мітки A. Станом пам'яті A будемо називати послідовність (a1,..am) натуральних чисел, тобто елемент Nm. Станом (конфігурацією) алгоритму A будемо називати елемент <q;a1,..,am> із D(A) = Q & Nm.
Стан <q;a1,..,am> називається: а) проміжковим, якщо q - мітка передачи управління; б) кінцевим (заключним), якщо q - кінцева мітка алгоритму A.
Визначемо функцію переходів F : D(A) --> D(A) алгоритму A.
1. Коли <q;a1,..,am> - кінцевий стан, то
F(<q;a1,..,am>) = <q;a1,..,am>.
2. Коли <q;a1,..,am> - проміжковий стан, то значення F залежить від виду команди qk Ф[k] (ik,jk) в (5) .
Якщо Ф[k] має вигляд :
a) zr = zt + 1, то F(<q;a1,..,am>) = <q*;b1,..,bm>, де q* = ik, br = at + 1, а bu = au для всіх таких u, що u не рівне r;
b) zr = zt -^ 1, то F(<q;a1,..,am>) = <q*;b1,..,bm>, де q* = ik, br = at -^ 1, а bu = au для всіх таких u, що u не рівне r;
c) zr = 0, то F(<q;a1,..,am>) = <q*;b1,..,bm>, де q* = ik, br = 0, а bu = au для всіх таких u, що u не рівне r;
d) zr = zt , то F(<q;a1,..,am>) = <q*;b1,..,bm>, де q* = ik, br = at , а bu = au для всіх таких u, що u не рівне r;
e) P0(zr), то F(<q;a1,..,am>) = <q*;b1,..,bm>, де bu = au для всіх u (1<= u <= m), а q* = ir, якщо ar = 0, і q* = jr, якщо ar > 0.
Перейдемо до визначення функції f[A] : Nn --> N, яку
обчислює алгоритм A при інтерпретації I.
По означенню інтерпретації маємо, що початковий стан пам'яті є I(M(A)) = <a1,..,an,0,..,0>. Стан c[0] =<q0;a1,..,an,0,..,0> називається початковим станом алгоритму A при інтерпретації I. Скінченна або нескінченна послідовність
T(A) = c[0],c[1],..,c[k],c[k+1],... (9)
називається траєкторією (шляхом) алгоритму A при інтерпретації I ( на вході <a1,..,an>), якщо
F(c[k]) = c[k+1] для всіх k із N.
Зрозуміло, що траєкторія (9) для A будується конструктивно по програмі цього алгоритму і початковому значенню вхідних змінних, що задає інтерпретація I.
При послідовному обчисленні станів c[k] за допомогою функції переходів F можливі два випадки :
1) в траєкторії (9) знайдеться стан с[t] = <q*;b1,..,bm> такий, що c[t] - кінцевий стан, а c[0],c[1],..,c[t-1] - проміжкові стани;
2) в траєкторії (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A.
У першому випадку будемо вважати, що A обчислює значення f[A](<a1,..,an> функції f[A] в точці <a1,..,an> ,i f[A](<a1,..,an>) = bm. Нагадаємо, що bm природнім чином можна інтерпретувати як число, що знаходиться в вихідній змінній y в стані c[t] алгоритму A, так як, по припущенню, zm = y.
Якщо в траєкторії (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A, будемо вважати, що A циклює в точці <a1,..,an> , тому значення f[A](<a1,..,an> функції f[A] в точці <a1,..,an> не визначено , тобто f[A](<a1,..,an>) = @. Іншими словами,
bm, коли T(A) - скінченна f[A](<a1,..,an>) = *
@, коли T(A) -нескінченна
(8)
Аналогічно визначається траєкторія і функція переходів для предикатного алгорітму Aq, і вважається що Aq реалізує предикат;
.t., коли T(A) - скінченна,
і q* = q[.t.];
P[Aq](<a1,..,an>) = * .f., коли T(A) -скінченна, i
і q* = q[.f.];
@, коли T(A) -нескінченна.
Замінивши у (5) сімволи f,g,b, і p згідно з інтерпретацією I ми отримаємо програмноподібну структуру,рядки якої будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-1 далі інтерпретуються , як відповідні алгоритми (програми) iз класу прграм KП-1 , функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль, Бейсік і т.п.
А саме:
1) символ " = " у схемах (1) -(3) інтерпретується як оператор присвоєння;
2) елементи із Qs інтерпретуються аналогічно міткам в мовах програмування;
3) виконання команди qr x = y + 1 (ir,jr) інтерпретується як послідовність команд qr: x = y+1; go to ir;
4) виконання команди qr x = y -^1 (ir,jr) інтерпретується як послідовність команд qr: x = y-^1; go to ir;
5) виконання команди qr x = y (ir,jr) інтерпретується як послідовність команд qr: x = y; go to ir;
6) виконання команди qr x = 0 (ir,jr) інтерпретується як послідовність команд qr: x = 0; go to ir;
7) виконання команди qr P0(x) (ir,jr) інтерпретується як умова qr: IF P0(x) THEN go to ir ELSE go to jr.
Як і у більшості мов програмування, оператор "go to ir" при функціонуванні програми передає управління на команду з міткою ir, а оператор "IF P0(x) THEN go to ir ELSE go to jr" передає управлыння
на команду з міткою ir, якщо предикат P0(x) = .t. ( x = 0),і передає управління на команду з міткою jr, якщо предикат P0(x) = .f.(x > 0).
В теорії алгоритмів вважається, що операторні SA та предикатні SP алгоритми із KS-1 виконуються на вхідних даних із N абстрактними автоматамиом - багаторегістровими обчислювальними машинами ( N-БРМ ). Для кожного алгоритму А ця машіна Ба складається з блоку управління і m регістрів, де кожний регістр (комірка) Rk може зберігати довілне натуральне число. Блок управління містить програму Па і забезпечує її виконання по вищенаведеній схемі. Система команд N-БРМ складається з множини 0,x+1, x-^1,P0(0), які можуть виконуватися над вмістом кожного Rk, а також команд присвоювання, безумовного і умовного переходу, пересилки і запису в регістр.
Часткові або всюдиозначенні k-арні функцію g : Nk --> N, яка задана на натуральних числах , або предикат P : E* --> T,F, будемо називати рекурсивною функцією (предикатом), або R-функцією (R-предикатом),якщо існує програма із класу КП-1 П1g, що обчислює g (P).
Приклади доведення по побудові рекурсивності функцій наведені у розділі VI данної інструкції.
Як відомо [1,2], згідно до тези Тюрінга-Черча, клас всіх R-функцій вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).
3. Аналгічно до класів KS-1 схем алгоритмів і ¶нтерпретацій KI-1 введемо, відпвидно, класи KS-2 і KI-2.
Нехай E = a1,..,an - деякий алфавит. Через E* позначимо множину всіх слів в алфавібі E, включаючи однолітерні слова виду 'ai' і пусте слово e =''.
Введемо на E* деякі стандартні функції і предикати. Якщо w = x1x2..xm і v = y1y2..yk - слова iз E*, то
а) con(w,v) = wv = x1x2..xmy1y2..yk, con(e,v) =con(v,e) = v;
б) del(w) = d(w) = x2x3..xm, del(e) = e;
в) для всіх літер ai із E предикат hai(w) = T (істино), коли x1 = ai, і hai(w) = F (хибно), коли перша літера x1 у слові w не дорівнює ai (1 <= i <= m), причому для всіх i
hai(e) = F.
Якщо а - довільна літера із E*, то через ( a^n ) позначається слово, що склдається із n літер a.
Клас схем програм KS-2 містить (n + 1) унарних функціональних символів fa1,fa2,..,fan,g , один константний символ b і n унарних предикатних символів pa1,pa2,..,pan,
В класі інтерпретацій KI-2 схем із KS-1 множина D завжди співпадає з множиною E* всіх слів в алфавіті E , а кожне відображення I із KI-2 задовільняє наступним вимогам:
1) I(b) = е;
2) I(fai(x)) = con(I(x),'ai')= I(x)ai для всіх літер ai із E;
3) I(g(x)) = del(I(x));
4) I(pai(x)) = hai(I(x)) для всіх літер ai із E;
5) I(xi) єE* для всіх вхідних змінних СОА і СПА виду (6),(7), і I(y) = e для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів.
Замінивши у (5) сімволи fai,g,b і hai згідно з інтерпретацією I із класу KI-2 ми отримаємо програмноподібну структуру,рядки якої будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-2 далі інтерпретуються , як відповідні алгоритми (програми) iз класу прграм KП-2 , функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль,коли ці програми працюють на даних типу string. Ясно, що функціонуваня команд програм із класу КП-2 аналгічно , з точністю до інтерпретації символів її схеми, до функціонуваня команд програм із класу КП-1, яке було описано вище.
Зауважимо також, що по аналогії з N-БРМ БN можна ввести E-БРМ БE, що реалізує програму із КП-2, а також NE-БРМ БNE. БNE
можна розглядати як "об'єднання" програм ПN i ПE для БN i БE в тому сенсі, що множини регістрів БN i БE не перетинаються, але вони мають загальний блок управління(i спільні мітки), в якій поміщена спільна програма ПNE, в яку входять всі команди, як із ПN так і із ПE.
Часткові або всюдиозначенні функцію g : E*вх -->E*вх, яка задана на множині слів довільного алфавіту E , або предикат P : E* --> T,F, будемо називати E- рекурсивною функцією (предикатом), або RE-функцією (RE-предикатом),якщо існує програма із класу КП-2 П1g, що обчислює g (P).
Як відомо [1],[2], за допомгою кодуючої функції доводиться, що , в певному сенсі, клас R-функцій (R-предикатів) і клас RE-функцій (RE-предикатів) є еквівалентні.
Приклади доведення по побудові RE-рекурсивності функцій і предікатьв наведені далі.
1.1 Побудуємо алгоритм, що обчислює функцію
z := f1(x,y) = x + y.
x, y ! z
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = x (q11,q11)
y1 = y (q12,q12)
z1 = 0 (q13,q13)
P0(x1) (q16,q14)
z1 = z1 + 1 (q15,q15)
x1 = x1 -^ 1 (q13,q13)
P0(y1) (q19,q17)
z1 = z1 + 1 (q18,q18)
y1 = y1 -^ 1 (q16,q16)
z = z1 (Я,Я)
1.2. Побудуємо алгоритм ( не оптимальний), що заносить в z значення функції добутку x i y, тобто z := f1(x,y) = x * y.
x, y ! z
q20
q21
q22
q23
x2 = x (q21,q21)
y2 = y (q22,q22)
z2 = 0 (q23,q23)
P0(y2) (q25,q10)
q10
q11
q12
q13
q14
q15
q16
q17
q18
q19
x1 = z2 (q11,q11)
y1 = x (q12,q12)
z1 = 0 (q13,q13)
P0(x1) (q16,q14)
z1 = z1 + 1 (q15,q15)
x1 = x1 -^ 1 (q13,q13)
P0(y1) (q19,q17)
z1 = z1 + 1 (q18,q18)
y1 = y1 -^ 1 (q16,q16)
z2 = z1 (q24,q24)
q24
q25
z2 = z1 (q23,q23)
z = z2 (Я,Я)
2.1 Нехай алфавіт Е = a,b. Побудуємо алгоритм, що обчислює
предикат Pe(w), де Pe(w) = T тоді і тільки тоді, коли w є пусте слово із E*, тобто w = e.
x ! q[.t.], q[.f.]
q10 x1 = x (q11,q11)
q11 ha(x1) (q[.f.],q12)
q12 hb(x1) (q[.f.],q[.t.])
2.2. Побудуємо алгоритм ( не оптимальний), що заносить в z значення функції con(x,y) = xy, тобто z := g1(x,y) = con(x,y) = = xy для слів із Е = a,b.
x, y ! z
q20
q21
q22
x2 = x (q21,q21)
y2 = y (q22,q22)
z2 = e (q10,q10)
q10
q11
q12
x1 = y2 (q11,q11)
ha(x1) (q22,q12)
hb(x1) (q22,q28)
q22
q23
q24
ha(y2) (q23,q25)
x2 = con(x2,a) (q24,q24)
y2 = del(y2) (q22,q22)
q25
q26
q27
q28
hb(y2) (q26,q10)
x2 = con(x2,b) (q27,q27)
y2 = del(y2) (q25,q25)
z = x2 (Я,Я)
Самостійно перевірити коректність реалізації функциі і предикатів контрольних прикладів.
ЛІТЕРАТУРА ДО ТЕМИ
Вітенько ¶.В. Конструктивні операції. Ужгород,1972.
2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.,Мир, 1983.
3. Мальцев А.И. Алгоритмы и рекурсивные функции.-М.,Наука, 1965.
Тема " Операторні та предикатні алгоритми -ІІ"
(Рекурсивні функції на областях, що відмінні від N)
Оскільки БРМ працює тільки з натуральними числами, наше визначення обчислюваності і можливості розв'язання застосовано тільки до функцій і предикатів від натуральних чисел. Ці поняття легко поширюються на інші види об'єктів (тобто цілі числа, поліноми, матриці і т.д.) за допомогою кодування.
Кодуванням області D об'єктів називається явне й ефективне відображення α : D →N. Ми будемо говорити, що об'єкт α € D кодується натуральним числом α (d). Припустимо, що f є функцією з D в D; тоді f природно кодується функцією f* з N в N, що відображає код кожного об'єкта d € Dom(f) у код об'єкта f (d). У явному виді це можна записати як
f*=α · f ·a-1
Тепер можна поширити визначення Мнр-обчислюваності на область D, рахуючи функцію f обчислюваною, якщо f*—обчислювана функція натуральних чисел.
Приклад. Розглянемо область Z. Явне кодування можна задати функцією α, де
2n, якщо n ( 0,
α-(n) =
-2n-1, якщо n < 0.
Тоді α-1 задається так:
(1/2)m , якщо m парне,
α-1 (m) =
(-1/2)(m+1), якщо m непарне.
Тепер розглянемо функцію х—1 на Z; позначаючи цю функ-ю через f, одержуємо f*:N →N, що задається:
1, якщо x:==0 (тобто х=α(0)),
f*(x)= х—2, якщо х> 0 і х парне (тобто х=а(п), п>0),
х +2, якщо х непарне (тобто х=α(n), п < 0).
Написання програми, що обчислює f*, є рутинною вправою; отже, х—1 є обчислювана функція на Z.
Приведене вище визначення очевидним образом розширюється на n-місцеві обчислювальні функції на області D і розв'язні предикати на D.
5.2. Вправи
1. Покажіть, що функція 2х на Z обчислювана.
2. Покажіть, що предикат ( x≥0 ) на Z є розв'язним.
ЛІТЕРАТУРА ДО ТЕМИ
1.Вітенько І.В. Конструктивні операції. Ужгород,1972.
2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.,Мир, 1983.
Тема " Алгоритмічні проблеми для L"
Нижче дається огляд нерозв'язних проблем, що виникають у самій теорії обчислювальності, і обговорюються деякі методи доказу нерозв'язності. Нагадаємо , що предикат М(х) називається розв'язним, якщо його характеристична функція, що задається формулою
1, якщо M(x) правдиве ,
Cm (x) =
0, якщо M(x) неправдиве
обчислювана. Це рівносильно твердженню про те, що предикат М (х) рекурсивний Предикат М (х) називається нерозв'язним, якщо він не є розв'язним. У літературі використовуються наступні терміни, еквівалентні твердженню про те, що предикат М (х) розв'язний:
М (х) рекурсивний,
М (х) має рекурсивну проблему дозволу,
М (х) рекурсивно розв'язний,
М (х) обчислювальний.
Алгоритм, що обчислює см, називається обчислювальною процедурою, для M(x).
1. Нерозв'язні проблеми в теорії обчислюваності
У більшості випадків докази нерозв'язності ґрунтуються на діагональному методі, як, наприклад, у наступному важливому прикладі.
1.1. Теорема. Проблема «x (Wx» (чи, що еквівалентно, «функція (x(х) визначена», чи «Рx(х)(», чи «функція(u(х, х) визначена») нерозв'язна.
Доведення. Характеристична функція цієї проблеми задається наступною формулою:
1,якщо x( Wx
f(x)=
0,якщо x( Wx
Припустимо, що функція f обчислювана, і приведемо це припущення до протиріччя. Саме за допомогою діагонального методу ми побудуємо обчислювану функцію g, таку, що Dom(g)(Wx(= Dom(фx)), при всіх х, чого, мабуть, бути не може.
Як завжди при використанні діагонального методу, ми будемо прагнути до того, щоб множина Dom(g) відрізнялося від Wx у njxці х. Тому будемо домагатися того, щоб
x ( Dom (g) (x (Wx
Визначимо тепер функцію g у такий спосіб:
0, якщо x( Wx (тобто якщо f(x)=0),
g(x)=
не визначена, якщо x( Wx (тобто якщо f(x)= 1).
Оскільки функція f обчислювана, то (по тезі Черча) обчислювана і функція g, що і дає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана, візьмемо таке т, що g=(m, тоді т ( Wm ( т ( Dom (g)(т ( Wm, чого не може бути.)
Отже, ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x (Wx» нерозв'язна. (
Зауважимо, що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретного числа а сказати, чи буде визначене значення (a (a). Для деяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, що обчислює тотальну функцію, і Р=Рa, то ми відразу знаємо, що значення (a (a) визначено. Теорема говорить лише, що не існує єдиного загального методу рішення питання про те, чи буде (x(х) визначено; іншими словами, не існує методу, що працює при всіх х.
Простий наслідок цього результату полягає в наступному.
1.2. Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x ( Dom(h) » і «х ( Ran(h)» нерозв'язні.
Доведення. Покладемо
x , якщо x( Wx
h(x)=
не визначена, якщо x( Wx
Тоді в силу тези Черча і обчислюваності універсальної функції (u функція h обчислювана (більш формально ми маємо h(x)( x1 ((u(х, х)), а ця функція обчислювана як результат підстановки). Ясно, що x ( Dom(h)( x( Wx (x ( Ran (h), так що обидві проблеми «x ( Dom(h) » і «х ( Ran(h)» нерозв'язні. (
З теореми 1.1 виводиться ще одна важлива нерозв'язна проблема:
1.3. Теорема (проблема зупинки). Проблема «функція фx(у) визначена» (чи в еквівалентній формі «Рx(y)( , чи « y ( Wx» нерозв'язна.
Доведення. Міркуючи неформально, ми відразу бачимо, що якби проблема «функція фx(у) визначена» була б розв'язна, то була б розв'язна і більш проста проблема «функція фx(х) визначена», що суперечить теоремі 1.1.
Щоб провести всі ці міркування більш докладно, розглянемо характеристичну функцію проблеми^ «функція фх(у) визначена», що має наступний вид:
1,якщо фх(у) визначена
g(x,y)=
0,якщо фх(у)не визначена
Якби функція g була обчислювана, то обчислюваною була б і функція f(x)=g(x, х), але f є характеристична функція проблеми «х ( Wx» і, отже, не обчислювана в силу теореми 1.1. Отже, функція g не обчислювана, і тим самим проблема « фx(y) визначена» нерозв'язна. (
Теорему 1.3 часто інтерпретують як твердження про нерозв'язність проблеми зупинки (для МНР-программ), у якому говориться про те, що не існує ніякого ефективного загального методу установити, чи зупиниться деяка конкретна програма, запущена після введення в неї деякого конкретного набору початкових даних. Зміст цього твердження для теоретичного програмування очевидний: не існує зовсім загального методу перевірки програм на наявність у них нескінченних циклів.
Розглянута в теоремі 1.1 нерозв'язна проблема «х ( Wx» важлива з кількох причин. Одна з них полягає в тому, що нерозв'язність багатьох проблем можна довести, показавши, що вони принаймні не простіші, ніж ця. Саме таким шляхом ми довели, що проблема зупинки (теорема 1.3) нерозв'язна: цей процес називається зведенням однієї проблеми до іншої.
Узагалі розглянемо деяку проблему М (х). Часто вдається показати, що рішення загальної проблеми М (х) привело б до рішення загальної проблеми «х ( Wx» , Тоді говорять, що проблема «х ( Wx» зводиться до проблеми М (х). Іншими словами, якщо мається дозволяюча процедура для проблеми М (x), то ми можемо дати і дозволяючу процедуру для проблеми «х ( Wx» . Таким чином, з можливості розв'язання М(х) випливає можливість розв'язання «х ( Wx» , звідки ми негайно робимо висновок, що М (х) нерозв'язна.
Для зведення проблеми «х ( Wx» до інших проблем часто використовується s-m-n-теорема, як показує, наприклад, доведення наступного результату.
1.4. Теорема. Проблема «фx=0» нерозв'язна.
Доведення. Розглянемо функцію f, визначену формулою
0, якщо х ( Wx
f(x,y)=
не визначена, якщо x ( Wx
Цю функцію ми ввели для того, щоб далі скористатися s-m-n-теоремою. Тим самим ми розглядаємо х як параметр, і нас цікавлять функції gx, такі, що gx(y)( f(x, у). При цьому ми вибрали f так, що gx=0(х ( Wx.
Теза Черча (чи підстановка з використанням 0 і (u) показує, що функція f обчислювана. Тому існує тотальна обчислювана функція k(x), що дається s-m-n-теоремо., така, що f(x, у)((k(x); тобто (k(x)=gx. Таким чином, по визначенню
(*) х ( Wx( (k(x)= 0
Отже, питання про те, чи вірно, що х ( Wx, можна вирішити, відповівши спочатку на питання: чи вірно, що (k(x)=0? Тим самим ми звели загальну проблему «х ( Wx» до загальної проблеми «фx=0»; оскільки перша з них нерозв'язна, те нерозв'язна і друга, що і було потрібно довести.
У зв'язку з тим що це перший приклад подібного роду, що зустрівся нам, розглянемо останню частину нашого міркування більш докладно. Нехай g-характеристична функція проблеми «фx=0», тобто
1, якщо фx=0
g(x)=
0, якщо фx(0
Припустимо, що функція g обчислювана. Тоді обчислюваною буде і функція h (х) = g (k (х)). У той же час співвідношення (*) дає
1, якщо фk(x)=0, тобто x( Wx,
h(x)=
0, якщо фk(x)(0, тобто x( Wx.
Тим самим у силу теореми 1.1 функція h не є обчислюваною. Стало бути, і функція g не є обчислюваною, так що проблема «фx=0» нерозв'язна. (
Теорема 1.4 показує, що в області перевірки правильності комп'ютерних програм є принципові обмеження. У ній говориться про те, що не може бути зовсім загального ефективного методу здійснити перевірку того, чи буде програма обчислювати нульову функцію. Трохи змінивши доведення теореми 1.4, можна переконатися в тім, що те ж саме справедливо і для будь-якої іншої конкретної обчислюваної функції (див. нижче впр. 1.8(i)).
Простий наслідок теореми 1.4 показує, що питання про те, чи обчислюють дві програми ту саму одномісну функцію, нерозв'язне. Зміст цього результату для теоретичного програмування також очевидний.
1.5. Наслідок. Проблема «фx=фy» нерозв'язна.
Доведення. Легко переконатися в тому, що ця проблема складніша проблеми «фx=0». Нехай с - таке число, що фс=0. Якщо f(x,y) - характеристична функція проблеми фx = фу, то функція g (x}=f (х, с) є характеристична функція проблеми «фx=0». По теоремі 1.4 функція g необчислювана, так що необчислювана і функція f. Отже, проблема «фx=фy » нерозв'язна. (
У наступних результатах ми знову скористаємося s-m-n-теоремою для зведення проблеми «х ( Wx».
1.6. Теорема. Нехай c - довільне число. Наступні проблеми нерозв'язні.
(а) (Проблема входу) «c ( Wx» (чи в еквівалентному формулюванні «Рx (с)(», чи «c ( Dom (фx)»);
(b) (Проблема виходу) «c ( Ex» (чи в еквівалентному формулюванні «с ( Ran (фx)»).
Доведення. Ми можемо звести...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора