Домашня робота ТА 2

Міністерство освіти і науки України

Національний авіаційний Університет

Кафедра прикладної інформатики

Домашня робота

з дисципліни «Теорія алгоритмів»

Виконав: студент ТП-113

Односумов М.С.

Київ 2015

Домашня робота

Тема роботи: Методи розробки алгоритмів.

Мета роботи: Одержати навики застосування основних методів розробки алгоритмів

Варіант 15

Завдання

1) Основні визначення і теореми теорії рекурсивних функцій

2) Задача пошуку найкоротшого шляху між усіма парами вершин в (ор)графі, обрахувати для заданого орієнтованого графу методом Флойда:

1

8

					28
2	14			20	44		15
		3					18
31				9		35	7
			22
	5				66

Завдання 1:

Арифметичні функції, для обчислення значень яких є які-небудь алгоритми, прийнято називати обчислюваними. Обчислювані функції грають в математиці важливу роль. В той же час, якщо поняттю алгоритму тут не буде доданий точний сенс, то і само поняття обчислюваної функції виявиться декілька розпливчатим. Р. ф. вже через сам характер свого визначення виявляються обчислюваними. У відомому сенсі вірно і зворотне: є серйозні підстави вважати, що математичне по своєму характеру поняття рекурсивності є точним еквівалентом декілька розпливчатого поняття вичислімості. Пропозиція вважати поняття вичислімості співпадаючим за об'ємом з поняттям рекурсивності відома в теорії Р. ф. під назвою тези Черча по імені американського математика А. Черча, що вперше (у 30-х рр. 20 ст) сформулював і обгрунтував це пропозиція. Прийняття тези Черча дозволяє додати поняттю обчислюваної арифметичної функції точний математичний сенс і піддати це поняття вивченню за допомогою точних методів.

  Р. ф. є частковими функціями, тобто функціями, не обов'язково усюди визначеними. Щоб підкреслити цю обставину, часто як синонім використовують термін «частково рекурсивні функції». Р. ф., визначені при будь-яких значеннях аргументів, називають загальнорекурсивними функціями.

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

  Оператор підстановки зіставляє функції f від n змінних і функціям g ₁ . . ., g _n від m змінних функцію h від m змінних таку, що для будь-яких натуральних чисел x ₁ , .., x _m

h ( x ₁ , .., x _m ) @ f ( g ₁ ( x ₁ , .., x _m ) ..., g _m ( x ₁ , .., x _m ))

