ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Теорія алгоритмів і математичні основи представлення знань

Теорія алгоритмів і математичні основи представлення знань

МЕТОДИЧНІ ВКАЗІВКИ

ДО ЛАБОРАТОРНИХ РОБІТ

 

 

Вступ

Одним із значних досягнень науки XX століття є теорія алгоритмів –нова математична дисципліна.

Теорія ЕОМ, практика програмування не можуть обійтись без теорії алгоритмів.

Теорія алгоритмів – це самостійна наука, яка має свій предмет. Предметом теорії алгоритмів є алгоритми.

Слово алгоритм походить від імені узбецького математика Хорезми ( по арабськи ал-Хорезми). Цей математик у IX столітті н. е. розробив правила 4-х дій над числами в десятковій системі числення. Сукупність цих правил у Європі стала називатись "алгоризм".

В 30-х роках ХХ ст. поняття алгоритм стало об’єктом математичного вивчення.Розвиток ЕОМ і методів програмування прискорив розвиток теорії алгоритмів, як необхідного засобу автоматизації. Але і в 1-му і в 2-му напрямках ТА треба дати поняття алгоритму. Тому перейдемо до інтуїтивного поняття алгоритму з його властивостями, прикладами й недоліками.

Інтуїтивне поняття алгоритму

Приклади деяких алгоритмів, із якими ми зустрічаємось у житті:

- у книгах рецептів приготування різних блюд;

- в довідниках аптечних рецептів для приготування ліків.

Приклади найпростіших алгоритмів із математики:

- правила оперування з десятковими числами (складання, віднімання, множення, ділення);

- правила оперування з комплексними числами;

- алгоритми розв’язання квадратичних рівнянь, систем рівнянь та інш.

Кожна наукова й технічна дисципліна має довідники. Такі довідники в значній своїй частині – це збірник алгоритмів, накопичених даною науковою або технічною дисципліною. Особливе значення мають алгоритми, накопичені в математиці, бо надбання математики є багатством усіх наук.

Алгоритм– це сукупність правил, які визначають процес переробки допустимих початкових даних у вихідні результати.

Дане поняття алгоритму має такі властивості або загальні риси, характерні для поняття алгоритму.

1. Дискретність:

алгоритм виконується по кроках у дискретному часі.

2. Детермінованість:

система величин, яка отримана на якомусь кроці алгоритму, однозначно визначається системою величин, отриманих на попередньому кроці алгоритму.

3. Елементарність:

закон одержання системи величин на кожному кроці алгоритму із системи величин на попередніх кроках повинен бути простим.

4. Направленість:

ця властивість передбачає, що виконання алгоритмів повинне завершуватись одержанням певних результатів.

Якщо ж спосіб одержання наступної величини не дає результату, то слід указати, що вважати результатом алгоритму.

5. Масовість:

Початкова система величин може вибиратись із потенціально нескінченної множини величин.

Таке поняття алгоритму не строге, не точне, бо воно включає слова: правило, спосіб, величина, точний зміст яких не встановлено, хоч інтуїтивно зрозуміло зміст цих слів.

Алгоритмічна система – система, яка дає чітке поняття, визначення алгоритму, задає загальний спосіб побудови алгоритмів.

Рекурсивні функції

Теза Черча

Клас алгоритмічно (або машинно) обчислюваних часткових числових функцій співпадає з класом усіх частково рекурсивних ф-цій.

 

Теза Черча являється гіпотезою. Вона зв’язує неточне інтуїтивне поняття алгоритму, обчислюваної ф-ції з точним математичним поняттям частково рекурсивної ф-ції.

Розмитість тези не дозволяє довести її, але на користь її справедливос-ті говорять багато чітко доведених тверджень.

Тобто є достатньо вагомих підстав прийняти тезу Черча як основу теорії алгоритмів.

 

Лабораторна робота №1

Тема. Примітивно і частково рекурсивні функції та їх властивості.

