5675

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

Конспект

Информатика, кибернетика и программирование

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

Украинкский

2012-12-17

339 KB

104 чел.

ЛЕКЦІЯ 1. Вступ. Інтуїтивне поняття алгоритму.

Поняття алгоритму інтуїтивно зрозуміло і часто використовується в математиці. Додавання і множення чисел “стовпчиком”, що відомо ще зі школи, формула обчислення коренів квадратного рівняння, перемножування двох матриць за правилом “рядок на стовпець” є алгоритмами. Безліч прикладів можна продовжити. У сучасній практиці під алгоритмом часто розуміють програму, а критерієм існування алгоритму вважають можливість його запрограмувати. Однак це не зовсім так. Спочатку дамо поняття алгоритму.

Під алгоритмом розуміють точне розпорядження про виконання у визначеному порядку точно зазначеної послідовності операцій для рішення всіх задач з даного класу задач.

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

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

Дискретність інформації. Кожен алгоритм має справа з даними – вхідними, проміжними і вихідними. Ці дані представляються у виді у виді кінцевих слів у деякому алфавіті.

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

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

Скінченність алгоритму. Скінченність  алгоритму означає, що опис алгоритму повинен бути скінченим. Крім цього, робота самого алгоритму також повинна бути кінцева, тобто після кінцевого числа кроків алгоритм повинний закінчувати свою роботу. Для програм, зокрема це означає, що алгоритм не повинний “зацикливаться”. Робота алгоритму завершується видачею результату. Тому кінцівка алгоритму тісно зв'язана з його результативністю: здатністю видавати результат.

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

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

Алфавіти і слова

Означення 1. Будемо називати довільну кінцеву множину алфавітом А, а елементи цієї множини буквами алфавіту А. Тоді довільні кінцеві послідовності букв називаються словами в даному алфавіті.

Любою алфавіт містить порожній символ. Будемо позначати його символом (. Порожній символ є і порожнім словом.

Безліч слів алфавіту А будемо позначати А*.

Визначення 1. Кількість букв у слові називається його довжиною і позначається вертикальними дужками. Наприклад, довжина слова аааа дорівнює |аааа | = 4, довжина порожнього слова |  | = 0.

Основною операцією над словами є конкатенація.

Визначення 2. Конкатенацією двох слів P і Q назвемо слово, отримане дописуванням слова Q після P: PQ.

Наприклад, конкатенація слів aab і ba є слово aabba. Операція конкатенації некоммутативна, але ассоциативна.

Визначення 3. Якщо x - деяке слово алфавіту A і якщо x представимо у виді конкатенації PQ, те P і Q називають подсловами слова x.

Наприклад, слово abb містить подслова a, b, ab, bb. Якщо x A* і x = P1QP2QP3, то говорять про першому, другому і т.д. входження слова Q у слово x. Слова, складені з послідовності однакових букв, будемо іноді записувати аааbb = a3b2, де ступінь позначає кількість входжень букви в слово.

Кодування і нумерація

Визначення 4. Нехай дані два алфавіти A і B. Кодування слів алфавіту A словами в алфавіті B є функція (p), що здійснює відображення безлічі слів в алфавіті А в безліч слів в алфавіті В: (p): A*У*, де pА*, (p)  B*.

Якщо кожному слову в алфавіті А відповідає слово в алфавіті В, то відображення однозначне.

Приклад.  Нехай A = {a, b}, B = {a, b, c}. Відображення (p) : p  cpc визначає кодування слів в алфавіті A словами в алфавіті B, наприклад, ab  cabc.

Визначення 5. Кодування називається блоковим, якщо кожній букві алфавіту А відповідає слово в алфавіті В.

Приклад. Відображення (a): a  ac, (b) : b  bc є блоковим кодуванням. Наприклад, (ab) = acbc.

Будь-які безлічі слів у деякому алфавіті можна упорядкувати в лексикографічному порядку: якщо R1R2, R1R2 і <, те R1R2 < R1R2..

Приклад лексикографічного упорядкування для слів алфавіту A = {a, b}:

a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, і т.д.

Асоціативні вирахування

Визначення 6. Підстановка слова P замість Q у слові W означає заміну Q на P у слові W. Підстановка позначається: PQ.

Приклад. Нехай даний алфавіт А = {a, b} і підстановка abba. Тоді результат виконання підстановки над словом ababbbab буде наступним:

1.  ababbbab 2.  baabbbab 3.  bababbab 4.  bbaabbab 

5.  bbababab 6.  bbbaabab 7.  bbbabaab 8.  bbbbaaab

9.  bbbbaaba 10. bbbbabaa 11. bbbbbaaa

Визначення 7. Сукупність усіх слів алфавіту A разом з кінцевою системою припустимих підстановок називається асоціативним вирахуванням.

Проблема еквівалентності слів

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

Визначення 9. Послідовність суміжних слів R1, R2, …, Rn називають дедуктивним ланцюжком від R1 до Rn.

Визначення 10. Якщо існує дедуктивний ланцюжок від R до S, те існує і дедуктивний ланцюжок від S до R. Такі два слова називаються еквівалентними словами.

Проблема еквівалентності слів полягає в перебуванні дедуктивного ланцюжка від слова R до слова S. Це означає, що необхідно знайти таку безліч припустимих підстановок, щоб, застосовуючи них до слова R, наприкінці дедуктивного ланцюжка одержати слово S.

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

ЛЕКЦІЯ 2. Машина Тьюринга

Визначення машини Тьюринга

Машина Тьюринга була першою алгоритмічною схемою, запропонованої як математичне визначення алгоритму в 1937 році.

Машина Тьюринга є гіпотетичною машиною: Тьюринг не ставив задачі сконструювати цей пристрій. Концепція обчислювальної машини належить фон Нейману, але її основою послужила машина Тьюринга. Машина Тьюринга є знакоперерабатывающим пристроєм. Задача машини Тьюринга – переробляти вхідне слово W  A* у деяке вихідне слово W A*, де А – зовнішній алфавіт.

Машина Тьюринга складається з трьох частин.

1). Нескінченна в обидва боки стрічка, розбита на осередки, у кожній з яких може знаходитися один (і тільки один) символ зовнішнього алфавіту A = {, , , …}... Інформація записується на стрічці у виді слова в алфавіті A. 

2).  Голівка, що зчитує, що в один дискретний момент часу обдивляється один осередок і може знаходитися в одному з внутрішніх станів qi ( Q, де Q - алфавіт внутрішніх станів. При цьому вона розпізнає записаний в осередку символ зовнішнього алфавіту, записує замість нього інший символ (можливо, той же самий), переходить в інший стан (можливо – у колишнє), після чого зрушується вправо, вліво або залишається на місці (П, Л, Н) (див. мал. 1).

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

3) Наступна частина машини Тьюринга – це програма, що складається з команд виду:  

qi   qj,  {Л, П, Н}, qi, qj Q, ,   A.

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

Послідовність команд задає алгоритм переробки слова. На вхід машини Тьюринга подається слово вихідне слово W в алфавіті A і задається початковий стан q0: початкова конфігурація. Робота машини Тьюринга відбувається по тактах, або по кроках. При роботі машини Тьюринга можливе розширення зовнішнього алфавіту A допоміжними символами, що після переробки слова заміняються символами алфавіту A або витираються. У число символів алфавіту A обов'язково входить порожній символ . Вважається, що споконвічно всі осередки стрічки заповнені порожніми символами.

У процесі роботи можливі ситуації:

  1.  Машина Тьюринга переробляє вихідне слово P у Q і зупиняється; тоді говорять, що дана машина застосовна до слова P.

Машина Тьюринга, починаючи роботу зі слова P, ніколи не зупиниться; тоді говорять, що дана машина Тьюринга не застосовна до слова P.

Розглянемо приклад.

Нехай заданий алфавіт A = {|, *}, вихідне слово, у якому може мати вигляд: P = | | |* | * | |. У початковому стані q0 машина обдивляється крайній лівий символ. Машина Тьюринга повинна перетворити це слово в порожнє слово, тобто повинна реалізовувати алгоритм обчислення нуль-функції: 0(x) = . Для цього вона повинна, рухаючи ліворуч праворуч, замінити кожен символ на стрічці на порожній символ і зупинитися, як тільки побачить крайній правий символ.

Програму для машини Тьюринга звичайно записують у виді таблиці.

Це дуже простий алгоритм.

Розглянемо програму для алгоритму додавання символу | до слова в тім же алфавіті. Нехай вихідне слово має вигляд: P = | | |. Це слово можна розглядати як число 3, а додавання символу | – як обчислення функції f(x) = x + 1 в унарной системі числення. Програма для машини Тьюринга насправді дуже проста: голівка машини пропускає всі символи |, рухаючи ліворуч праворуч, і, дійшовши до крайнього правого порожнього символу , дописує туди ще один символ |, після чого зупиняється у своєму заключному стані (див. табл. ). 

Очевидно, що точно так само можна скласти програму для додавання будь-якого символу алфавіту A наприкінці слова, тобто такий алгоритм реалізовує вихідну рекурсивну функцію P(x) = x, де   A.

Третя вихідна функція: функція проекції Uij(x) = xi, є не що інше, як елементарна дія машини Тьюринга – розпізнавання символу.

Розглянемо тепер обчислення більш складної функції: F(x,y) = x+y, де x, y – слова, задані в унарной системі числення. Нехай вихідна конфігурація на стрічці задана так, що в початковому стані голівка обдивляється крайній лівий символ |, (див. мал.), слово на стрічці являє собою два числа, розділені символом *.

Складемо машину Тьюринга, що працює по наступному алгоритмі. У початковому стані q0 машина бачить крайню ліву паличку, витирає її і, перейшовши в стан q1, рухається вправо, поки не побачить крайній праворуч порожній символ. Тоді на місці порожнього символу машина записує паличку, переходить у новий стан q2 і рухається вліво в тім же стані q2, пропускаючи всі символи, поки не дійде до крайнього ліворуч порожнього символу. Тоді машина залишає його на місці, зрушується вправо і переходить у стан q0. Після цього процес повторюється доти, поки в стані q0 машина не побачить символ *. Це означає, що уже всі палички перенесені ліворуч праворуч, машина може витерти символ * і зупинитися, тобто перейти в заключний стан.

A \ Q

q0

q1

q2

|

 q1 П

 q1 П

q2 Л

*

 ! П

* q1 П

* q2 Л

 ! Н

 q2 Л

q0 П

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

f(x, 0) = x,

f(x, y+1) = f(x, y) + 1.

f(2, 3) = f(2, 2) + 1 = (f(2, 1) + 1) + 1 = ((f(2, 0) + 1) + 1) + 1.

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

((2 + 1) + 1) + 1 = (3 + 1) + 1 = 4 + 1 = 5.

ЛЕКЦІЯ 3.  Машина, що розпізнає, Тьюринга

Машина, що розпізнає, Тьюринга - це машина, що обчислює предикат P(W) таким чином, що якщо P(W) = T, те машина зупиняється в стані так!, а якщо P(W) = F, те в стані немає!.

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

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

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

Нуль-функція 0(x)= ;

Додавання символу : P(x) = x, де   A;

Функція, що проектує, Uij(x) = xi;

Тотожне перетворення Т(x) = х;

Алгоритм копіювання слова Copy(x) = x*x;