(тут і нижче умовна рівність @ означає, що обидва вираження, що зв'язуються їм, осмислено одночасно і в разі свідомості мають одне і те ж значення).

  Оператор примітивної рекурсії зіставляє функціям f від n змінних і g від n + 2 змінних функцію h від n + 1 змінних таку, що для будь-яких натуральних чисел x ₁ , .. .., x _n , в

h ( x ₁ , .., x _n ,0) @ f ( x ₁ , .., x _n ),

h ( x ₁ , .., x _n , в + 1) @ g ( x ₁ , .., x _n , в , h ( x ₁ , .., x _n , в )).

  Оператор мінімізації зіставляє функції f від n змінних функцію h від n змінних таку, що для будь-яких натуральних чисел x ₁ , .., x _n

h ( x ₁ , .., x _n ) @ f ( x ₁ , .., x _n-1 , в )

де в таке, що f ( x ₁ , .., x _n-1 , в -1) визначені і відмінні від x _n , а f ( x ₁ , .., x _n , в ) визначена і рівна x _n , якщо ж в з вказаними властивостями не існує, то значення h ( x ₁ , .., x _n ) вважається не визначеним.

  Важливу роль в теорії Р. ф. грають так звані примітивно рекурсивні функції — Р. ф., що виходять з вихідних функцій в результаті кінцевого числа вживань одних лише операторів підстановки і примітивної рекурсії. Вони утворюють власну частину класу загальнорекурсивних функцій. Через відому теорему Кліні про нормальну форму Р. ф. можуть бути вказані такі конкретні примітивно рекурсивні функції U від однієї змінної і T _n от n + 2 змінних, що для будь-якого Р. ф. j від n змінних і для будь-яких натуральних чисел x ₁ . . ., x _n має місце рівність j( x ₁ ..., x _n )@ U ( в ), де в є найменше з чисел z таких, що T _n (j, x ₁ ..., x _n , z ) = 0 (тут j є т.з. гедельов номер функції j — число, яке ефективно будується за системою рівності, задаючою функцію j). З цієї теореми, зокрема, витікає, що для Р. ф. від п змінних може бути побудована універсальний Р. ф. від n +1 змінних, тобто такий Р. ф. Ф _n , що для будь-якого Р. ф. j від n змінних і для будь-яких натуральних чисел x ₁ . . ., x _n має місце умовна рівність

j( x ₁ . . ., x _n )@ Ф _n (, x ₁ . . ., x _n ).

  Це — один з центральних результатів загальної теорії Р. ф.

  Теорія Р. ф., будучи частиною алгоритмів теорії, є розгалуженою математичною дисципліною з власною проблематикою і з додатками в ін. розділах математики. Поняття «Р. ф.» може бути покладене в основу конструктивного визначення вихідних математичних понять. Широке вживання теорія Р. ф. знайшла в математичній логіці . Зокрема, поняття примітивне рекурсивній функції лежить в основі первинного доведення знаменитої теореми Геделя про неповноту формальної арифметики, а поняття «Р. ф.» в його повному об'ємі було використано С. К. Кліні для інтерпретації інтуїционістськой арифметики (дослідження це склало цілу епоху в області семантики ). Апарат теорії Р. ф. використовується також в теорії обчислювальних машин і програмування.

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

Завдання 2:

D0=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	∞	∞	∞
	∞	∞	0	20	∞	9	∞	∞
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	∞	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0

На основании матрицы D⁰, вычислим последовательно все элементы матрицы D¹. Для этого мы используем рекуррентное соотношение d_i,j¹=min{ d_i,1⁰+ d_1,j⁰; d_i,j⁰}. d_1,1¹=min{d_1,1⁰+d_1,1⁰d_1,1⁰}=min{0+0; 0}=0 d_1,2¹=min{d_1,1⁰+d_1,2⁰d_1,2⁰}=min{0+∞; ∞}=∞ d_1,3¹=min{d_1,1⁰+d_1,3⁰d_1,3⁰}=min{0+∞; ∞}=∞ d_1,4¹=min{d_1,1⁰+d_1,4⁰d_1,4⁰}=min{0+∞; ∞}=∞ d_1,5¹=min{d_1,1⁰+d_1,5⁰d_1,5⁰}=min{0+∞; ∞}=∞ d_1,6¹=min{d_1,1⁰+d_1,6⁰d_1,6⁰}=min{0+∞; ∞}=∞ d_1,7¹=min{d_1,1⁰+d_1,7⁰d_1,7⁰}=min{0+∞; ∞}=∞ d_1,8¹=min{d_1,1⁰+d_1,8⁰d_1,8⁰}=min{0+28; 28}=28 d_2,1¹=min{d_2,1⁰+d_1,1⁰d_2,1⁰}=min{14+0; 14}=14 d_2,2¹=min{d_2,1⁰+d_1,2⁰d_2,2⁰}=min{14+∞; 0}=0 d_2,3¹=min{d_2,1⁰+d_1,3⁰d_2,3⁰}=min{14+∞; ∞}=∞ d_2,4¹=min{d_2,1⁰+d_1,4⁰d_2,4⁰}=min{14+∞; ∞}=∞ d_2,5¹=min{d_2,1⁰+d_1,5⁰d_2,5⁰}=min{14+∞; 31}=31 d_2,6¹=min{d_2,1⁰+d_1,6⁰d_2,6⁰}=min{14+∞; ∞}=∞ d_2,7¹=min{d_2,1⁰+d_1,7⁰d_2,7⁰}=min{14+∞; ∞}=∞ d_2,8¹=min{d_2,1⁰+d_1,8⁰d_2,8⁰}=min{14+28; ∞}=42 d_3,1¹=min{d_3,1⁰+d_1,1⁰d_3,1⁰}=min{∞+0; ∞}=∞ d_3,2¹=min{d_3,1⁰+d_1,2⁰d_3,2⁰}=min{∞+∞; ∞}=∞ d_3,3¹=min{d_3,1⁰+d_1,3⁰d_3,3⁰}=min{∞+∞; 0}=0 d_3,4¹=min{d_3,1⁰+d_1,4⁰d_3,4⁰}=min{∞+∞; 20}=20 d_3,5¹=min{d_3,1⁰+d_1,5⁰d_3,5⁰}=min{∞+∞; ∞}=∞ d_3,6¹=min{d_3,1⁰+d_1,6⁰d_3,6⁰}=min{∞+∞; 9}=9 d_3,7¹=min{d_3,1⁰+d_1,7⁰d_3,7⁰}=min{∞+∞; ∞}=∞ d_3,8¹=min{d_3,1⁰+d_1,8⁰d_3,8⁰}=min{∞+28; ∞}=∞ d_4,1¹=min{d_4,1⁰+d_1,1⁰d_4,1⁰}=min{∞+0; ∞}=∞ d_4,2¹=min{d_4,1⁰+d_1,2⁰d_4,2⁰}=min{∞+∞; ∞}=∞ d_4,3¹=min{d_4,1⁰+d_1,3⁰d_4,3⁰}=min{∞+∞; ∞}=∞ d_4,4¹=min{d_4,1⁰+d_1,4⁰d_4,4⁰}=min{∞+∞; 0}=0 d_4,5¹=min{d_4,1⁰+d_1,5⁰d_4,5⁰}=min{∞+∞; ∞}=∞ d_4,6¹=min{d_4,1⁰+d_1,6⁰d_4,6⁰}=min{∞+∞; ∞}=∞ d_4,7¹=min{d_4,1⁰+d_1,7⁰d_4,7⁰}=min{∞+∞; 18}=18 d_4,8¹=min{d_4,1⁰+d_1,8⁰d_4,8⁰}=min{∞+28; 15}=15 d_5,1¹=min{d_5,1⁰+d_1,1⁰d_5,1⁰}=min{∞+0; ∞}=∞ d_5,2¹=min{d_5,1⁰+d_1,2⁰d_5,2⁰}=min{∞+∞; ∞}=∞ d_5,3¹=min{d_5,1⁰+d_1,3⁰d_5,3⁰}=min{∞+∞; ∞}=∞ d_5,4¹=min{d_5,1⁰+d_1,4⁰d_5,4⁰}=min{∞+∞; ∞}=∞ d_5,5¹=min{d_5,1⁰+d_1,5⁰d_5,5⁰}=min{∞+∞; 0}=0 d_5,6¹=min{d_5,1⁰+d_1,6⁰d_5,6⁰}=min{∞+∞; 22}=22 d_5,7¹=min{d_5,1⁰+d_1,7⁰d_5,7⁰}=min{∞+∞; ∞}=∞ d_5,8¹=min{d_5,1⁰+d_1,8⁰d_5,8⁰}=min{∞+28; ∞}=∞ d_6,1¹=min{d_6,1⁰+d_1,1⁰d_6,1⁰}=min{∞+0; ∞}=∞ d_6,2¹=min{d_6,1⁰+d_1,2⁰d_6,2⁰}=min{∞+∞; ∞}=∞ d_6,3¹=min{d_6,1⁰+d_1,3⁰d_6,3⁰}=min{∞+∞; ∞}=∞ d_6,4¹=min{d_6,1⁰+d_1,4⁰d_6,4⁰}=min{∞+∞; ∞}=∞ d_6,5¹=min{d_6,1⁰+d_1,5⁰d_6,5⁰}=min{∞+∞; ∞}=∞ d_6,6¹=min{d_6,1⁰+d_1,6⁰d_6,6⁰}=min{∞+∞; 0}=0 d_6,7¹=min{d_6,1⁰+d_1,7⁰d_6,7⁰}=min{∞+∞; 35}=35 d_6,8¹=min{d_6,1⁰+d_1,8⁰d_6,8⁰}=min{∞+28; ∞}=∞ d_7,1¹=min{d_7,1⁰+d_1,1⁰d_7,1⁰}=min{∞+0; ∞}=∞ d_7,2¹=min{d_7,1⁰+d_1,2⁰d_7,2⁰}=min{∞+∞; ∞}=∞ d_7,3¹=min{d_7,1⁰+d_1,3⁰d_7,3⁰}=min{∞+∞; ∞}=∞ d_7,4¹=min{d_7,1⁰+d_1,4⁰d_7,4⁰}=min{∞+∞; ∞}=∞ d_7,5¹=min{d_7,1⁰+d_1,5⁰d_7,5⁰}=min{∞+∞; ∞}=∞ d_7,6¹=min{d_7,1⁰+d_1,6⁰d_7,6⁰}=min{∞+∞; ∞}=∞ d_7,7¹=min{d_7,1⁰+d_1,7⁰d_7,7⁰}=min{∞+∞; 0}=0 d_7,8¹=min{d_7,1⁰+d_1,8⁰d_7,8⁰}=min{∞+28; ∞}=∞ d_8,1¹=min{d_8,1⁰+d_1,1⁰d_8,1⁰}=min{∞+0; ∞}=∞ d_8,2¹=min{d_8,1⁰+d_1,2⁰d_8,2⁰}=min{∞+∞; ∞}=∞ d_8,3¹=min{d_8,1⁰+d_1,3⁰d_8,3⁰}=min{∞+∞; ∞}=∞ d_8,4¹=min{d_8,1⁰+d_1,4⁰d_8,4⁰}=min{∞+∞; ∞}=∞ d_8,5¹=min{d_8,1⁰+d_1,5⁰d_8,5⁰}=min{∞+∞; ∞}=∞ d_8,6¹=min{d_8,1⁰+d_1,6⁰d_8,6⁰}=min{∞+∞; ∞}=∞ d_8,7¹=min{d_8,1⁰+d_1,7⁰d_8,7⁰}=min{∞+∞; ∞}=∞ d_8,8¹=min{d_8,1⁰+d_1,8⁰d_8,8⁰}=min{∞+28; 0}=0 Представим матрицу D¹, включив в нее рассчитанные элементы.

D1=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	∞	∞	42
	∞	∞	0	20	∞	9	∞	∞
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	∞	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0

На основании матрицы D¹, вычислим последовательно все элементы матрицы D². Для этого мы используем рекуррентное соотношение d_i,j²=min{ d_i,2¹+ d_2,j¹; d_i,j¹}. d_1,1²=min{d_1,2¹+d_2,1¹d_1,1¹}=min{∞+14; 0}=0 d_1,2²=min{d_1,2¹+d_2,2¹d_1,2¹}=min{∞+0; ∞}=∞ d_1,3²=min{d_1,2¹+d_2,3¹d_1,3¹}=min{∞+∞; ∞}=∞ d_1,4²=min{d_1,2¹+d_2,4¹d_1,4¹}=min{∞+∞; ∞}=∞ d_1,5²=min{d_1,2¹+d_2,5¹d_1,5¹}=min{∞+31; ∞}=∞ d_1,6²=min{d_1,2¹+d_2,6¹d_1,6¹}=min{∞+∞; ∞}=∞ d_1,7²=min{d_1,2¹+d_2,7¹d_1,7¹}=min{∞+∞; ∞}=∞ d_1,8²=min{d_1,2¹+d_2,8¹d_1,8¹}=min{∞+42; 28}=28 d_2,1²=min{d_2,2¹+d_2,1¹d_2,1¹}=min{0+14; 14}=14 d_2,2²=min{d_2,2¹+d_2,2¹d_2,2¹}=min{0+0; 0}=0 d_2,3²=min{d_2,2¹+d_2,3¹d_2,3¹}=min{0+∞; ∞}=∞ d_2,4²=min{d_2,2¹+d_2,4¹d_2,4¹}=min{0+∞; ∞}=∞ d_2,5²=min{d_2,2¹+d_2,5¹d_2,5¹}=min{0+31; 31}=31 d_2,6²=min{d_2,2¹+d_2,6¹d_2,6¹}=min{0+∞; ∞}=∞ d_2,7²=min{d_2,2¹+d_2,7¹d_2,7¹}=min{0+∞; ∞}=∞ d_2,8²=min{d_2,2¹+d_2,8¹d_2,8¹}=min{0+42; 42}=42 d_3,1²=min{d_3,2¹+d_2,1¹d_3,1¹}=min{∞+14; ∞}=∞ d_3,2²=min{d_3,2¹+d_2,2¹d_3,2¹}=min{∞+0; ∞}=∞ d_3,3²=min{d_3,2¹+d_2,3¹d_3,3¹}=min{∞+∞; 0}=0 d_3,4²=min{d_3,2¹+d_2,4¹d_3,4¹}=min{∞+∞; 20}=20 d_3,5²=min{d_3,2¹+d_2,5¹d_3,5¹}=min{∞+31; ∞}=∞ d_3,6²=min{d_3,2¹+d_2,6¹d_3,6¹}=min{∞+∞; 9}=9 d_3,7²=min{d_3,2¹+d_2,7¹d_3,7¹}=min{∞+∞; ∞}=∞ d_3,8²=min{d_3,2¹+d_2,8¹d_3,8¹}=min{∞+42; ∞}=∞ d_4,1²=min{d_4,2¹+d_2,1¹d_4,1¹}=min{∞+14; ∞}=∞ d_4,2²=min{d_4,2¹+d_2,2¹d_4,2¹}=min{∞+0; ∞}=∞ d_4,3²=min{d_4,2¹+d_2,3¹d_4,3¹}=min{∞+∞; ∞}=∞ d_4,4²=min{d_4,2¹+d_2,4¹d_4,4¹}=min{∞+∞; 0}=0 d_4,5²=min{d_4,2¹+d_2,5¹d_4,5¹}=min{∞+31; ∞}=∞ d_4,6²=min{d_4,2¹+d_2,6¹d_4,6¹}=min{∞+∞; ∞}=∞ d_4,7²=min{d_4,2¹+d_2,7¹d_4,7¹}=min{∞+∞; 18}=18 d_4,8²=min{d_4,2¹+d_2,8¹d_4,8¹}=min{∞+42; 15}=15 d_5,1²=min{d_5,2¹+d_2,1¹d_5,1¹}=min{∞+14; ∞}=∞ d_5,2²=min{d_5,2¹+d_2,2¹d_5,2¹}=min{∞+0; ∞}=∞ d_5,3²=min{d_5,2¹+d_2,3¹d_5,3¹}=min{∞+∞; ∞}=∞ d_5,4²=min{d_5,2¹+d_2,4¹d_5,4¹}=min{∞+∞; ∞}=∞ d_5,5²=min{d_5,2¹+d_2,5¹d_5,5¹}=min{∞+31; 0}=0 d_5,6²=min{d_5,2¹+d_2,6¹d_5,6¹}=min{∞+∞; 22}=22 d_5,7²=min{d_5,2¹+d_2,7¹d_5,7¹}=min{∞+∞; ∞}=∞ d_5,8²=min{d_5,2¹+d_2,8¹d_5,8¹}=min{∞+42; ∞}=∞ d_6,1²=min{d_6,2¹+d_2,1¹d_6,1¹}=min{∞+14; ∞}=∞ d_6,2²=min{d_6,2¹+d_2,2¹d_6,2¹}=min{∞+0; ∞}=∞ d_6,3²=min{d_6,2¹+d_2,3¹d_6,3¹}=min{∞+∞; ∞}=∞ d_6,4²=min{d_6,2¹+d_2,4¹d_6,4¹}=min{∞+∞; ∞}=∞ d_6,5²=min{d_6,2¹+d_2,5¹d_6,5¹}=min{∞+31; ∞}=∞ d_6,6²=min{d_6,2¹+d_2,6¹d_6,6¹}=min{∞+∞; 0}=0 d_6,7²=min{d_6,2¹+d_2,7¹d_6,7¹}=min{∞+∞; 35}=35 d_6,8²=min{d_6,2¹+d_2,8¹d_6,8¹}=min{∞+42; ∞}=∞ d_7,1²=min{d_7,2¹+d_2,1¹d_7,1¹}=min{∞+14; ∞}=∞ d_7,2²=min{d_7,2¹+d_2,2¹d_7,2¹}=min{∞+0; ∞}=∞ d_7,3²=min{d_7,2¹+d_2,3¹d_7,3¹}=min{∞+∞; ∞}=∞ d_7,4²=min{d_7,2¹+d_2,4¹d_7,4¹}=min{∞+∞; ∞}=∞ d_7,5²=min{d_7,2¹+d_2,5¹d_7,5¹}=min{∞+31; ∞}=∞ d_7,6²=min{d_7,2¹+d_2,6¹d_7,6¹}=min{∞+∞; ∞}=∞ d_7,7²=min{d_7,2¹+d_2,7¹d_7,7¹}=min{∞+∞; 0}=0 d_7,8²=min{d_7,2¹+d_2,8¹d_7,8¹}=min{∞+42; ∞}=∞ d_8,1²=min{d_8,2¹+d_2,1¹d_8,1¹}=min{∞+14; ∞}=∞ d_8,2²=min{d_8,2¹+d_2,2¹d_8,2¹}=min{∞+0; ∞}=∞ d_8,3²=min{d_8,2¹+d_2,3¹d_8,3¹}=min{∞+∞; ∞}=∞ d_8,4²=min{d_8,2¹+d_2,4¹d_8,4¹}=min{∞+∞; ∞}=∞ d_8,5²=min{d_8,2¹+d_2,5¹d_8,5¹}=min{∞+31; ∞}=∞ d_8,6²=min{d_8,2¹+d_2,6¹d_8,6¹}=min{∞+∞; ∞}=∞ d_8,7²=min{d_8,2¹+d_2,7¹d_8,7¹}=min{∞+∞; ∞}=∞ d_8,8²=min{d_8,2¹+d_2,8¹d_8,8¹}=min{∞+42; 0}=0 Представим матрицу D², включив в нее рассчитанные элементы.

D2=	0	∞	∞	∞	∞	∞	∞	28
	14	0	∞	∞	31	∞	∞	42
	∞	∞	0	20	∞	9	∞	∞
	∞	∞	∞	0	∞	∞	18	15
	∞	∞	∞	∞	0	22	∞	∞
	∞	∞	∞	∞	∞	0	35	∞
	∞	∞	∞	∞	∞	∞	0	∞
	∞	∞	∞	∞	∞	∞	∞	0