Мета. Засвоїти основні поняття (Cхема примітивної рекурсії, примітивно рекурсивні функції.Операція мінімізації.Частково рекурсивні функції, .)

Завдання.

1 Встановлення примітивної рекурсивності функцій (побудова схем примітивної рекурсії):

а) f(x) = n;

в) f(x) = nx,

де n- порядковий номер студента в журналі.

2 Побудувати 2 функції із ф-ції g(x) = n взяттям обмеженої суми і обмеженого добутку і встановити примітивну рекурсивність побудованих функцій.

3 Для заданої примітивно рекурсивної ф-ції g(x) =(x + n)2,

побудувати частково рекурсивну функцію за допомогою операції мінімізації.

 

Приклад виконання завдання

Варіант 37. Виконав студент групи ЗІТ-***. Дата ***.

1Нехай n=5

а) f(x) = 5;

Треба використати елементарні арифметичні функції: нуль функцію О(х) = 0; функцію безпосереднього слідування S(x) = x +1 та операцію підстановки. Тоді

f(x) = S(S(S(S(S(О(х))))))=5; тобто ця функція є ПРФ.

Позначимо її const5(x)=5.

в)f(x) = 5·x.

Покажемо, що ця функція є ПРФ.

Функцію product(x,y)=x·y можна одержати з функцій О(х) та

h(x,y,z)=z+x операцією примітивної рекурсії. Справді,

product(x,0)=0=О(х) ;

product(x,y+1)=x·(y+1)= x·y+x=product(x,y)+x.

Оскільки функція sum(x,y)=x+y) є ПРФ , а функція h(x,y,z)=z+x як різновид функції sum(x,y) з фіктивним аргументом у є теж ПРФ , тоді функцію f(x) = 5·x.можна представити як

f(x) = product(x,const5(x)).

Отже ця функція –ПРФ.

2 Нехай g(x) = 5.

а)Побудуємо функцію із ф-ції g(x) = 5 взяттям обмеженої суми і обмеженого добутку

у у f(у) = S g (i) = S 5 = 5(у+1) (1) i=0 i=0 Ця функція є ПРФ як .функція отримана із ПРФ взяттям обмеженої суми  

в) Побудуємо функцію із ф-ції g(x) = 5 взяттям обмеженого добутку

у у f(у) = Õ g (i) = Õ 5 = 5у+1 (1) i=0 i=0 Ця функція є ПРФ як .функція отримана із ПРФ взяттям обмеженого добутку  

3Нехай задана ф-ція g(x) = ( x+1)2 - ПРФ

Допустимі значення аргументу x: 0, 1, 2,…

Введем допоміжний аргумент у і розглянемо рівняння g(y) = х, тобто (у+1)2 = х

Зафіксуємо допустимі значення основного аргументу х у таблиці 2.

 

Таблиця 2

х Рівняння Корінь рівняння mу((у+1)2 = х) f(x) побудо- вана ф-ція Отримане значення кореня рівняння будемо приймати за значення ф-ції, яку ми будуємо. Це значення ф-ції відповідає зафіксованому значенню х  
(у+1)2 = 0 нема 0 ® не визначене
(у+1)2 = 1 1® 0
(у+1)2 = 2 нема 2® не визначене
(у+1)2 = 3 нема 3 ® не визначене
(у+1)2 = 4 4® 1
(у+1)2 = 5 нема 5 ® не виз-не
(у+1)2 = 6
(у+1)2= 7 нема 7 ® не виз-не
(у+1)2= 8 нема 8 ® не виз-не
(у+1)2= 9 9 ® 2

 

Аналітичний вираз побудованої ф-ції f(x)

 
 


f(x) =

√х -1, для х=k2, де kÎN0, х ³1;
не визначена, для інших допустимих значень х.

 

1.3 Контрольні питання

 

1 Інтуітивне поняття алгоритму.

2 Приклади алгоритмів.