Алгоритм, що заміняє, Repxjxi(x) = xj, де xi, xj ( A(B, де B - допоміжний алфавіт.

З цих елементарних алгоритмів можна утворювати більш складні за допомогою композиції машин Тьюринга.

1. Послідовна композиція.

Нехай М1 і М2 – дві машини Тьюринга. Тоді, ототожнивши заключний стан машини М1 з початковим станом машини М2 і, при необхідності, перенумерувавши внутрішні стани машини М2, одержимо нову машину Тьюринга, що, починаючи роботу зі слова W, спочатку буде виконувати над ним перетворення, виконувані машиною М1, а потім буде працювати як машина М2. Композицію машин Тьюринга можна позначити: M1М2 = M2(М1(W)). Таким чином, послідовна композиція машин Тьюринга здійснює суперпозицію функцій.

2. Рівнобіжна композиція.

Якщо на стрічці записане слово W, що представимо як конкатенація двох слів Р||Q, можна скласти таку машину Тьюринга, що буде працювати як машина M1 над подсловом P і як машина M2 над подсловом Q, а потім здійснить конкатенацію результатів: M1(P)||M2(Q).

3.  Машина, що розпізнає, Тьюринга.

Якщо існують машини Тьюринга M1 і M2 і машина, що розпізнає, Тьюринга P, то можна скласти таку машину Тьюринга M, що, починаючи роботу зі слова W, машина работает працює спочатку що як розпізнає машина P(W). Якщо вона закінчує обробку вихідного слова в стані так, то далі працює машина M1(W), а якщо в стані ні, те машина M2(W).

4. Циклічна машина Тьюринга.

Можна побудувати таку машину Тьюринга M, що, починаючи роботу зі слова W0, спочатку працює як розпізнає машина P, що обчислює предикат P(W0). Якщо вона завершує свою роботу в стані так!, те далі вона працює як машина Тьюринга M1 над словом W0 і завершує свою роботу з вихідним словом W1. Далі керування передається машині, що розпізнає, P, що обчислює предикат P(W1), і так далі, доти, поки машина, що розпізнає, Тьюринга P не зупиниться в стані немає! на слові Wk. Тоді машина Тьюринга M зупиняється у своєму заключному стані.  

Було математично доведене, що для реалізації будь-яких алгоритмів досить цих чотирьох структур .

ЛЕКЦІЯ 4.Нормальний алгоритм Маркова

Визначення 11. Нормальний алгоритм Маркова – це кінцевий упорядкований набір підстановок виду P(.) Qi, i = 1, 2, …, n... P Qi – звичайна підстановка, що означає, що крайнє ліве входження подслова Pi у W заміняється на Qi., Pi  . Qi – кінцева підстановка, тобто після її виконання робота алгоритму завершується.

Робота алгоритму Маркова.

Вихідне слово  А* переробляється за допомогою алгоритму в такий спосіб. Починаючи з першої підстановки, шукається перше ліве входження подслова Pi у слові W. Якщо воно знайдено, то воно заміняється на Qi, після чого список підстановок проглядається із самого початку. Якщо ж входження Pi не було знайдено, то вибирається наступна підстановка. Якщо була виконана заключна підстановка, то процес переробки слова завершується і тоді говорять, що алгоритм застосуємо до даного слова. Може виявитися, що процес не завершується, тобто жодна з заключних підстановок не застосовувалася в процесі переробки слова. У цьому випадку говорять, що алгоритм не застосуємо до даного слова.

Приклад. Нормальний алгоритм Маркова для додавання двох чисел в унарной системі, тобто алгоритм обчислює функцію f(x,y) = x+y в алфавіті A = {|, *}. Список підстановок складається з двох підстановок.

  1.  * |  |*

*  

Процес переробки слова полягає в наступному (у дужках зазначений номер застосовуваної підстановки):

| | |* | | | | (1)  | | | |* | | | (1) | | | | |* | | (1) | | | | | |* | (1) | | | | | | |* (2) | | | | | | |

Приклад. Алгоритм звертання слова в алфавіті A = {a, b, c, …, z}... Наприклад, вихідне слово abc звертається в слово cba. Список підстановок:

  1.    

  

  

  

 



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

abc (6) abc (5)bac (5)bca (6) bca (5)cba (6) cba (6) cba (1)cba (2)cba (3)cba (2)cba (3)cba (2)cba (4)cba.

Еквівалентність нормальних алгоритмів і машини Тьюринга

Теорема. Нехай M – машина Тьюринга з зовнішнім алфавітом A і внутрішнім алфавітом Q. Тоді існує нормальний алгоритм Маркова з алфавітом АQ, еквівалентний даній машині Тьюринга.

Доказ. Нехай дана машина Тьюринга M із зовнішнім алфавітом А = {xi}, де = 1, 2, …, n, і внутрішнім алфавітом = {qi}, j = 0, 1, …, n... Двовимірну конфігурацію на стрічці можна записати як x1x2…qjxixi+1…xn,де символ поточного стану qj коштує перед символом, що обдивляється голівка машини Тьюринга в даний момент часу. Ми одержимо слово в алфавіті АQ. Тоді можна замінити кожну команду машини Тьюринга на послідовність підстановок у такий спосіб:

  1.  qj  qr    qj  qr
  2.  qj  qrП qjxi  qrxi,  xi A
  3.  qj  qrЛ xiqj  qrxi xi A
  4.  qj .    qj Q
  5.    q0

Таким чином, якщо мається деяка програма для машини Тьюринга, те за допомогою цих п'яти правил її можна перетворити в алгоритм Маркова.

Приклад. Нехай задана програма для машини Тьюринга в алфавіті А = {|, *}.

q0

|

| q0 П

| ! H

*

* q0 П

Нормальний алгоритм Маркова, еквівалентний цій машині Тьюринга має вигляд:

  1.  q0 | | | q0 |

q0 |* | q0*

q0 |   | q0

q0  . |

  q0

Процес переробки слова:

| | * |  q0 | | * | | q0 | * | | | q0 * | | | *q0 |  | | * |q0   | | * | |

Теорема (зворотна). Для кожного нормального алгоритму Маркова можна побудувати еквівалентну йому машину Тьюринга.

Схема доказу.

  1.  Пошук подслова Р в слові W (необхідно скласти машину Тьюринга, що шукає подслово P у слові W; голівка машини Тьюринга, у результаті, буде стояти на першому символі подслова P).

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

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

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

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

Клас функцій, вычислимых по Тьюрингу

Словникові примітивно рекурсивні функції

Вихідні функції для алфавіту A:

Нуль-функція 0(x)= ;

Додавання символу : P(x) = x, де   A;

Функція, що проектує, Uij(x) = xi, де j - кількість букв у слові x, xi - i-я буква слова x.

Схема примітивної рекурсії для алфавіту A = {a, b).

Нехай g(x1, …, xn), h1(x1, …, xn+2), h2(x1, …, xn+2), – вихідні або примітивно рекурсивні функції. Тоді f(x1, …, xn+1) – нова примітивно рекурсивна функція, якщо

f(x1, …, ) = g(x1, …, xn),

f(x1, …, a) = h1(x1, …, xn, a, f(x1, …, xn+1)),

f(x1, …, b) = h1(x1, …, xn, b, f(x1, …, xn+1))...

Позначимо операцію конкатенації con(x1, x2), x1, x2  A*, A={a, b} і покажемо, що вона є примітивно рекурсивною.

con(x1, ) = x1 = U12(x) = x1;

con(x1, x2, a) = x1x2a = Pa(con(x1x2));

con(x1, x2, b) = x1x2b = Pb(con(x1x2)).

У загальному випадку

con(x1, x2, ) = x1x2 = P(con(x1x2)).

Функція f(x1, x2, …, xn) називається ефективно вычислимой, якщо для кожного набору аргументів а1, а2, … , аn з її області визначення може бути обчислене значення функції f(а1, а2, … , аn). Якщо функція ефективно вычислима, то говорять, що існує алгоритм її обчислення.

Теорема. Функція F(х1, х2,…хn) рекурсивна (частково рекурсивна) тоді і тільки тоді, коли вона вычислима по Тьюрингу.

Доказ.

  1.  Усяка рекурсивна функція вычислима по Тьюрингу.

Z(x) =  – нуль-функція вычислима на машині Тьюринга, що знищує будь-яке слово на стрічці.

N(x) = x+1 – вычислима на машині Тьюринга, що до будь-якого слова W на стрічці дописує заданий символ :W.

Ujn(x) = xi  – функція проекції вычислима на машині Тьюринга, що у слові W виділяє символ xi.

(x1, x2) = g(F1(x1, x2), F2(x1, x2)) – суперпозиція функцій, реалізується за допомогою композиції машин Тьюринга:

M= (x1*x2)(MF1||MF2)зам*|| Мg.

Машина спочатку копіює вихідне слово:

Copy2(x1*x2)  x1*x2 || x1*x2.

Потім воно переробляється рівнобіжною композицією машин МF1||  МF2 у слово  F1(x1*x2) || F2(x1*x2)), потім алгоритм зам*|| заміняє допоміжний поділяючий символ || на *, і далі працює машина, що обчислює функцію  g(F1(x1, x2), F2(x1, x2)):  Mg(F1(x1*x2)*F2(x1*x2)). Результатом її роботи є функція (x1,x2).

Схема примітивної рекурсії також обчислюється за допомогою композиції машин Тьюринга. Наприклад, найпростіша схема примітивної рекурсії: (0) = c, (x+1) = F((x)) вычислима як композиція, що реалізує ітерацію. Для цього будуються машини:

MD переробляє трійку чисел x#m#z у трійку x#m+1#F(z)$

MC переробляє число x у трійку x#0#c ;

Ф розпізнає властивість m<z у трійці чисел x#m#z.

Композиція MCпоки Ф повторити MD задає алгоритм, що, виходячи зі слова  x, виробляє трійку x#0#C, потім x#1#(c), потім x#2#((c)), і т.д. доти, поки не буде отримана трійка x#x#(x). Тоді виділяє алгоритм, застосований до цього слова, виділить крайній правий компонент слова, що є результатом обчислення функції (x).

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

Оскільки всі шість пунктів визначення рекурсивних функцій реалізовані у виді композиції машин Тьюринга, те всяка рекурсивна функція вычислима на машині Тьюринга.

Таким чином, було показано, що клас функцій, вычислимых на машині Тьюринга, є частково рекурсивним класом.

Крім цих алгоритмічних схем було знайдено і запропоноване багато інших, наприклад, машина фон Неймана, машина Посади, блок-схеми Посади, формальне вирахування рекурсивних функцій Эрбрана - Геделя й інші. Виявилося, що усі вони еквівалентні між собою, і, отже, усі вони обчислюють рекурсивні або частково рекурсивні функції. Ця обставина послужила причиною тому, що ряд учених (Черч, Тьюринг, Марков) практично одночасно висловили гіпотезу, що відома як теза Черча.

ЛЕКЦІЯ 5.Теза Черча

Кожна функція є ефективно вычислимой тоді і тільки тоді, коли вона рекурсивна.

Іншими словами, теза Черча пропонує розуміти під ефективної вычислимостью існування алгоритмічної схеми, а оскільки всі знайдені алгоритмічні схеми обчислюють тільки клас рекурсивних (частково рекурсивних) функцій, то під ефективної вычислимостью тоді розуміється рекурсивність.   

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

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

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

Невычислимые функції

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

Доказ. Припустимо, існує перерахування L = F1, F2,…,Fk,…всіх арифметичних функцій (тобто функцій, визначених на безлічі N). Побудуємо функцію U(n) у такий спосіб:

  1, якщо Fn(n) не визначена,

U(n) = 

  Fn(n) + 1, у противному випадку.

Тоді U(n) – усюди визначена на N функція. Якщо безліч арифметичних функцій счетно, тобто існує перерахування L, то побудована нами функція входить у це перерахування з яким-небудь номером, наприклад, m, тобто U(n L і U(n) = Fm. Тоді, обчислюючи значення цієї функції від m відповідно до її визначення, одержимо: U(m) = Fm(m): Fm(m) = Fm(m) + 1, якщо Fm(m) визначена, що неможливо, тобто ми прийшли до протиріччя.

Побудована нами функція, по-перше, доводить незліченність безлічі арифметичних функцій, а по-друге, по способі побудови вона є невычислимой функцією.

Таким чином, ми установили, що безліч всіх арифметичних функцій незліченно, тобто його потужність дорівнює 20 = c. Постараємося з'ясувати, яка потужність безлічі всіх рекурсивних функцій. Тепер, коли встановлена еквівалентність усіх рекурсивних функцій і всіх машин Тьюринга, для цього досить “перерахувати” усі можливі машини Тьюринга.

Розглянемо безліч символів, необхідних для зображення програми для машини Тьюринга. Нехай зовнішній алфавіт складається з двох символів: = {0, 1}(можливість кодування будь-яких даних у двоичной системі числення ні в кого не викликає сумніву – адже саме так працюють сучасні обчислювальні машини). Нехай стани позначаються десятковими числами, тобто внутрішній алфавіт = {0, 1, 2, 3, 4, …, 9}, і три символи нам знадобляться для вказівки руху голівки: {П, Л, Н}. Кожній клітці в таблиці, що зображує програму машини Тьюринга, поставимо у відповідність команду у виді: aiqj  червонийqд, де ai,ak A,   {П, Л, Н}, qj, qд  Q. Будемо використовувати роздільники: , – для заміни символу , ; – для відділення однієї команди від іншої. Тоді послідовність команд може бути зображена, наприклад, так: 10, 0П12; 01, 0П1; 11, 1Л2; і так далі. Запис 10, 0П12; означає, що в стані 0 машина бачить символ 1, записує на його місце символ 0, зрушується вправо і переходить у стан 12. Тоді для запису програми машини Тьюринга досить тільки 15 символів (з огляду на, що символи зовнішнього алфавіту 0 і 1 входять і в алфавіт Q). У результаті будь-яка програма може бути представлена,  як число в 15-тиричной системі числення.

Записана так, як зазначено вище, програма для машини Тьюринга M називається кодом машини Тьюринга і позначається d(M), а 15-тиричное число, яке можна поставити їй у відповідність, називається індексом машини Тьюринга.

Таким чином, кожній машині Тьюринга можна поставити у відповідність її індекс – число в 15-ричной системі числення. Але безліч чисел у 15-тиричной системі числення счетно (тому що счетна будь-яка нескінченна послідовність кінцевих послідовностей символів), – виходить, безліч усіх машин Тьюринга теж счетно. Отже, потужність безлічі всіх рекурсивних функцій (оскільки вони і тільки вони вычислимы на машині Тьюринга) дорівнює 0, і  0 c.

Ми показали, що всіх арифметичних функцій більше, ніж вычислимых функцій, а звідси випливає, що існують невычислимые функції. У загальному виді це означає існування таких проблем (задач), для яких неможливо побудувати алгоритм, тобто машину Тьюринга, – якщо приймати теза Черча. Це не означає, утім, що ці проблеми взагалі нерозв'язувані. Проблема вважається алгоритмічно нерозв'язної, якщо існує хоча б одна задача з даного класу задач, для якої математично строго доведена неможливість побудови алгоритму, тобто машини Тьюринга, або нормального алгоритму Маркова, або якої-небудь іншої алгоритмічної схеми. Тьюринг запропонував інструмент для доказу алгоритмічної нерозв'язності – універсальну машину Тьюринга.

Універсальна машина Тьюринга

Будь-яка програма для машини Тьюринга може бути закодована деяким кодом. Позначимо через d(М) код програми машини Тьюринга. Тоді можна побудувати таку машину Тьюринга М(d(М)*W) на вхід якої буде подаватися код d(М) разом із вхідним словом W. Тоді машина Тьюринга спочатку перевіряє, чи є d(М) синтаксично правильним програмним кодом для машини Тьюринга, і якщо це так, то виконує програму машини М над словом W; якщо ж ні, те вона зупиняється в стані “немає!”. Така машина Тьюринга називається універсальною машиною Тьюринга.

Універсальна машина Тьюринга є математичним апаратом для доказу алгоритмічної нерозв'язності проблем . Аналогічно можна побудувати й універсальний алгоритм Маркова.

ЛЕКЦІЯ 6. Алгоритмічно нерозв'язні проблеми

Проблема останова для машини Тьюринга  

Історично першою алгоритмічно нерозв'язною проблемою, доведеної Тьюрингом, була проблема останова для машини Тьюринга. Вона формулюється так: чи можна побудувати таку універсальну машину Тьюринга М, що будучи застосованої до слова (d(М)* W), вона буде зупинятися в “так!” стані, якщо машина Тьюринга М застосовна до слова W, тобто зупиняється на цьому слові, і зупинятися в “немає!” стані, якщо машина М не застосовна до слова W.

Теорема. Проблема останова для машини Тьюринга алгоритмічно нерозв'язна.

Доказ. Припустимо, що така універсальна машина Тьюринга М побудована. Це означає, що в таблиці програми універсальної машини Тьюринга є дві команди, по яких вона в деякому стані q на деякому символі зупиняється в “так!” стані, і в деякому стані q на деякому символі зупиняється в “немає!” стані (тобто в її таблиці є клітки:

  1.  

Побудуємо тепер машину Тьюринга М так, що змінимо в ній тільки одну команду: у стані q на символі машина не зупиняється, а продовжує нескінченно писати символ у ту саму осередок. Таблиця для машини М показана нижче.

q

q 

даний

немає!

Тепер на вхід машини М подамо її власний код, для якого вхідним словом буде код машини Тьюринга М: М(d(M)*d(M)).  Чи зможе тепер машина М розпізнати, чи зупиниться вона сама на коді машини Тьюринга М ? Універсальна машина Тьюринга працює так, як машина, код якої поданий на її стрічку, отже, дійшовши до символу у стані q (у коді машині М – слові, що переробляється,), машина М( зупиниться в стані так!”, у той час як М не зупиняється! І навпаки, коли в стані q машина М бачить символ , вона видає повідомлення “ні” і зупиняється, а машина М для цієї ситуації теж зупиняється в стані “ні”, тобто вона видає повідомлення про те, що машина М не зупиняється!

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

Проблема алгоритмічної нерозв'язності зв'язана з проблемою самозастосовності.

Проблема самозастосовності

Будемо говорити, що машина Тьюринга М самозастосовна, якщо вона зупиняється на своєму власному коді d(М), і не самозастосовна, якщо вона не зупиняється на своєму коді d( М).

Теорема. Проблема розпізнавання самозастосовності машини Тьюринга алгоритмічно не розв'язна.

Доказ. Припустимо, що побудовано машину Тьюринга М, що зупиняється в “так!” стані, якщо машина самозастосовна, і в “немає!” стані, якщо не самозастосовна. Тоді в програмі машини Тьюринга присутні дві команди виду: q  так!, q  немає!

Аналогічно попередньому доказові, побудуємо машину М, змінивши одну команду: q  дана (тобто машина не зупиняється, а нескінченно пише символ на стрічці). Тепер, якщо на вхід М подати d): М(d)) машина буде видавати “так!”, – тобто повідомляти, що М самозастосовно, у той час як вона не самозастосовна, тому що не зупиняється, і, навпаки, вона буде видавати повідомлення “немає!”, якщо машина М не зупиняється, тобто якщо вона самозастосовна.

У такий спосіб доказательстно нерозв'язності проблеми самозастосовності зводиться до доказу неможливості розпізнавання останова машини Тьюринга. Звідси виник і загальний метод доказу алгоритмічної нерозв'язності інших задач: метод зведення проблем. У цьому методі нова проблема зводиться до деякої іншої проблеми, для якої вже доведена алгоритмічна нерозв'язність. Особливо часто проблема зводиться в проблемі самозастосовності. Як приклад розглянемо проблему еквівалентності слів в асоціативних вирахуваннях.

Теорема (Маркова – Посади). Існує асоціативне вирахування, у якому проблема розпізнавання еквівалентності слів алгоритмічно нерозв'язна.

Доказ. Нехай машина Тьюринга М починає роботу зі слова R з початковою конфігурацією q0 і закінчує роботу словом S з кінцевою конфігурацією qk. Проблема розпізнавання еквівалентності слів R і S у такій постановці полягає в перебуванні алгоритму, що по коду машини М розпізнає, чи зупиниться вона в стані qk, починаючи роботу з конфігурації q0, чи ні. Подамо код цієї машини разом зі словом R на вхід універсальної машини М: М(d(M)*R). Для машини М( проблема останова нерозв'язна. Звідси випливає, що проблема розпізнавання еквівалентності слів також алгоритмічно нерозв'язна. Покажемо, що вона нерозв'язна також і в деякому асоціативному вирахуванні. Для цього скористаємося тим властивістю, що для будь-якої машини Тьюринга можна побудувати еквівалентне йому асоціативне вирахування.

Остання властивість була доведена нами для нормальних алгоритмів Маркова. Нормальний алгоритм Маркова можна розглядати як асоціативне вирахування з однонапрвленными підстановками, що непоредственно випливає з визначення цих систем. При необхідності для кожної підстановки нормального алгоритму можна визначити зворотну підстановку й одержати асоціативне вирахування з двунапраленными підстановками.  

Побудуємо асоціативне вирахування S(M), що виконує той же алгоритм, що і машина М, зокрема, що переробляє слово R у слово S,  і приєднаємо до нього систему підстановок виду qkaiqk. Одержимо нове вирахування S(M). У цьому вирахуванні також переробляються слова виду R у слова виду S, але всі заключні конфігурації М в S(M) эквивалентнтны. Тому в S(M) слова q0 і qk еквівалентні, якщо і тільки якщо машина М, почавши роботу зі слова q0, зупиниться. Через нерозв'язність проблеми останова для М, проблема еквівалентності слів q0 і qk  також нерозв'язна.

З цієї теореми випливає, що проблема розпізнавання еквівалентності слів у загальному випадку (тобто для всієї безлічі асоціативних вирахувань) алгоритмічно нерозв'язна. Звідси випливає також, що проблема еквівалентності алгоритмів нерозв'язна: по двох заданих алгоритмах неможливо визначити, обчислюють вони ту саму чи функцію ні.

Історично алгоритмічна нерозв'язність спочатку була встановлена для проблем, що виникають у математичній логіці, – проблем виводимості у формальних теоріях. Доказ нерозв'язності проблем самозастосовності й еквівалентності показав, що алгоритмічні схеми можуть служити апаратом дослідження можливості розв'язання і повноти формальних теорій. Проблему  виводимості у формальній теорії можна інтерпретувати як проблему распознаваниия еквівалентності слів: з помошью заданої системи правил висновку необхідно визначити, чи є формула виведеної з заданої системи аксіом і вихідної безлічі посилок. Тоді з алгоритмічної нерозв'язності розпізнавання еквівалентності слів випливає нерозв'язність (у загальному випадку!) проблеми виводимості. Ми знаємо, що вирахування висловлень розв'язне: побудова таблиці істинності формули є алгоритмом, за допомогою якого доводиться, що формула є (або не є) тавтологією логіки висловлень, а, отже, і теоремою вирахування висловлень. Вирахування предикатів 1-го порядку нерозв'язно, що було доведено для формальної арифметики S (теорема Гёделя про неповноту). Доказ теореми Гёделя істотно основывалость на рекурсивності представимых у S функцій і відносин. Отже, той же самий результат можна одержати, використовуючи апарат алгоритмічних схем, зокрема, машини Тьюринга. У 1936 р. цей результат: проблема розпізнавання виводимості алгоритмічно нерозв'язна, – був отриманий Черчем.

Теорема Черча дає конструктивний спосіб побудови невычислимой функції.

Як приклад визначення такої функції розглянемо наступну задачу. Уявимо собі велику бібліотеку, у якій книги розставлені по розділах. Для кожного розділу складений каталог. Кожна книга має призначену їй ціну, а оскільки каталог роздягнула містить зведення про всі книги, він повинний бути самою коштовною книгою. Тому його вартість определна як функція від вартості самою дорогою нкиги в розділі: Ск = Сmax + 1. Книг у бібліотеці виявилося настільки багато, що всі каталоги були складені в окремий розділ і був складений каталог каталогів. Йому також повинна бути призначена ціна за  визначеним вище правилом: вартість його повинна бути найвищої в цьому розділі, тобто Скк = Скmax, і повинна бути на одиницю більше ціни найдорожчої книги в розділі: Скк = Скmax + 1. Але оскільки каталог каталогів сам є каталогом, те його ціна болжна бути на одиницю більше його власної вартості: Скк = Скк + 1. Таким чином, виявилося, що вартість його неможливо обчислити за заданим правилом.


ЛЕКЦІЯ 7. Складність обчислень

Масові задачі

Масова задача  визначається списком параметрів і формулюванням властивостей відповіді.

Приклад. 1). Задача про комівояжера (на повному зваженому графі).  

Параметри: набір міст C = {c1, ..., cm) і відстаней d(ci, cj) між ними.

Вид відповіді: упорядкований набір міст <c(1) , ..., c(m)>, що мінімізує величину шляху

d(c(i), c(i+1) + d(c(m), c(1))  B .

2). Перебування максимального елемента в масиві. Параметри: масив x(1), x(2), …< x(n)... Вид відповіді: числа m, j, такі, що m – max1knx(k) = x(j), причому j – максимальне з усіх можливих.

3). Выполнимость конъюнктивной нормальної форми (КНФ). Параметри: кількість перемінних, від яких залежить КНФ, і довжина формули. Вид відповіді: знайти хоча б один набір значень перемінних, при якому КНФ дорівнює 1, або довести, що дана КНФ дорівнює нулеві.

Індивідуальна задача I виходить з , якщо всім параметрам привласнені конкретні значення.

Алгоритм A вирішує задачу , якщо він вирішує будь-яку задачу I з .

Складність алгоритму

Довжина слова, що кодує задачу I, – це величина n, функцією від якої визначається складність алгоритму А. 

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

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

Асимптотические представлення

Дуже часто, щоб порівняти одну величину з інший, досить знать не точні, а наближені значення. У таких випадках звичайно записують: A B (A приблизно дорівнює B). Для оперирования наближеними величинами в математику прийнято використовувати символ O, що дає можливість заміняти символ символом =. Запис O(f(n)) застосовується тоді, коли f(n) є функцією від цілого позитивного n, однак точне значення цієї функції невідомо, – відомо лише, що значення це невелико. Більш точно, запис O(f(n)) означає, що існує позитивна константа з, така, що величина xn, представлена як O(f(n)), задовольняє умові:

xn  f (n) для всіх n 0.

Наприклад, співвідношення Hn = ln(n) + v + O(1/n) означає, що | Hn – ln(n) + v  c/n. Константа з невідома, однак, зрозуміло, що O(1/n) буде як завгодно мало, якщо n досить велико.

Символ O завжди коштує в правій частині рівності. Наприклад, n2/2 + n = O(n2) означає, що n2/2 + n не більше, ніж n2, тобто при досить великому n значення вираження n2/2 + n будить приблизно дорівнює n2. Якщо це оцінка складності алгоритму, то можна сказати, що складність алгоритму квадратична.

Для O(f(n)) здійсненні наступні властивості:

f(n) = O(f(n)),

cO(f(n)) = O(f(n)),

O(f(n)) + O(f(n)) = O(f(n)),

O(O(f(n))) = O(f(n)),

O(f(n)) O(g(n)) = O(f(n)g(n)),

O(f(n)g(n)) = f(n)O(g(n)).

Класи складності задач 

Запис f(n)  O(g(n)) означає, що існує константа з, така, що f (n)  c g(n) для всіх n 0. Алгоритм називається поліноміальним, якщо його складність TA (n)  O(p(n)), де p(n) - поліноміальна функція.

Приклад неполіноміальної функції - nlog n.

Складність моделювання машиною B роботи алгоритму складності f (n) на машині А.

Моделируемая

Моделююча машина А

машина B

1МТ

kМТ

МДП

     1-стрічкова МТ (1МТ)

-

O(f (n))

O(f (n))log f (n)

k-стрічкова МТ (kМТ)

O(f 2(n))

-

O(f (n))log f (n)

Машина довільного доступу (МДП)

O(f 3(n))

O(f 2(n))

-

Приклад - розпізнавання паліндрома (слова, симетричного щодо середини): на 1-МТ його складність O(n2), а вже на 2-МТ - O(n).

Цю таблицю можна розглядати як виправдання (обґрунтування розумності) усієї наступної теорії. Для будь-якої функції складності:

  1.   аддитивной константою можна зневажити – це, як правило, накладні витрати, помітні лише на задачах малого обсягу;
  2.   мультиплікативна константа переборюється зростаючою швидкодією комп'ютерів;
  3.   ступінь полінома, як видно з таблиці, для однієї і тієї ж задачі може бути різної при різних архитектурах машин; тому, якщо будувати машинно-незалежну теорію складності, ступенем полінома приходиться зневажити. Таким чином, мовчазно приймається теза: перенос задачі на детерминированную машину будь-якої мислимої архітектури змінює її складність не більш ніж полиномиально. У термінах, що вводяться нижче, це означає, що приналежність (або неприналежність) задачі класові P не залежить від типу машини, на якій написаний алгоритм рішення задачі. Тому -
  4.   задачі експонентної складності зберігають цю складність (тобто важко вычислимы) на машині будь-якої архітектури.  

Ідея полиномиальности (точніше - розгляд складності з точністю до полиномиальности) - перший ключовий момент теорії. Надалі для зручності формулювань розглядаються тільки задачі розпізнавання властивостей, тобто задачі, рішення яких - це відповідь «так» або «ні». Задача розпізнавання характеризується двома безлічами: безліччю D всіх індивідуальних задач і безліччю індивідуальних задач Y з відповіддю «так». При розумних схемах кодування задача розпізнавання перетворюється в задачу розпізнавання мови L(, ) в алфавіті K схеми кодування: L(, ) ={безліч усіх  K* , що є кодами задач з Y при схемі кодування . Природно вважати, що коди однієї і тієї ж задачі при різних розумних схемах кодування розрізняються по довжині не більш, ніж полиномиально. «Розумні схеми кодування» - це схеми стиснуті і полиномиально декодируемые.

Детерминированная (тобто звичайна) машина Тьюринга (ДМТ) із двома заключними станами: q («так») і q («ні»).

Мова LM розпізнається ДМТ M, якщо LM = { K* : M() = q}.

Якщо M зупиняється на усіх  K*, то тимчасова складність TM (n) визначається так:

 TM (n) = max TM () по усім таким, що  = n.

ДМТ M називається поліноміальної, якщо існує такий поліном p(n), що для будь-яких n TM (n)  p(n).

Клас мов P - це безліч усіх мов, для яких існують распознающие їхній ДМТ.

Задача розпізнавання належить класові P при кодуванні , якщо L(, )P.

Задача комівояжера формулюється як задача розпізнавання в такий спосіб:

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

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

Недетерминированный «алгоритм»: недетерминированное угадування + поліноміальна детерминированная перевірка.

 Недетерминированная машина Тьюринга (НДТМ) містить звичайний детерминированный блок і модуль, що угадує. Обчислення при даному вхідному слові складається з двох етапів. Спочатку угадує модуль пише на стрічці довільне слово K* ліворуч від вхідного слова, а потім детерминированный блок перевіряє, чи не є ( рішенням, і переходить або в q , або в q . Таким чином, існує нескінченна безліч  різних обчислень при даному вхідному слові .

НДТМ М приймає , якщо хоча б одне з обчислень на вході є приймаючої, тобто переводить М в q .

Мова LM , розпізнаваний М, - це безліч усіх слів у K*, прийнятих М. 

Час прийняття TM () = min числа кроків по всіх приймаючих обчисленнях .

Тимчасова складність М TM (n) = max TM () по усім таким, що  = n.

TM (n) = 1, якщо немає жодного слова довжини n, прийнятого М. 

Клас NP - це безліч усіх мов, прийнятих НД-машинами за поліноміальний час. Очевидно, що P  NP.

Теорема. Якщо   NP, то існує такий поліном p, що може бути вирішена детерминированным алгоритмом з тимчасовою складністю O(2p(n) ).

Дійсно, нехай q(n) - поліном, що обмежує тимчасову складність НД-алгоритма, що вирішує задачу . Тоді існує слово-здогад довжини  q(n), що детерминированно перевіряється за час q(n). Загальне число здогадів не перевершує k q(n) , де k - потужність алфавіту. Тому час роботи детерминированного алгоритму не перевершує q(n) k q(n) .

Мова L1 полиномиально зводимо до мови L2, якщо існує функція f, що задовольняє двом умовам:

  1.  f має поліноміальну складність;
  2.  для кожного  L1 , якщо і тільки якщо f()L2 .

Позначення: L1  L2.

Теорема. Якщо L1  L2, то з L2  P випливає, що L1  P. Еквівалентне формулювання: з L1  P випливає, що L2  P.

Доказ очевидний.

Зведення задачі 1 до задачі 2 означає, що 2 не простіше, ніж  1 .

Це зрозуміло: адже легку задачу можна звести до важкого, а важку до легкого - немає: якщо «важка» зведена до легкого, виходить, вона не така вуж важка.

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

Нехай в індивідуальній задачі про гамильтоновом цикл G = (V, E), V= m.

Відповідна задача про комівояжера будується так:

d(vi , vj ) = 1, якщо (vi , vj )E, і 2 у противному випадку; B = m. 

Функція f , що здійснює це зведення, полиномиальна, оскільки обчислення d(vi , vj) зводиться до з'ясування входження (vi , vj ) у E; усього таких з'ясувань m(m - 1)/2.

Якщо G містить гамильтонов цикл, то цей цикл є маршрутом у f (G) з довжиною m. Він мінімальний, тому що усі ваги на ребрах цього маршруту рівні 1. Отже, у цьому випадку задача f (G) дає позитивну відповідь. Якщо ж G не містить гамильтонов цикл, то довжина мінімального маршруту в f (G) більше m, і відповідь у задачі f (G) - негативний.  

Теорема. Відношення ( транзитивно.

Доказ тривіальний.  

Мови L1 і L2 полиномиально еквівалентні, якщо L1  L2 і L2 L1 . Це дійсне відношення еквівалентності: воно симетрично по визначенню, а транзитивність тільки що доведена. Виникають класи еквівалентності, причому P - найменший клас.

Мова L називається NP-повним, якщо L  NP і будь-яка інша мова L NP зводиться до L. Тим самим NP-повні задачі - самі важкі в класі NP, і якщо хоча б одна NP-повна задача утримується в P, те і всі NP-повні задачі утримуються в P.

Помітимо, що в цьому випадку всі задачі з NP утворювали б єдиний клас поліноміальної еквівалентності.

Теорема. Якщо L1, L2  NP, L1 - NP-повний і L1  L2, то L2 - також NP-повний.

Дійсно, по визначенню, для будь-якого L NP L’  L1 і, отже, у силу транзитивності відносини поліноміального зведення L L2 .

Теорема Кука. Задача выполнимости конъюнктивной нормальної форми є NP-повною.

Ця теорема, доказ якої займає більш семи книжкових сторінок, - останній і вирішальний ключовий момент NP-теорії. Адже з визначення NP-повної задачі не випливає, що існує хоча б одна така задача. Теорема Кука дає конструктивний доказ існування таких задач.

Є 6 змістовно цікавих задач, NP-повнота яких доводиться зведенням до задачі Кука:

  1.  3-выполнимость - выполнимость для КНФ, до якої кожна диз'юнкція містить рівно 3 литерала.
  2.  Верхове покриття - чи мається в графі G(V, E) верхове покриття не більш ніж з k елементів, тобто таке V  V, що V k і хоча б один кінець будь-якого ребра належить V?
  3.  Кліка - чи вірно, що граф містить кліку потужності k?
  4.  Гамильтонов цикл.
  5.  k-раскрашиваемость - чи можна розфарбувати граф G(V, E) у k квітів, де k <V?
  6.  Ізоморфізм подграфу.

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


ЛЕКЦІЯ 8.Поняття і способи їхніх представлень

Основою абстрактного мислення є поняття. Поняття являють собою одиницю мислення. Здатністю формувати поняття і встановлювати зв'язку між ними людина відрізняється, наприклад, від тварини.

У традиційній логіці, що викладається як філософська дисципліна, поняття визначається як “думка, у якій узагальнені в клас і виділені з деякої безлічі предмети по системі ознак, загальної тільки для цих виділених предметів” [2]. Таким чином, поняття (concept) можна визначити як сукупність об'єктів, що володіють тими самими властивостями (ознаками). Наприклад, поняття риба можна охарактеризувати як безліч усіх живих істот, що живуть у воді, плавають, мають  зябра, плавці і хвіст.

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

Формальне поняття, або концепт, можна представити як двійку (A, B), де Aобсяг поняття (экстенсионал, extent), тобто всі об'єкти або елементи з деякої універсальної безлічі V, що охоплюються цим поняттям, а B – це зміст поняття (интенсионал, intent), що є безліччю ознак (атрибутів), що визначають дане поняття. Атрибути – це властивості об'єктів, якими вони володіють. Вони поділяються на двох категорій: прості атрибути, що або є, або їхній ні, і багатозначні атрибути, наприклад, довжина, вартість та інше, коли атрибут може приймати безліч значень.

Між обсягом і змістом поняття існує зворотна залежність: чим більше обсяг, тим менше зміст. Наприклад, поняття юрист можна визначити як безліч усіх людей, що мають юридичне утворення. Поняття суддя можна визначити як безліч людей, що мають юридичне утворення, що працюють у суді і виконуючих цілком визначені обов'язки. Таким чином, безліч суддів є підмножиною безлічі юристів, тобто додавання нових властивостей збільшило потужність безлічі ознак і зменшило потужність безлічі об'єктів.   

Для формалізації понять і встановлення зв'язків між ними традиційно використовується мова логіки предикатів.

Рис.  1. Співвідношення між обсягом поняття і його змістом

Нехай перемінна x приймає значення на безлічі всіх людей. Це безліч у філософській логіці називається универсумом міркування, або родом поняття; у теорії предикатів воно називається областю визначення предиката.  На цій безлічі можна визначити два предикати: P(x) – “x – юрист”, Q(x) – “x – суддя”. Тоді область істинності B предиката P(x) є обсяг поняття юрист, а область істинності A предиката Q(x) – обсяг поняття суддя. Очевидно, що  B (див. мал.4), тобто кожен суддя є юристом, що виражається за допомогою логічної імплікації: x(Q(x)  P(x)).

Більш складна структура поняття:

У ИИ, так само, як у повсякденному житті, термін “поняття” має більш широкий зміст. Обсягом поняття можуть бути не тільки об'єкти, але і факти, події, дії і т.п. У будь-якому випадку поняття має двох характеристик: экстенсионал і интенсионал. У теорії представлення знань під экстенсионалом розуміється набір конкретних фактів, що відповідають даному поняттю. Наприклад, поняттю рухатися (рух)відповідають дії: йти, бігти, повзти, стрибати, їхати, нестися, і ін. Усі ці дії складають интенсионал поняття рухатися. Экстенсионал може бути кінцеве або нескінченним, наприклад, поняття парні числа має нескінченний экстенсионал. У цьому випадку неможливо визначити экстенсионал перерахуванням елементів предметної області. Тоді задають деяке характеристичне правило, що дозволяє визначити, чи належить елемент даному чи поняттю ні. У даному випадку таким правилом є наступне: якщо при розподілі на 2 число в залишку дає 0, то воно належить экстенсионалу поняття “парне” число. Це визначення і буде интенсионалом даного поняття. Ну, а саме поняття визначається областю істинності предиката “x - парне число”, де x N.

Між декларативним і процедурним представленням, з одного боку, і интенсионалом і экстенсионалом, з іншої, існує очевидний зв'язок. Экстенсионал – це набір конкретних даних, заданих у декларативній формі. Интенсионал, як правило, задає процедуру, що дозволяє визначити приналежність того або іншого факту або об'єкта деякому поняттю. Інтелект виділяє знання, відокремлює них від даних, що завжди задаються экстенсионально.

Звичайно поняття представляються у виді знака.

ЗНАК-ТРИКУТНИК ФРЕГЕ

Трикутник Фреге розглядають як визначення поняття знак.

Знак є триєдність, що складається з імені, концепту і представлення. Знак позначає деяке поняття – концепт. Це зміст знака, його семантика, його значення. Ім'я – це назва знака, його позначення, його синтаксис. Представлення – це те, що представляє знак. Це представлення звичайне зв'язується з реальним світом, у той час, як ім'я і концепт належать ментальному світові людини. У ролі денотата можуть виступати предмети зовнішнього світу (суб'єкти й об'єкти), події, явища або процеси, – усе, що може одержати деяке ім'я, про що мається деяке представлення і визначене знання. Наприклад, стіл має ім'я (стіл, table і т.д. на інших мовах), йому відповідає поняття, тобто концепт (яке, до речі, досить важко описати – це те, за чим їдять, за чим сидять і т.д.), а конкретний стіл, на який ми дивимося зараз – це денотат столу. Згадуючи інші типи конкретних столів (інші денотати), ми можемо виділити характерні ознаки столу як концепту  і скласти його опис.


ЛЕКЦІЯ 9.Поняття відносини

Для позначення якого-небудь зв'язку між об'єктами або поняттями в математику часто користуються поняттям відносини. Наприклад, властивість елемента належати або не належати безлічі є відношенням « X», причому, якщо елемент належить безлічі, то відношення є щирим, а якщо не належить, те помилковим. Включення безлічі в іншу безліч «X  Y» також є відношенням. На безлічі людей задане відношення споріднення, наприклад, «x – батько y». Якщо взяти конкретних людей і підставити їхні імена замість x і y, то ми одержимо щире або помилкове висловлення, наприклад: «Лаий – батько Эдипа» — щире висловлення, «Поліб — батько Эдипа» — помилкове. У цьому змісті відношення також є предикатом, що звертається в щире або помилкове висловлення при підстановці в нього конкретних елементів з області визначення.

Визначення 1. Декартовым добутком безлічей X і Y називається безліч всіх упорядкованих пар <x, y>, таких, що  X і  Y. Це позначається як:

 Y {x, y|x  X, y  Y}.

Приклад. Нехай дані безлічі X = {1, 2} і Y = {2, 3, 4}. Декартово произвение цих двох безлічей:  Y = {<1, 2>, 1, 3, 1, 4, <2, 2>, 2, 3, 2, 4}. Розглянемо підмножину цього декартового добутку A = {<1, 2>, 1, 3, 1, 4, 2, 3, 2, 4}. Це не що інше, як відношення : x  y — «x менше y». На тім же безлічі упорядкованих пар можна виділити ще одне відношення 1 y = x + 1 — це підмножина {<1, 2>, 2, 3}. Інше відношення 2: x = y — це підмножина {<2, 2>}.

Визначення 2. Безліч упорядкованих пар утворить бінарне відношення. Позначається: xу   або xу. Таким чином, бінарне відношення — це деяка підмножина декартового добутку двох безлічей. Якщо — деяке відношення, то вираження x, у   і xв еквівалентні і читаються як «x знаходиться у відношенні до у».

Природним узагальненням поняття бінарного відношення є поняття n-арного (n-місцевого) відносини, обумовленого як підмножина декартова добутку n безлічей:

X1  X2  ...  Xn = {xi1xi2, ..., xin  | xi1  X1xi2  X2, ..., xin  Xn}.

n-арное відношення являє собою безліч упорядкованих n-ок (читається: «энка»). Упорядковану n-ку називають інакше кортежем. Підмножина кортежів з n елементів утворить n-арное відношення. При n = 2 має місце бінарне відношення, при n = 3 використовується термін тернарное відношення.

Приклади.

Для деяких відносин прийняті спеціальні позначення.

Рівність: x = y;  Тотожність:  y. Нерівності: x  y, x  y; xy; > y. Приналежність: x  Y; x  Y. Включення: X  Y; X  Y. Конгруентність: x  y.

  •  Безліч {<2, 4>, <7, 3>, <3, 3>, <2, 1>}, будучи безліччю упорядкованих пар, є бінарне відношення. Не маючи ніякого конкретного значення, це відношення, природно, не має і спеціальної назви.
  •  Якщо позначає відношення материнства, то <Джейн, Джон>   означає, що Джейн є матір'ю Джона.
  •  «x і y – батьки z» — тернарное відношення.

Визначення 3. Областю визначення відносини (позначення: D) називають безліч перших координат елементів з , областю значень відносини (позначення: R) — безліч других координат елементів з .

Наприклад, як областю визначення, так і областю значень відносини включення для підмножин безлічі U є безліч (U); областю визначення для відношення материнства служить безліч усіх матерів, у той час, як область значень цього відношення — безліч усіх людей.

Способи завдання відносин

Графік відносини

Аналітична геометрія площини ґрунтується на допущенні про те, що між крапками евклідової площини і декартовым добутком  R існує взаємно однозначна відповідність. Кожній крапці на площині відповідають її координати — упорядкована пара <x, y>. Тому відношення на безлічі R можна зображувати на площині деякою конфігурацією або безліччю крапок. Наприклад, відношення рівності можна зобразити у виді прямій y = x у декартовой системі координат.

Визначення 4. Якщо основним предметом вивчення служать відносини в R, то безліч крапок, що відповідають елементам відносини, називають графіком цього відношення.

Графічний спосіб завдання безлічі

Якщо задано відношення xy,  X,  Y, то елементи безлічей X і Y можна зображувати крапками на площині, а упорядковану пару — лінією (дугою) зі стрілкою, спрямованої від x до y:  .  Наприклад, відношення 1 = {<xi, xi>, <xi, xg>} може бути представлене у виді графа, зображеного на мал. 5. Відношення 2 = {1, 2, 2, 3, 3, 1} може бути представлене у виді орієнтованого графа (див. мал.).

Граф відносини 1.

Граф відносини 2.

Матричний спосіб завдання відносин

Задамо відношення : »x дружить з у» на безлічі M2, де М = {a1, a2, a3, a4}— безліч персонажів. Це відношення можна представити у виді таблиці (матриці), елементи якої дорівнюють одиниці, якщо між відповідними елементами є відношення дружби, і нулеві в противному випадку.

a1

a2

a3

a4

a1

1

0

1

0

a2

0

1

0

0

a3

1

1

1

1

a4

0

0

1

1

З цієї таблиці видно, що a1 дружить з a3, a2 не дружить ні з ким, крім як із самим собою, а a3 дружить з усіма. Такий спосіб завдання відносин називається матричним способом. У цьому випадку відношення    Y представляється у виді матриці = || aig || c елементами aig, де i -номер рядка, g — номер стовпця. aig = 1, якщо елементи xi і yg знаходяться у відношенні , і aig = 0 у противному випадку.

Властивості відносин

Визначення. Відношення на безлічі X називається рефлексивним, якщо для будь-яких  X виконується xx.  Якщо для всіх  X виконується xx, то відношення називається антирефлексивним.

Приклади. Відношення рівності рефлексивно. Відношення x  y, x, yR рефлексивно, тому що x  x. Відношення x  y, x, yR антирефлексивно, тому що не здійсненно x  x.

Визначення. Відношення на безлічі X називається симетричним, якщо для будь-яких  X,  X, з xy випливає yx. Іншими словами, відношення симетричне, якщо всякий раз, як виконується xy, виконується і yx.

Приклади. З того, що »x родич y», випливає, що «y родич x», — відношення симетричне. Відношення «x – сестра , визначене на безлічі всіх людей, несиметрично: можливо, що y є братом x. Онако те ж відношення, визначене на безлічі жінок, є симетричним.

Визначення. Відношення на безлічі X називається антисиметричним, якщо для будь-яких x X, з того, що xy і yx, випливає x = y.

Приклади. Відношення x  y антисиметрично: з того, що x  y і y  x, випливає, що x = y, тобто це той самий елемент.

Якщо для будь-яких x, y  Х з того, що xy, випливає, що не виконується yx, то відношення називається асиметричним.

Відносини «x предок у» і «у нащадок x» асиметричні, причому друге є зворотним до першого. Відношення строгого порядку x < y є асиметричним: якщо виконується x < y, те не виконується y < x.

Визначення. Відношення називається транзитивним, якщо з того, що xy і yz, випливає xz.

Приклад. Якщо «x предок y» і «y предок z», то «x предок z», — відношення транзитивно. Відношення x < y, де x, y  R , транзитивно: якщо x < y і y < z, те x < z. Відношення «x любить y», у загальному випадку нетранзитивно: якщо x любить y, а y любить z, те з цього не випливає, що x любить z.

Відношення еквівалентності

Визначення. Відношення, що має властивості рефлексивности, симетричності і транзитивності, називається відношенням еквівалентності.

Приклади відносин еквівалентності.

Відношення рівності на будь-якій безлічі є відношенням еквівалентності, причому відношення рівності є в деякому змісті мінімальним (граничним) случаємо відносини еквівалентності.

Геометричне відношення подоби трикутників на площині є відношенням еквівалентності.

Відносини порівнянності по модулі числа n у Z: x порівнянно з у по модулі числа n, якщо різниця x – у поділяється на n. Позначається: x  у (mod n). Наприклад: 3 6(mod 3), 7  13(mod 3).

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

Твердження виду sin2x + cos2x = 1, (a + b)(a – b) = a2 – b2, що складаються їхніх формул, з'єднаних знайомий рівності, задають бінарне відношення на безлічі формул, що описують суперпозиції елементарних функцій. Це відношення равносильности також є відношенням еквівалентності: формули рівносильні, якщо вони задають ту саму функцію.

Відношення «студенти x і y учаться в одній групі», де x, y  {«студенти першого курсу»}.

Відношення «жити в одному районі», визначене на безлічі людей, що живуть у м. Києві, є відношенням еквівалентності.

Безліч усіх жителів Києва розбивається останнім відношенням еквівалентності на ряд непересічних підмножин, у даному випадку на безлічі людей, що живуть у тому самому районі. Два жителі вважаються еквівалентними по даному відношенню, якщо вони живуть у тому самому районі, і в цьому змісті вони нерозрізнені, тобто вони володіють тим самим властивістю: «жити в районі «ХХХ». Ця властивість є визначальною властивістю (предикатом) безлічі всіх жителів району «ХХХ». З іншого боку, не можна жити в двох (і більш) районах відразу (у всякому разі, відповідно до прописки), тому безлічі жителів різних районів не перетинаються. Таким чином, відношення «жити в одному районі» розбиває всю безліч жителів міста на ряд непересічних підмножин, таких, що усередині кожної підмножини всі жителі еквівалентні по даному відношенню, і ніякі два жителі різних підмножин не знаходяться у відношенні еквівалентності один з одним. Такі підмножини називаються класами еквівалентності.

Дамо більш строге визначення.

Визначення. Нехай на безлічі X задане відношення еквівалентності . Тоді підмножина A  X називається класом еквівалентності по відношенню , якщо для будь-яких елементів x, y  A виконується відношення xy.

Можна побудувати класи еквівалентності в такий спосіб. Виберемо елемент a1, що належить X, і утворимо підмножину A1  X з a1 і всіх елементів, еквівалентних a1. Це буде клас еквівалентності A1. Далі виберемо елемент a2  X і утворимо клас A2, що складається з всіх елементів, еквівалентних a2, і т.д. Одержимо систему класів A1, A2, ..., таку, що будь-який елемент ai  X входить тільки в один клас, об'єднання всіх безлічей A1  A2  ... утворить безліч X, і для будь-яких i, j Ai  Aj = , тобто безліч класів еквівалентності утворить розбивка безлічі X.

Отримана система класів еквівалентності має наступні властивості.

Нехай є відношення еквівалентності на X. Тоді безліч класів еквівалентності по відношенню є розбивка безлічі X. Назад, якщо є деяка розбивка безлічі X, а відношення таке, що ab тоді і тільки тоді, коли  A,  A,  , те є відношення еквівалентності на X.

На підставі цієї теореми можна дати конструктивне визначення відносини еквівалентності: відношення на безлічі Х називається еквівалентністю, якщо існує розбивка Х на підмножини {A1, A2 ,..., An} таке, що відношення xу виконується тоді і тільки тоді, якщо x і в належать тому самому підмножині. Будемо позначати клас еквівалентності, породжений елементом  X через [a], якщо  [a]. Тоді, якщо ab, те [a] = [b].

Визначення 2.18. Безліч класів еквівалентності безлічі X по відношенню називається фактором-безліччю безлічі X по відношенню і позначається [X/].

Приклади. Усі класи еквівалентності по відношенню рівності складаються з одного елемента. Фактор-безліч по відношенню рівності складається з елементів самої безлічі.

Усі подібні один одному трикутники складають один клас еквівалентності. Наприклад, безліч рівносторонніх трикутників складає один клас еквівалентності, безліч прямокутних рівнобедрених трикутників — інший і т.д. Фактор-безліч — безліч усіх можливих трикутників — нескінченно.

Розглянемо відношення порівнянності по модулі 3 на безлічі Z: xy  x  y(mod 3). Запис x  y(mod 3) означає, що різниця ху поділяється на 3 без залишку. Будемо позначати це так: xy   (ху)/3.

З'ясуємо, якими властивостями володіє це відношення. Нехай х, у  Z.

1. Рефлексивность: для всякого x xx. Дійсно, (x – x)/3 = 0/3 = 0; 0  Z, отже, відношення рефлексивне.

2. Симетричність: якщо xy, те вх.

Нехай (х – у)/3 = k  Z. Тоді вх  (у – х)/3 = –(х – у)/3 = –k  Z. Отже, умова симетричності виконується.

3. Транзитивність: з xy і вz випливає xz.

Нехай (х–у)/3 = k1  Z, тобто х–у = 3k1, і (y–z)/3 = k2  Z, тобто y–z = 3k2. Вирішимо цю систему рівнянь, склавши них: х–у+y–z = 3(k1+k2), тобто x–z = 3(k1+k2)= k3  Z. Умова транзитивності виконується.

Відношення х  у (mod 3) є відношенням еквівалентності. Знайдемо його фактор-безліч [Z/].

Для відношення порівнянності по модулі 3 на безлічі Z фактор-безліч буде складатися з усіх чисел виду a+3k, де kZ. Довільне число х можна записати у виді 3q+r, 0  < 3. У той самий клас еквівалентності потраплять усі числа, що дають при розподілі на 3 однакове число r у залишку. Ми одержимо три класи еквівалентності: [0] = {0, 3, 6, 9, 12, …}; [1] = {1, 4, 7, 10, 13, …}; [2] = {2, 5, 8, 11, 14, …}... У клас [0] попадають усі числа, що поділяються на 3 без залишку, у клас [1] — усі числа, при розподілі на 3 дающие в залишку 1, і в клас [2] — усі числа, що дають у залишку 2.

Кожен клас можна охарактеризувати одним представником цього класу, і в даному випадку таким представником зручніше за усе вибрати залишок r. Отже, фактор- безліччю Z по відношенню відносини х  у (mod 3) буде [Z/] = {[0], [1], [2]}.

ЛЕКЦІЯ 10.Відношення порядку

Основні поняття теорії ґрат

Відношення часткового порядку визначається як відношення, що задовольняє наступним трьом властивостям:

Р1.  x  x     –  рефлексивность,

Р2. якщо x  y і y  x, то x = y  –  антисиметричність,

Р3. якщо x  y і y  z, то x  z  –  транзитивність.

Наприклад, відношення включення безлічей  B, тобто “A – підмножина B”,  є відношенням порядку. Для нього виконуються всі перераховані вище властивості:

 A – будь-яка безліч включена саме в себе;

якщо  B  і  A, те B, тобто безлічі і B  рівні;

якщо  B  і  C, то  C, – властивість транзитивності неважко перевірити за допомогою діаграм Венна.

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

Якщо в упорядкованій безлічі для будь-яких двох елементів не виконується властивість рефлексивности, тобто x  y і x  y, то таке відношення називається  відношенням строгого порядку і позначається x < y. Наприклад, відношення “x – предок y”, визначене на безлічі всіх людей, є відношення строгого порядку.

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

У частково упорядкованій безлічі не кожні два елементи знаходяться у відношенні порядку; у такій безлічі є непорівнянні елементи. Як приклад розглянемо безліч усіх підмножин безлічі P = {a, b, c}, тобто множина-ступінь (Р) = {, {a}, {b}, {c}, {ab}, {ac}, {bc}, {abc}}. Це частково упорядкована безліч по відношенню включення: {a {ab}, {a {abc}, {ab {abc},   {a},   {b},   {c}, і так далі, однак безлічі {a}, {b}, {c} і безлічі {ab}, {ac}, {bc} непорівнянні.

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

P4.  x,y: x  y або y  x.

Наприклад, безліч натуральних чисел є ланцюгом; підмножина A = {, {a}, {ab}, {abc}} безлічі (Р)  з відношенням порядку    {a {ab {abc} утворить ланцюг.

Оскільки властивості P1, P2, P3 задають найбільш загальний тип порядку, частково упорядковані безлічі називають просто упорядкованими, на відміну від лінійно і строго упорядкованих безлічей.

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

Говорять, що “a покриває b” в упорядкованій безлічі X, якщо b  a і не існує такого xX, щоб   a. Тоді упорядкована безліч можна зобразити у виді графа, що будується знизу нагору: якщо елемент b покриває елемент a, те він розташовується вище елемента a і з'єднується з ним прямій. Отриманий граф називається діаграмою упорядкованої безлічі, або діаграмою Хассе (див. мал. 1).

    a)    b)   c)

Рис.  1.

а).   b покриває a;   b).    а покриває b і з;    с).     а, з покривають b.

Діаграма Хассе може бути отримана з ориентированого графа відносини порядку x  y, де x X, видаленням петель і транзитивно замикаючих дуг. Якщо два елементи a, b  X знаходяться у відношенні порядку a  b, то на діаграмі існує шлях з а в b. Таким чином, будь-яка кінцева упорядкована безліч з точністю до ізоморфізму визначається своєю діаграмою.

Рис.  2. Приклади діаграм Хассе

На мал. 2-а зображена діаграма ланцюга натуральних чисел {1, 2, 3, 4}, на мал. 2-b – діаграма безлічі S = {{a}, {b}, {ab}, {abc}, {abcd}}, упорядкованого відношенням включення. Ми бачимо, що кожен вышележащий елемент на діаграмі “більше” усіх, лежачих нижче його. Таким чином, немає необхідності стрільцями указувати відношення порядку між елементами: це легко визначити за рівнем, що займає кожен елемент на діаграмі Хассе. Тому діаграма Хассе звичайно зображується без стрілок.

Якщо в упорядкованій безлічі X існує єдиний елемент а, такий що xX (а  х), то а називається найменшим елементом упорядкован-безлічі, або инфимумом безлічі (позначається inf). Якщо існує єдиний елемент b, такий що xX (x  b), то b називається найбільшим елементом, або супремумом безлічі X (позначається: sup).

З визначень випливає, що будь-яка упорядкована безліч може мати тільки один найменший і один найбільший елемент. Ці елементи часто називають нулем і одиницею упорядкованої безлічі відповідно, і позначають 0 і I.

На мал. 2-а inf=1 і sup=4; на мал.2-b sup= {abcd}, а inf відсутній. Однак, оскільки будь-яка безліч містить у собі порожня безліч, ця діаграма може бути добудована так, як показано на мал. 2-з.

Упорядкована безліч, у якому існують найбільший і найменший елементи, називають упорядкованою безліччю з нулем і одиницею. Тоді. будь-який інший елемент безлічі лежить між нулем і одиницею, тому елементи 0 і I, якщо вони існують, називаються універсальними гранями безлічі Р. 

Мінімальним елементом упорядкованої безлічі X називається такий елемент а, що ні для якого xX не виконується умова  а, а максимальним елементом називається такий елемент b, що ні для якого xX не виконується умова b  x.

Неважко показати, що найменший елемент завжди є мінімальним в упорядкованій безлічі, а найбільший – максимальним, але зворотне здійсненно далеко не завжди. У розглянутому вище прикладі на мал. 2-b безліч {abcd} є найбільшим елементом і, у той же самий час, максимальним, а безлічі {a} і {b} є мінімальними елементами, у той час як найменшого елемента в цій безлічі не існує.

Будь-який кінцевий ланцюг містить найбільший і найменший елементи, що є мінімальним і максимальним елементами.

ЛЕКЦІЯ 12

Ґрати

Розглянемо безліч на мал. 2-з. Для двох елементів x={a}, y={ab} выполнятется відношення порядку:  y, тобто {a {ab}. Для цих двох елементів {a}= inf{x, y} є точною нижньою гранню, {a, b}= sup{x, y} є точною  верхньою гранню. Елементи {a}, {b} непорівнянні. Однак для них існує елемент u = , такий що u  x і u  y. Цей елемент – “найближчий нижній сусід” – і буде точною нижньою гранню елементів {a} і {b}: inf{{a}, {b}} . Йому відповідає перетинання даних безлічей. Точною верхньою гранню цих двох елементів буде елемент v, такий, що x  v  і y  v, і не існує такого z, щоб x   v і y   v. Цей елемент – “найближчий верхній сусід” – є безліч {ab}= sup{xy}, що є об'єднанням двох даних безлічей.

Побудуємо діаграму Хассе для множини-ступеня (Р) = {, {a}, {b}, {c}, {ab}, {ac}, {bc}, {abc}} (мал. 3). Тут точною нижньою гранню підмножин є їхнє теоретико-множинне перетинання, наприклад, для {a} і {b} це , для {a, b} і {b, c} це {b} і т.д., а точною верхньою гранню двох підмножин є їхнє теоретико-множинне об'єднання, наприклад, для {a} і {b} це {a, b}, для {a, b} і {b, c} це {a, b, c} і т.д.

Дивлячись на діаграму (P), можна зробити висновок, що в інтерпретації теорії множин операції sup (xy) відповідає операція об'єднання, а inf (xy) – операція перетинання безлічей. Ця аналогія послужила підставою для вибору найменування операції перебування точної верхньої грані – “об'єднання” (позначається ), і точної нижньої грані – “перетинання” (позначається ), у теорії ґрат (див. [1]).

Тепер ми можемо визначити, що таке ґрати.

Рис.  3.Діаграма Хассе (P)

Ґратами називається упорядкована безліч, у якому будь-які два елементи x і y мають точну нижню грань, називану перетинанням, (позначається inf{xy}  xy), і точну верхню грань, називану об'єднанням (позначається sup{xy}  xy).

Безліч (P) на мал. 3 утворить ґрати. Узагалі, безліч усіх підмножин деякої безлічі X утворить ґрати. Будь-який ланцюг також є ґратами, у якій xy збігається з меншим, а xy з великим з елементів x, y.

Принцип подвійності.

Відношення, зворотне для відношення порядку, саме є упорядкованістю. Дійсно, якщо x  y (x менше y“) , те y  x (y більше x“). Наприклад, якщо x  y є відношення “x  y, те зворотне йому відношення y  x  є “ x“. Для будь-якого упорядкованої безлічі X безліч Y, обумовлене на тих же елементах відношенням, зворотним до упорядкованості в X, називається двоїстою безліччю. Наприклад, для множини-ступеня двоїстим йому безліччю буде безліч з відношенням порядку  A – “B включає A”.  Діаграма такої безлічі буде “переверненої”: нулем цієї безлічі буде безліч P={abc}, а одиницею – ; операції sup{xy} буде відповідати перетинання, а inf{xy} – об'єднання підмножин.

ВЛАСТИВОСТІ ҐРАТ

У будь-якій у-безлічі для операцій перетинання й об'єднання виконуються (при визначених у них вираженнях) наступні закони:

 x = x,  L1.

 x = x — идемпотентность;

 y =  x,  L2.

 y =  x — коммутативность;

 ( z) = ( y)  z,  L3.

 ( z) = ( y z — ассоциативность;

 ( y) = x,  L4.

 (x  y) = x — поглинання.

Крім того, нерівність x  y рівносильна кожному з умов:

 y = x і  y = y — умова сумісності.

Дистрибутивні ґрати

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

Визначення. Ґрати називаються дистрибутивної, якщо в ній виконуються тотожності:

 ( z) = ( y ( z)    xyz, L6'

 ( z) = ( y ( z)    xyz. L6"

Булевы ґрати

Визначення. Булевой ґратами називаються дистрибутивні ґрати з доповненнями.

По теоремі 6.7: c  x = c  y і c  x = c  y  x = y, тобто кожен елемент дистрибутивних ґрат з доповненнями має не більш одного доповнення.

У булевой ґратам будь-який елемент х має одне і тільки одне доповнення х'. При цьому:

x  x' = 0,  x  x' = I,     L8

(x')' = x, L9

(x  y)' = x'  y',          (x  y)' = x'  y'. L10

Оскільки доповнення в булевой алгебрі єдині, її можна розглядати як алгебру з двома бінарними операціями й однієї унарной операцією: B = <L, , , >.

Рис.  1 Булевы ґрати.

Визначення. Булевой алгеброю L = <B, , , > називається алгебра з операціями , , ', що задовольняють умовам L1 — L10.

Приклад. На мал. 6.2 показані булевы ґрати 2, 22, 23, 24.

ЛЕКЦІЯ 13

Особливості погано структурованих областей і об'єктів керування.

1. Унікальність. Звичайні системи керування (наприклад, виробничими і технологічними процесами) можуть тиражуватися. Такі системи стерпні з одного об'єкта на іншій. Наприклад, якщо створено систему керування электоропотреблением, те вона може застосовуватися в будь-якій мережі, що задовольняє умовам, для яких вона створена. Але існують об'єкти, що мають таку структуру і функціями, що до них не можна застосувати типову стандартну процедуру керування. До таких об'єктів відносяться суспільні, соціальні, політичні, адміністративні структури. Кожен такий об'єкт унікальний, тому що на природу і структуру його впливають неповторні особливості середовища, історичного періоду, індивідуальні характеристики особистостей. Такі системи створюються фактично один раз для рішення реальних задач, і перенос їх вимагає великих витрат або просто неможливий.

2. Відсутність формализуемой мети функціонування. Ця особливість властива природним системам, що не створюються людиною, наприклад, екологічним, природним системам, а також суспільній і адміністративній системам. Метою функціонування такої системи є її працездатність у цілому, підтримка деяких параметрів у заданих межах, однак формалізувати таку мету у виді деякого критерію, як правило, не можна. Наприклад, в екологічної системи усі фактори, що впливають на її функціонування, настільки численні, а зв'язку між ними настільки складні і неясні, що задати деяку функцію, що описує мету її функціонування, у принципі не можна. У суспільних системах головне значення має система відносин між її елементами. Ціль її функционирания є існування як таке, тобто підтримка даної суспільної формації, забезпечення рівня життя населення, системи виробничих і соціальних відносин.

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

В оптимальному керуванні події повторюються. Оптимальна система керування прогнозує події на підставі моделі, що враховує закономірності протікання процесу, виявлені в його повтореннях, видає оптимальне керування в систему й одержує відгук по системі зворотного зв'язку, враховує його, і процес повторюється. Саме повторюваність процесу зі збереженням усіх його властивостей дозволяє будувати оптимальні моделі керування. Адекватність моделі перевіряється на досвіді за результатами керування. Адаптація її відбувається на підставі повторення процесу, коли нові параметри моделі дозволяють одержати менші відхилення реального значення цільової функції від її оптимального значення.

У природних і суспільних системах події не повторюються в точності. Існуючі аналогії не мають характеру логічної або статистичної закономірності.

4. Динамічність. Структура і функціонування об'єкта змінюється з часом, тобто об'єкт еволюціонує. Наприклад, міняється структура міста, міняється суспільний лад і структура органів керування, міняється природа й екологія місцевості в процесі життєдіяльності людини. Керування такими системами повинне бути адаптивним, здатним змінюватися зі зміною об'єкта.

5. Непонота опису (наявність Не-факторів). Під Не-факторами розуміється неточність, неповнота, невизначеність, невірогідність даних, що описують об'єкт. При описі об'єктів, про які мова йде, ми зіштовхуємося з двома, здавалося б суперечними один одному властивостями: великою кількістю ознак, що описують об'єкт, і неповнотою опису об'єкта. Велика кількість ознак породжується складністю таких об'єктів, багатогранністю проблеми. На них можна дивитися з різних точок зору, виділяючи різні аспекти з різним ступенем деталізації. Опис проблеми виробляється, як правило, експертами-фахівцями в даній області, незнайомими з математичними методами теорії керування (політологами, соціологами, біологами, і т.п.). Зведення, одержувані від них, суб'єктивні, залежать від думки експерта, що бачить проблему з погляду своєї спеціальності, тому система ознак і їхніх оцінок у них різна, що породжує їхнє різноманіття. Оцінки й описи експертів, отримані по спеціальних методиках витягу знань, дозволяють оцінити ступінь невірогідності тієї або іншої оцінки і врахувати неї в моделі, скоротити розмірність простору ознак, але не забезпечують повноти опису. Інформація, отримана з інших джерел, – текстів газет, повідомлень, телебачення, – носить опосередкований характер і також містить неточності і невизначеності, породжувані невірогідністю джерел, посилань, багатозначністю природної мови, використанням модальностей і т.п. Самі описи, оцінки значень ознак, носять звичайно якісний вербальний характер, оцінити ступінь їхньої невірогідності не представляється можливим, а без цього неможливо бороти з невірогідністю моделі.

6. Наявність волі волі. Об'єктами керування можуть бути не тільки штучні системи, але і люди, що мають волю волі. Пророчити поводження людини як об'єкта керування або елемента системи часто буває неможливо. Людина діє в системі з обліком своїх особистих цілей і інтересів. Поводження людей важко врахувати при моделюванні об'єкта керування.

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

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

ЗАДАЧІ ПРИЙНЯТТЯ РІШЕНЬ

Процедуру ухвалення рішення можна інтерпретувати як рішення задачі. У загальному виді задачу інтерпретують як те, що вимагає виконання або дозволи [Ожегов, 1988].

Задачі керування поділяють на добре і слабко структуровані. До добре структурованого відносяться задачі, що можуть бути точно сформульовані і вирішені кількісно, – всі інші відносяться до погано структурованих задач. Добре структуровані задачі згодом стали називати кількісними, а слабко структуровані – якісними [Оптнер, 1969]. Якщо до першого відносять традиційні задачі з кількісними значеннями перемінних і відносин між ними, то до других – задачі, у яких мети, структура, умови відомі лише частково і характеризуються великим обсягом Не-факторів: неповнотою і недовизначеністю описів, цілей, структури і показників функціонування. О. И. Ларичев [Ларичев, 1964] доповнив дану класифікацію, увівши категорію неструктурованих задач, до яких відносяться такі задачі керування, у яких усі перемінні задані лише описово і невідомі які-небудь кількісні залежності між ними. Добре структуровані задачі інакше називають замкнутими, а слабко структуровані і неструктуровані – відкритими [Козелецкий,1979].

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

Формалізація задачі прийняття рішень

Модель прийняття рішень

Задача прийняття рішень у штучному інтелекті розглядається як пошук у просторі станів. У загальному виді задача формулюється в такий спосіб.

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

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

Задачу ухвалення рішення (ЗПР) можна описати набором:

<S, S, S0, Sk, P, Q>,   (1)

де S – безліч станів (ситуацій), називане универсумом, SS – підмножина можливих (припустимих) станів, S0 Sпідмножина початкових станів, Sk  S підмножина кінцевих, або цільових станів, P:SS – кінцева безліч правил перетворення, Q – безліч критеріїв оцінки знайденого рішення. Кожне правило Pi є функцією Pi:SiS, де Si – область визначення Pi. Вважається, що правило примено до стану s, якщо sSi.

Рішенням ЗПР є послідовність застосувань правил (P1, P2 , …, Pn) , така що

композиція P1P2 Pn(s)Sk, s)S0...

послідовність P1, P2 , …, Pn задовольняє критеріям з безлічі Q.

Якщо елементи набору (1) не змінюються в процесі пошуку рішення, то маємо ЗПР у замкнутій формі, що відповідає статичної проблемної області (ПО); якщо корекція набору припустима, наприклад, можливе поповнення S, S, P, те маємо ЗПР у відкритій формі, що відповідає динамічної ПО.

Для рішення ЗПР можна застосовувати як строгі методи теорії прийняття рішень, так і евристичні.

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

Евристичні методи характеризуються тим, що вони не гарантують одержання  рішення, а одержувані рішення, якщо вони знайдені, характеризуються неповнотою і недовизначеністю. До таких методів відносяться методи правдоподібного висновку.

Процес пошуку рішення відображається звичайно у виді дерева рішень (вирішального дерева), у якому вершини відповідають станам, а ребра – правилам перетворення.

Специфікою погано структурованих задач є їх комбинаторность, т.е швидкий (лавинообразный) ріст вирішальних дерев у процесі пошуку. Задача побудови вирішального дерева в більшості випадків є NP-повною задачею. Тому основа рішення таких задач – евристичні методи, що базуються на обліку специфіки ПО, знань і досвіду експертів, що вирішують подібні задачі.

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

ЛЕКЦІЯ 14

Концептуальні графи

Графічні представлення знань служать для структуризації й узагальнення знань.

Концептуальний граф представляє логічну формулу. Імена й аргументи предикатів представлені в ньому двома типами вузлів. Дуги графа з'єднують імена предикатів з їх аргументами.

Концептуальний граф

Концептуальний граф представлення з бінарними предикатами

При графічному представленні бінарних предикатів кола іноді опускають, а імена предикатів пишуть безпосередньо над стрільцями. Кожен бінарний предикат представимо у виді найпростішого концептуального графа:

Стрілки спрямовані від першого аргументу бінарного предиката (Ім'я_предиката) до другого (Значення_j).

Концептуальні графи n-арных предикатів використовують наступні угоди. Останній, n-й  аргумент вважається вихідним, тобто стрілка до цього аргументу виходить з окружності, що представляє предикат. Всі інші аргументи – вхідні, тобто стрлки від них входять в окружність.

Звичайно усе-таки використовують бінарні предикати. Ім'я бінарного предиката представляє деяку функцію. Відповідний йому вузол називається сполучним вузлом – він зв'язує два аргументи бінарного предиката. Ці аргументи бінарного предиката називаються концептами. Тому такі графи одержали назва концептуальних. Вузли, що відповідають імені предиката називається сполучними, а вузли, що відповідають аргументам, – вузлами-концептами.

Семантичні мережі

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

ФРЕЙМИ

Структура фрейму:

{<ім'я фрейму> <ім'я слота> <значення слота> <ім'я слота> <значення слота> …}

Структура слота:

{<ім'я слота> <1> <v1> … <n> <vn> <q1> <qm> …},

де i – імена атрибутів, характерних для даного слота, vi – значення цих атрибутів або безлічі значень, qi – різні посилання на інші слоты.

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

Приклад.

{<ПОДІЯ> <ДЕ> <значення слота> <КОЛИ> <значення слота> <ЖЕРТВА> <значення слота> ... <СВІДОК> <значення слота> ...}

Фрейм ПРИСШЕСТВИЕ складається зі слотов.

Один зі слотов СВІДОК може мати наступну структуру:

{<СВІДОК>; <ІМ'Я> <значення слота>; <ВІК> <значення слота>; <МІСЦЕ РОБОТИ> <значення слота>; <ПОСАДА> <значення слота>; <АДРЕСА> <значення слота>; <ЩО БАЧИВ>; <ЩО ЗНАЄ> ; …<МОТИВИ>}

СЦЕНАРІЇ (Script)

Сценарій представляється у виді мережі, у якій вершини відповідають фактам, а дуги – зв'язкам, що описують відносини спеціального типу. Ці відносини мають наступну властивість: якщо між вершинами x і y існує безліч шляхів w1, w2, …, wn і маються обидва факти a, b, що відповідають вершинам x і y, те те має місце сукупність фактів принаймні на одному зі шляхів, що з'єднують x і y.

Прикладами таких відносини є: причина – наслідок, частина – ціле, мета – подцель і т.п.

Сценарії у свою чергу поділяються на фрагменти або сцени (chunk). Свзи між фрагментами – тимчасові або просторові. Зв'язку усередині сцени можуть бути найрізноманітнішими.

Методи виявлення таких зв'язків можна розділити на неформальні (робота з експертом) і формальні.

ЛІТЕРАТУРА

  1.  Трахтенброт В.А. Алгоритми й обчислювальні автомати. М.: Світ. Сов. Радіо. 1974. 200 с.
  2.  Трахтенброт В.А. Алгоритми і машинне рішення задач. М.: Гос. изд. физ.-мат. літератури. 1960. 120 с.
  3.  Биркгоф Г. Теорія ґрат. М.: Наука, 1984.
  4.  Булос Дж., Джеффри Р. Вычислимость і логіка. М. Світ, 1994.
  5.  Вагин В. Н. Дедукція й узагальнення в системах исскуственного інтелекту. М., Наука. 1986.
  6.  Горбатов В. А. Основи дискретної математики. М.: Вища школа, 1986.
  7.  Єршов Ю.А., Палютин Е.А. Математична логіка. М.: Наука, 1979.
  8.  Заді Л. Поняття лінгвістичної перемінної і його застосування до прийняття проблемних рішень. М.: Світ, 1976.
  9.  Клини С. К. Введення в метаматематику. М.: Світ, 1957.
  10.  Клини С. К. Математична логіка. М.: Світ, 1973.
  11.  Кофман А. Введення в теорію нечітких безлічей. М.: Радіо і зв'язок, 1982.
  12.  Кузин Л. Т. Основи кібернетики. У 2 т. Т. 2. М.: Енергія, 1979.
  13.  Кузнєцов О. П., Адельсон-Вельский Г. М. Дискретна математика для інженера. М.: Енергія, 1980.
  14.  Кэррол Л. Історія з вузликами. М.: Світ, 1973.
  15.  Лаврів И. А., Максимова Л. Л. Задачі по теорії множин, математичній логіці і теорії алгоритмів. М.: Наука, 1975.
  16.  Мелихов А. Н., Берштейн Л. С., Коровин С. Я. Ситуаційні системи, що радять, з нечіткою логікою.  - М.: Наука. Гл. ред. фіз.-мат. літ., 1990., -272 с.
  17.  Мендельсон Э. Введення в математичну логіку. М.: Наука, 1976.
  18.  Нагель Э., Ньюмен Д. Теорема Геделя. М.: Знання, 1970.
  19.  Поспєлов Д. А. Ситуаційне керування. Теорія і практика. М.: Наука, 1986. - 288 с.
  20.  Робертс Ф. С. Дискретні математичні моделі з додатками до соціальних, біологічних і екологічних задач. М.: Наука, 1986.
  21.  Столл Р. Безлічі, логіка, аксіоматичні теорії. М.: Освіта, 1968.
  22.  Таран Т. А. Основи дискретної математики. Київ: Просвіта, 1998.
  23.  Трахтенброт В.А. Алгоритми й обчислювальні автомати. М.: Сов. Радіо. 1974. – 200 с.
  24.  Фрид Э. Елементарне введення в абстрактну алгебру. М.: Світ, 1979.
  25.  Чень Ч., Чи Р. Математична логіка й автоматичний доказ теорем. М.: Наука, 1983.
  26.  Шрейдер Ю. А. Рівність, подібність, порядок. М.: Наука, 1971.
  27.  Гэри М., Джонсон Д. Обчислювальні машини і труднорешаемые задачі. М.: Світ, 1982.
  28.  Ахо А., Хопкрофт Дж., Ульман Дж. Побудова й аналіз обчислювальних алгоритмів. М.: Світ, 1978.
  29.  Кук С.А. Складність процедур висновку теорем. // Кібернетичний збірник, М.: Світ, 1975. Вып. 12.
  30.  Карпо Р.М. Зведення комбінаторних проблем. // Кібернетичний збірник, М.: Світ, 1975. Вып. 12.


 

А также другие работы, которые могут Вас заинтересовать

83096. Технология и организация торговли декоративной косметикой 97 KB
  На мой взгляд, тема декоративной косметики всегда будет оставаться актуальной. Это объясняется тем, что сегодня декоративная косметика занимает одну из лидирующих позиций на рынке косметики и естественно, что пользуется спросом у покупательниц всего мира.
83097. Разработка конструкции и технология изготовления компьютерного стола 857.76 KB
  Допускается применять плиты древесностружечные по действующей нормативной документации соответствующие по качеству плитам указанных марок; пленки декоративные на основе термореактивных полимеров с неполной степенью конденсацией смолы по действующей нормативной документации.