3 Властивості алгоритмів.

4 Що таке рекурсія.

5 Елементарні арифметичні функції.

6 Операції:

підстановки (суперпозиції);

примітивної рекурсії;

мінімізації.

7 Взяття обмеженої суми, обмеженого добутку.

8 Що таке примітивно рекурсивні ф-ції

9 Що таке частково рекурсивні ф-ції .

10 Теза Черча.

 

Нормальні алгоритми Маркова

Принцип нормалізації

Будь-який алгоритм над скінченим алфавітом А являється еквівалентним відносно А деякому нормальному алгоритму Маркова над А.

 

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

 

2.2 Лабораторна робота №2

Тема. Нормальні алгоритми Маркова та їх властивості.

Мета. Засвоїти основні поняття стосовно алгоритмічної системи нормальні алгоритми Маркова (НАМ).

 

Завдання.

1 Нехай n порядковий номер студента в журналі. Нехай

m визначається так:

10, якщо n =1;

m= n якщо 1£ n £ 10;

остача від ділення n на 10, збільшена на одиницю.

 

Створити нормальний алгоритм Маркова Um для обчислення функції S(x) = x + 1, якщо х – число записане в m- значній системі числення.

2 Застосувати Um для обчислення S(n), (де n порядковий номер), попередньо перевівши цей порядковий номер у m- значну систему числення.

3 Побудувати нормальний алгоритм Маркова, який перетворює кожне натуральне число, записане в алфавіті А= {|} в частку від ділення цього числа на n, записану в тому самому алфавіті.

4 Побудувати нормальний алгоритм Маркова U, який є композицією двох нормальних алгоритмів Маркова U1 і U2 , при чому:

U1 - збільшує кожне натуральне число, записане в алфавіті А= {|} на число t1;

U2 - збільшує кожне натуральне число, записане в алфавіті А= {|} на число t2;

де t1 та t2 – перша і друга цифра, відповідно,

числа:

n + 30 (для БІТ1-**, ЗІТ1-***); при n ¹40, n ¹50, n ¹60.

n + 40 (для БІТ2-**, ЗІТ2-***); при n ¹50, n ¹60, n ¹70.

n + 50 (для БІТ3-**, ЗІТ3-***); при n ¹60, n ¹70, n ¹80.

n + 60 (для БІТ4-**, ЗІТ4-***); при n ¹70, n ¹80, n ¹90.

t1= 1, t2 = 2 при n = 40;

t1= 2, t2 = 3 при n = 50;

t1= 3, t2 = 4 при n = 60.

t1= 4, t2 = 5 при n = 70.

t1= 5, t2 = 6 при n = 80.

t1= 6, t2 = 7 при n = 90.

 

Приклад виконання завдання

Варіант 37. Виконав студент групи ЗІТ-***. Дата ***.

 

1 Створимо НАМ U5 для обчислення ф-ції S(x) = x + 1, коли х записано в 5-значній системі числення. НАМ U5 запишемо у вигляді 3-х стовпчиків формул підстановок

 

1) *0 ® 0* 6) 0* ® ·1 11) 0у ® ·1
2) *1 ® 1* 7) 1* ® ·2 12) 1у ® ·2
3) *2 ® 2* 8) 2* ® ·3 13) 2у ® ·3
4) *3 ® 3* 9) 3* ® ·4 14) 3у ® ·4
5) *4 ® 4* 10) 4* ®у0 15) 4у ® у0
    16) у® ·1
    17) ®*

 

2 Застосуємо U5 для обчислення S(n), (де n=2410), попередньо перевівши цей порядковий номер у 5- значну систему числення

( n=445). Протокол застосування U5 ( в дужках вкажемо номер застосованої підстановки) :

44 (17)

*44 (5)

4*4 (5)

44* (10)

*4у4 (15)

у00 (16)

100 (17)

 

Um (445)=1005=2510..

 

3 Побудуємо нормальний алгоритм Маркова, який перетворює кожне натуральне число, записане в алфавіті А= {|} в частку від ділення цього числа на 3, записану в тому самому алфавіті.

f 1) *III ® I* 2) *I ® * 3) * ® · 4) ® *

 

4 Побудуємо нормальний алгоритм Маркова U, який є композицією двох нормальних алгоритмів Маркова U1 і U2 , при чому:

U1 - збільшує кожне натуральне число, записане в алфавіті А= {|} на число 2;

U2 - збільшує кожне натуральне число, записане в алфавіті А= {|} на число 1;

1) * ® II

2) ® ·I

3) ® *

 

2.3 Контрольні питання

1 Алгоритмічна система нормальні алгоритми Маркова (НАМ).

2 Поняття функції обчислюваної за Марковим.

3 Побудова НАМ для нуль – функції, ф-ції безпосереднього слідування, селекторної ф-ції.

4 Поняття еквівалентних відносно алфавіту А нормальних алгоритмів Маркова

5 Композиція НАМ. Приклад.

6 Розгалуження двох НАМ під керуванням третього. Приклад.

7 З’єднання НА. Приклад.

8 Повторення одного НА під керування іншого. Приклад.

9 Принцип нормалізації.

 

Машина Тьюрінга

Cуперпозиція машин Тьюрінга

З математичної точки зору МТ – це просто визначений алгоритм для переробки слів.

Кожна МТ забезпечує знаходження значення деякої словникової функції в алфавіті А

fMT: S(A), де S(A) – множина слів А.

Тому природно ввести операцію суперпозиції МТ. Ця операція суперпозиції МТ буде еквівалентна суперпозиції функцій, що

представляють ці МТ.

 

Нехай МТ М1 обчислює ф-цію f1(w) в алфавіті А. А = {a1, …, an}
М2 обчислює ф-цію f2(w) в алфавіті А.
Значення суперпозиції f2(f1(w)) визначене тоді і тільки тоді, коли визначена ф-ція f1(w) і визначено значення ф-ції f2 на слові f1(w).
Побудуємо МТ М, яка буде суперпозицією машин М1 і М2 і обчислює суперпозицію f2(f1(p)).
Програма для обчислення суперпозиції f2(f1(p)) являється об’єднанням програм для обчислення ф-цій f1 і f2.
Початковий стан МТ М2 повинен збігатися із заключним станом МТ М1. Усі стани М2, крім початкового, повинні відрізнятися від станів М1.

 

Після перетворення програми М2, програми М1 та М2 об'єднуються в одну таблицю-програму МТ М.
Початковим станом М стає початковий стан М1 Заключним станом М стає заключний стан М2 Суперпозицію М машин М1 і М2 будемо позначати М2 ° М1. Як змінити стан МТ М2 ? Треба всі номери станів крім початкового збільшити на число, що збігається з номером заключного стану М1

 

Можливість будувати МТ за допомогою суперпозиції, розгалуження, циклів приводять до думки, що мова Тьюрінговського програмування дозволяє реалізувати будь-який алгоритм (в інтуітивному розумінні).

Теза Тьюрінга

Класи обчислюваних і обчислюваних за Тьюрінгом функцій збігаються.

Довести тезу Тьюрінга, як і тезу Черча, неможливо, оскільки саме поняття алгоритму (в інтуітивному розумінні) є неточним. Це не теорема і не постулат математичної теорії. Це твердження, яке пов'язує теорію з тими об'єктами, для опису яких її створено.

Підтвердженням тези Тьюрінга є,

- по перше математична практика;

- по друге, той факт, що опис алгоритму у термінах будь-якої іншої відомої алгоритмічної моделі може бути зведений до його опису у вигляді МТ.

 

Лабораторна робота №3

Тема. Машина Тьюрінга (МТ) та їх властивості.

Мета. Засвоїти основні поняття алгоритмічної системи Машина Тьюрінга.

Завдання.

1 Застосувати МТ, яка реалізує функцію S(x) = x +1 в алфавіті A = {|,0,1} для обчислення S(n), (де n порядковий номер студента в журналі), попередньо перевівши цей порядковий номер у 2-кову систему числення.

2 Створити МТ для обчислення функції Imn1, х2, ..хm,.. хn) =хm ,

якщо х1, х2, ..хm,.. хn – числа записані в алфавіті A = {|}, а між числами х1, х2, ..хm, ..хn ставиться *, де m визначається так:

10, якщо n =1;

m= n якщо 1£ n £ 10;

остача від ділення n на 10, збільшена на одиницю.

3 Створити машину Тьюрінга , яка переводить будь-яке натуральне число, записане в алфавіті A = {|}, в запис цього числа в m – значній системі числення.

4 Створити МТ, яка перетворювала б будь-яке натуральне число k,

записане в алфавіті A = {|} в число k+m, де m –визначене в пункті 2.

Приклад виконання завдання

Варіант 37. Виконав студент групи ЗІТ-***. Дата ***.

1 Застосуємо МТ, яка реалізує функцію S(x) = x +1 в алфавіті

A = {|,0,1} для обчислення S(n), (де n порядковий номер студента в журналі), попередньо перевівши цей порядковий номер у 2-кову систему числення. Нехай n=210 =102 .Тоді S(102 )=112. Нижче наведем програму МТ та протокол роботи МТ. Символ {!}

означає зупинку МТ.

 

  Стан МТ
Символ q0 q1 q2
# #q1L 1q2L  
0q0R 1q2L  
1q0R 0q1L !

 

Протокол МТ  
1) # 1 0 #
q0
2) # 1 0 #
q0
3) # 1 0 #
q0
4) # 1 0 #
q1
5) # 1 1 #
q2
 

 

2 Створимо МТ для обчислення функції I451, х2, х3, х4, х5) = х4 , якщо х1, х2, х3, х4, х5 – числа записані в алфавіті A = {|}, а між числами х1, х2, х3, х4, х5 ставиться *.

 

  Стан МТ
Символ q0 q1 q2 q3 q4 q5
| |q1L #q1R #q2 R #q2 R |q4R #q5R
*   #q2R #q3 R   #q5R  
# #q1R         !

 

3 Створимо машину Тьюрінга , яка переводить будь-яке натуральне число, записане в алфавіті A = {|} в запис цього числа в 4 – значній системі числення. Головка МТ нехай стоїть спочатку проти правого крайнього символу {|} в стані q0.

 

  Q (Стан МТ)
A Символ q0 q1 q2
| #q1 L |q1L |q2R
# ! 1q2 S #q0L
! 1q2 S 0q2R
! 2q2 S 1q2R
! 3q2 S 2q2R
! 0q1 L 3q2R

 

4 Створимо МТ, яка перетворювала б будь-яке натуральне число k, записане в алфавіті A = {|} в число k+3. Головка МТ нехай стоїть спочатку проти лівого крайнього символу {|} в стані q0.

 

  Стан МТ
Символ q0 q1 q2 q3
| |q0R      
# |q1R |q2R |q3R !

 

 

3.3 Контрольні питання

 

1 Алгоритмічна система Машина Тьюрінга (МТ).

2 Поняття функції обчислюваної за Тьюрінгом.

3 Суперпозиція МТ.

4 Розгалуження МТ.

5 Теза Тьюрінга .

6 Еквівалентність теорій (МТ, нормальних алгоритмів Маркова та ЧРФ).

7 Поняття про алгоритмічно розв′язувані проблеми та алгорит-мічно нерозв′язувані проблеми.

8 Проблема зупинки МТ.

9 Проблема розпізнавання самозастосовності МТ.

10 Проблема еквівалентності слів для асоціативних числень.

Лабораторна робота №4

Тема. Логіка висловлень

Мета. Засвоїти основні поняття логіки висловлень

Завдання.

1Користуючись таблицями істинності довести тотожну істинність формули логіки висловлень під № n ( Варіант формули, згідно з порядковим номером n студента в журналі див. у Додатку 1).

2 Записати формулу під № m із Додатку 1, користуючись тільки логічними операціями (Ø, Ù), де .m = 33- n.

3 Користуючись формулами логіки висловлень під № 1-14 із Додатку 1,перетворити складне висловлення із завдання № 2 (яке містить тільки логічні операції (Ø, Ù)) так, щоб рівносильне йому висловлення містило заперечення лише простих висловлень.

4 За методом Куайна довести тотожну істинність формули логіки висловлень із завдання № 3.

Приклад виконання завдання

1 Користуючись таблицями істинності доведемо тотожну істинність формули логіки висловлень :

1) (А®В) Ú (В®А)

 

А ® В Ú В ® А

 

2 Запишемо формулу логіки висловлень, користуючись тільки логічними операціями (Ø, Ù).

       
   
 


~

 

 

 

3 Користуючись формулами логіки висловлень під № 1-14 із Додатку 1,перетворимо складне висловлення із завдання № 2 (яке містить тільки логічні операції (Ø, Ù)) так, щоб рівносильне йому висловлення містило заперечення лише простих висловлень.

 

 
 

 


4 За методом Куайна довести тотожну істинність формули логіки висловлень із завдання № 3. Скористаємося тим, що МÚØМº1, а формула МÙØМ є суперечністю, тобто МÙØМº0

 
 

 


Контрольні питання

1 Що називається простим висловленням або атомом?

2 Як будувати правильно побудовані формули (ППФ)Приклад

3 Яка формула називається тавтологією, суперечністю .Приклади.

4 Рівносильні формули.

5 Повні системи логічних зв'язок. Приклад .

6 Відновлення формул за таблицями істинності.

7 Визначення числення висловлювань як аксіоматичної теорії.

8 Приклад виведення теореми із посилок ( гіпотез) в численні висловлювань .

9 Методи перевірки тавтологічності формул числення висловлю-вань (метод Куайна).

10 Теорема дедукції.

11 Зв'язок між тавтологіями та теоремами числення висловлень.

12 Несуперечність числення висловлень.

Математична логіка.

Лабораторна робота №5

Тема. Логіка предикатів 1-го порядку.

Мета. Засвоїти основні поняття (Поняття n-місного предикату. Квантори загальності та існування. Вільні та зв'язані змінні. Алфавіт та формули логіки предикатів . Інтерпретація формул логіки предикатів . Загальнозначимі формули логіки предикатів . Рівносильні перетворення формул з кванторами. Нормальні форми формул логіки предикатів 1-го порядку).

Завдання.

1 Нехай ("x) А12(f11(x), n) Ù ($x) А22(f21(x), n) формула логіки предикатів 1-го порядку(де n порядковий номер студента в журналі). Розглянути 2 інтерпретації формули. В 1-й інтерпретації значення формули повинно бути "істина", а в 2-й інтерпретації - "хибність"

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

3 Формулу із 2-го завдання перетворити у таку рівносильну їй формулу в заданій інтерпретації, яка не містила б операцій заперечення.

4 Побудувати попередню нормальну форму для формули із 1-го завдання.

 

Приклад виконання завдання

1 Нехай ("x) А12(f11(x), а1) Ù ($x) А22(f21(x), а1) формула логіки предикатів 1-го порядку . Розглянемо 2 інтерпретації формули. В 1-й інтерпретації значення формули повинно бути "істина", а в 2-й інтерпретації - "хибність"

Перша інтерпретація D = R; а1=37, f11(x)=| х |+37,

А12(f1(x), а1) =" f11(x) ³ а1".

f21(x)=x2 , А22(f21(x), а1) =" f21(x)= а1"

Отримане висловлення ("x) ( | х |+37 ³37) Ù ($x) (x2 =37) є істинним.

Друга інтерпретація D = N; a1=37, f11(x)=sinx,

А12(f11(x), а1) = " f11(x) > а1".

f21(x)=Öx , А22(f21(x), а1) =" f21(x)= а1"

Отримане висловлення ("x) ( sinx >37) Ù ($x) (Öx =37) є хибним.

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

Ø(("x) А12(f11(x), а1) Ù ($x) А22(f21(x), а1)) º

($x) ØА12(f11(x), а1) Ú ("x) ØА22(f21(x), а1)

Інтерпретація D = R; а1=37, f11(x)=cosх,

А12(f1(x), а1) = " f11(x) > а1".

f21(x)=x, А22(f21(x), а1) =" f21(x)= а1"

Отримане висловлення (існує х, для якого не виконується нерівність cosх < 37, або для будь-якого х не виконується рівність х=37) є хибним.

 

3 Формулу із 2-го завдання перетворимо у таку рівносильну їй формулу в заданій інтерпретації, яка не містила б операцій заперечення.

Отримане висловлення (існує х, для якого виконується нерівність cosх ³ 37, або для будь-якого х виконується нерівність х¹37)є хибним.

 

4 Побудуємо попередню нормальну форму для формули із 1-го завдання.

("x) А12(f11(x), а1) Ù ($x) А22(f21(x), а1) º

("x) А12(f11(x), а1) Ù ($y) А22(f21(y), а1) º

("x) ($y)(А12(f11(x), а1) Ù А22(f21(y), а1)).

 

6.3 Контрольні питання

1 Логіка предикатів .

2 Поняття n-місного предикату.

3 Квантори загальності та існування. Вільні та зв'язані змінні.

4 Алфавіт логіки предикатів .

5 Формули логіки предикатів .

6 Інтерпретація формул логіки предикатів .

7 Загальнозначимі формули логіки предикатів .

8 Рівносильні перетворення формул з кванторами.

9 Правило побудови заперечення формул з кванторами.

10 Нормальні форми формул логіки предикатів 1-го порядку.

11 Аксіоми та правила виведення числення (логіки) предикатів 1-го порядку.

12 Виведення формул в численні предикатів 1-го порядку на прикладі.

13 Основні властивості числення предикатів 1-го порядку.

14 Несуперечність числення предикатів 1-го порядку.

15 Теорема дедукції для числення предикатів 1-го порядку.

16 Зв'язок між тавтологіями числення висловлювань та загальнозначимими формулами числення предикатів 1-го порядку.

 


Література

1 Кривий С.Л. Теорія алгоритмів і математичні основи представлення знань. Конспект лекцій. – К.: ДАЛПУ 1999.

2 Алгоритмы вокруг нас. Криницкий Н.А. – М.: Наука. 1984.

224 с.

3 Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. –К: Наукова думка. 2002.-579 с.

4 Дискретна математика: Підручник / Ю. М. Бардачов , Н. А. Соколова, В. Е. Ходаков; за ред. В. Е. Ходакова. – К.: Вища шк., 2002. –287 с.: іл.

5 Донской В.И. Дискретная математика.-Симферополь: Издательство "СОНАТ" , 2000. –360 с Илл.45.

6 А. Ахо, Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир. 1979. – 536 с.

7 Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика. – М.: Мир. 1980. – 476 с.

8 А. Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. – М.: Вильямс. 2000.

9 Искусственный интеллект. – В 3-х кн. Кн. 2. Модели и методы: Справочник / Под ред. Д.А. Поспелова. – М. : Радио и связь, 1990. – 304 с.

 

Зміст  
Вступ
1 Рекурсивні функції
1.1 Теоретичні поняття і визначення…………………………
1.2 Лабораторнаробота№1……………………………………
1.3 Контрольні питання………………………………...
2 Нормальні алгоритми Маркова
2.1 Теоретичні поняття і визначення………
2.2 Лабороторна робота №2……………………………………...
2.3 Контрольні питання………………………………..
3 Машина Тьюрінга ………………….
3.1 Теоретичні поняття і визначення
3.2 Лабороторна робота №3………………………………..
3.3 Контрольні питання
4 Еквівалентність алгоритмічних систем
5 Математична логіка. Логіка висловлень
5.1 Теоретичні поняття і визначення
5.2 Лабораторна робота №4
5.3 Контрольні питання
6 Математична логіка. Логіка предикатів 1-го порядку
6.1 Теоретичні поняття і визначення
6.2 Лабораторна робота №5
6.3 Контрольні питання
Додаток 1. Тотожно істинні формули логіки висловлень
Література

 

Теорія алгоритмів і математичні основи представлення знань

МЕТОДИЧНІ ВКАЗІВКИ

ДО ЛАБОРАТОРНИХ РОБІТ

 

 

Вступ

Одним із значних досягнень науки XX століття є теорія алгоритмів –нова математична дисципліна.

Теорія ЕОМ, практика програмування не можуть обійтись без теорії алгоритмів.

Теорія алгоритмів – це самостійна наука, яка має свій предмет. Предметом теорії алгоритмів є алгоритми.

Слово алгоритм походить від імені узбецького математика Хорезми ( по арабськи ал-Хорезми). Цей математик у IX столітті н. е. розробив правила 4-х дій над числами в десятковій системі числення. Сукупність цих правил у Європі стала називатись "алгоризм".

В 30-х роках ХХ ст. поняття алгоритм стало об’єктом математичного вивчення.Розвиток ЕОМ і методів програмування прискорив розвиток теорії алгоритмів, як необхідного засобу автоматизації. Але і в 1-му і в 2-му напрямках ТА треба дати поняття алгоритму. Тому перейдемо до інтуїтивного поняття алгоритму з його властивостями, прикладами й недоліками.

Інтуїтивне поняття алгоритму

Приклади деяких алгоритмів, із якими ми зустрічаємось у житті:

- у книгах рецептів приготування різних блюд;

- в довідниках аптечних рецептів для приготування ліків.

Приклади найпростіших алгоритмів із математики:

- правила оперування з десятковими числами (складання, віднімання, множення, ділення);

- правила оперування з комплексними числами;

- алгоритми розв’язання квадратичних рівнянь, систем рівнянь та інш.

Кожна наукова й технічна дисципліна має довідники. Такі довідники в значній своїй частині – це збірник алгоритмів, накопичених даною науковою або технічною дисципліною. Особливе значення мають алгоритми, накопичені в математиці, бо надбання математики є багатством усіх наук.

Алгоритм– це сукупність правил, які визначають процес переробки допустимих початкових даних у вихідні результати.

Дане поняття алгоритму має такі властивості або загальні риси, характерні для поняття алгоритму.

1. Дискретність:

алгоритм виконується по кроках у дискретному часі.

2. Детермінованість:

система величин, яка отримана на якомусь кроці алгоритму, однозначно визначається системою величин, отриманих на попередньому кроці алгоритму.

3. Елементарність:

закон одержання системи величин на кожному кроці алгоритму із системи величин на попередніх кроках повинен бути простим.

4. Направленість:

ця властивість передбачає, що виконання алгоритмів повинне завершуватись одержанням певних результатів.

Якщо ж спосіб одержання наступної величини не дає результату, то слід указати, що вважати результатом алгоритму.

5. Масовість:

Початкова система величин може вибиратись із потенціально нескінченної множини величин.

Таке поняття алгоритму не строге, не точне, бо воно включає слова: правило, спосіб, величина, точний зміст яких не встановлено, хоч інтуїтивно зрозуміло зміст цих слів.

Алгоритмічна система – система, яка дає чітке поняття, визначення алгоритму, задає загальний спосіб побудови алгоритмів.

Рекурсивні функції

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти