5. Штучний інтелект

1. Знання. Класифікація знань.

На інтуїтивному рівні знання можна визначити як інформацію, на основі якої можна отримувати нову інформацію, тобто нові знання.

Визначення. Знаннями інтелектуальної системи називається трійка <F, R, P>, де F - сукупність фактів, що зберігаються в пам’яті системи в явному вигляді, R - сукупність правил, які дозволяють на основі існуючих фактів отримувати нові, P - сукупність процедур, які визначають, яким чином слід застосовувати правила.

Знання, доступні системі, складають базу знань цієї системи.

Розрізняють екстенсіональні та інтенсіональні представлення.Під екстенсіональним представленням мається на увазі просто набір фактів, або кортежів, що входять до бази даних. Інтенсіональне представлення - це задання правила, якому підпорядковуються записи у базі даних. Інтенсіональне відношення можна формально визначити як відношення R(A₁, …, A_n ). Вважається, що до бази даних, що описується відношенням R , належать ті і тільки ті факти, які задовольняють йому. Якщо в чисто екстенсіональній базі даних всі факти необхідно зберігати в явному вигляді, то при наявності інтенсіональних представлень це не обов’язково. Нові факти можуть бути породжені відношенням R ,за його ж допомогою може бути перевірена істинність того чи іншого твердження.

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

Типи знань бувають такі:

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

2. Визначення та твердження. Вони ґрунтуються на базових елементах і очікуються бути достовірними.

3. Концепції. Являють собою перегрупування та узагальнення базових фактів.

4. Відношення. Можуть бути як властивостями базових елементів, так і відношення між концепціями. Прикладом відношень можуть бути скрипти.

5. Теореми та правила перезапису. Це частковий випадок породжуючих правил Rз визначеними властивостями. Для використання теорем потрібні експертні правила їх використання. Наявність теорем визначає відмінність експертних систем та реляційних СУБД.

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

7. Стратегії або евристика. Має зворотній до послідовності отримання порядок осмислення інформації. Наприклад, це можуть бути роздуми типу «Я хочу отримати такий результат, а тому мені треба зробити такі дії». Поява експертних систем пов’язана якраз з цією властивістю осмислення інформації людським мозком.

8. Метазнання. Являє собою сукупніть скоефіцієнтів довіри до існуючих знань.

Спосіб задання знань включає два аспекти: спосіб організації знань і модель задання. Вони різняться рівнями задання і рівнем детальності. За рівнями задання виділяють знання нулевого рівня (конкретні і абстрактні знання) і знання більш високих рівнів (метазнання). Перший рівень складають знання про задання знань нульового рівня. Число рівнів може бути продовжено.

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

2. Фреймова модель задання знань.

Теорія фреймів (1975 р. М.Мінський). "фрейм" – англ. Frame ("рамка", "каркас"). Мінський: знання групуються в модулі, і назвав фреймами ці модулі. Інтуїтивно фрейм - каркас, на якому тримаються знання ( або рамка, на основі якої описуються різноманітні об’єкти та ситуації). Мінський: коли людина потрапляє в нову ситуацію, вона співставляє цю ситуацію з тими фреймами, які зберігаються у неї в пам’яті.

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

E.g. Фрейм "Студента". Прізвище, ім’я та по-батькові, факультет, курс => представляються слотами. Опис = заповнення слотів конкретними значеннями. Екземпляри понять утворюються в результаті конкретизації фреймів понять.

Ієрархія понять. Фрейм "Студент" наслідує слоти від фрейму "Людина". Заповнені слоти можуть успадковуватися фреймами-нащадками.

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

Фрейм може мати таку структуру:

1) Ім`я фрейму. Цей ідентифікатор є єдиним в даній фреймовій системі.

Кожний фрейм складається з довільного числа слотів (декілька з них системні, решта - користувача). Слоти: а) IS - A, що вказує на фрейм-предок даного фрейму; b) слот - вказівник фреймів нащадків, який є списком вказівників цих фреймів; с) слот для введення імені користувача, дати визначення, дати зміни, тексту коментаря; d) інші слоти.

Кожний слот в свою чергу задається фіксованою структурою даних.

2) Ім`я слоту - ідентифікатор, унікальний в фреймі. Деякі імена слотів мають смислове навантаження: а) IS - A(визначає тип відношення); b) DESENDANTS (вказівник прямого дочірнього фрейму); c) DEFINED BY (користувач, який визначає фрейм); d) DEFINEDON (дата визначення фрейму); e)MODIFIEDON (дата модіфікації фрейму); f)COMMENT - коментар; g)HAS_PART, RELATIONS - системні і використовуються при редагуванні бази знань і керуванні виведенням.

3) Вказівники наслідування використовуються тільки в фреймових системах ієрархічного типу, що грунтуються на відношеннях "IS - А". Вони вказують, яку інформацію про атрибути слотів фрейму вищого рівня наслідують слоти з таким же ім`ям в фреймі нижчого рівня.

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

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

6) Демон. Тут дається визначення демонів типу if-needed, if-аdded, if-removed. Демоном називається процедура, яка автоматично запускається при виконанні деякої умови. Демони запускаються при зверненні до відповідного слоту. Наприклад, демон if-needed запускається, якщо в момет звернення до слоту його значення не було встановленно, if-added - при підстановці значення в слот, if-removed - при стиранні значення слоту.

Спеціалізовані мови для представлення знань фреймами:KRL та ін. Часто фреймові моделі ще називаються об'єктними. Загальна форма об’єктного представлення визначається як: Об’єкт, (атрибут_j, значення_ j)( j = 1, … m). Об’єктна модель лягла в основу об'єктно-орієнтованих мов програмування, таких, як Smalltalk, C++, Delphi.

Зв’язок між семантичними мережами та фреймами: на сучасному етапі фреймові моделі та семантичні мережі розглядають, як правило, у спільному контексті: -> вузли семантичної мережі - як фрейми з власною внутрішньою структурою; <- можна вводити різноманітні зв’язки між слотами фреймів. Тоді фрейм набуває рис семантичної мережі.

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

Мережні моделі базуються на семантичних мережах. Мережна модель:<I,C₁ ,C₂, ...,C_n ,Г>. I-множина інформаційних одиниць,C₁,C₂,...,C_n-типи зв’язків між інформаційними одиницями, Г-відображення, що задає зв’язки між інформаційними одиницями. Мережні моделі тісно пов’язані з моделями "сутність-зв’язок". Сутність - об’єкт довільної природи. П-сутність: об’єкт, що існує в реальному світі. Його представлення в базі знань ->М-сутність. У базі знань відображаються також зв’язки між сутностями.

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

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

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

	Клас	Об`ємна місткість
Чайник	Властивість	Металевий, фарфоровий, з носиком
	Приклад	Металевий

У вигляді концептуального графа можна представляти будь-яку логічну формулу або словесне висловлювання. (Тоді концептуальний граф – проста семантична мережа, що відповідає одному твердженню). E.g. "Жак надсилає книгу Марі" => предикат ПОСИЛКА(ЖАК_2, МАРІ_4, КНИГА_22), а концептуальний граф матиме вигляд:

Ц ифри потрібні для того, щоб дати кожній сутності своє індивідуальне ім’я. Прямокутники концептуального графа - для представлення аргументів предикатів, а кола - для представлення самих предикатів. Круг і прямокутник з'єднуються дугою, якщо вони є відповідно ім'ям та аргументом того самого предиката. Часто буває корисним представити предикат, що відповідає деякій складній фразі природної мови, у вигляді кон'юнкції бінарних предикатів. Предикат ПОСИЛКА (ЖАК_2, МАРІ_4, КНИГА_22) можна переписати у вигляді: Відправник (Посилка_8, Жак_2); Отримувач (Посилка_8, Марі_4); Що (Посилка_8, Книга_22); IS_A (Посилка_8, Посилки). Предикат IS_A відіграє винятково важливу роль та означає належність деякої сутності до певного типу. Бінарне представлення називають представленням "об'єкт-атрибут-значення". "Об'єкт" є ім'ям бінарного предикату (або назвою сутності, що описується). "Атрибут" є назвою деякої ознаки, або властивості цього об'єкта. "Значення" відповідає конкретному значенню цієї властивості

Семантична мережа - це композиція концептуальних графів, об’єднаних за тими чи іншими правилами. Багато методів логічного виведення на семантичних мережах грунтуються на зв’язку IS_A та понятті наслідування, що тісно з ним пов’язане. Сутність наслідує атрибути типу, до якого вона належить. Якщо для типу визначені конкретні значення атрибутів, сутність, що належить до цього типу, наслідує їх за замовченням

Зв’язок PART-OF показує відношення "ціле - частина". Цей зв’язок показує відношення між екземплярами класу.

л астівка

is-a

птах

E.g. речення "всі ластівки - птахи". Cемантична мережа:

Ластівка - ім`я "Дана", тоді мережу можна розширити наступним чином:

дана

is-a

ластівка

is-a

птах

Тоді з семантичної мережі можна вивести речення: Дана - птах. Механізм наслідування НЕ завжди гарантує правильність висновку.

Приклад семантичної мережі:

4. Продукційна модель задання знань.

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

Визначення. Продукційною моделлю називається представлення знань у вигляді сукупності продукцій. Продукція визначається в як вираз такого вигляду: (i) Q; P; A  B; N Тут (i) - ім'я продукції, за допомогою якого вона виділяється серед усієї множини продукцій; Q - сфера застосування продукції; предметна область, до якої вона відноситься; - умова застосування продукції; A  B - ядро продукції; інтерпретація залежить від конкретної ситуації; часто ядро інтерпретується як "якщо маєш A, зроби B"; N - постумова продукції, постулює процедури, які необхідно виконати після реалізації ядра.

E.g.: МАГАЗИН; У ПОКУПЦЯ ГРОШІ; ЯКЩО ПОКУПЕЦЬ ХОЧЕ КУПИТИ РІЧ, ВІН ПЛАТИТЬ В КАСУ; ЗМІНИТИ БАЗУ ДАНИХ ПРО ТОВАРИ.

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

Відомі стратегії керування вирішенням конфліктів: принцип "стосу книг"; принцип найбільш довгої умови; принцип метапродукцій; принцип "класної дошки"; принцип пріоритетного вибору; принцип керування за іменами.

Компоненти ПС:

1. набір правил, які використовуються як база знань (база правил).

2. робоча пам`ять (де зберігаються умови, які відносяться до конкретних задач предметної області, і результати виведень, отриманих на їх основі).

3. механізм логічного виведення. Він використовує правила в відповідності до робочої пам`яті.

Дві основні стратегії логічного виведення у ПС:

1. для отримання заключення проводиться робота по вибору попередньо записаного вмісту робочої пам`яті, застосуванню правил і доповнень даних в пам`яті (прямим виведенням).

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

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

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

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

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

5. Розпізнавання образів.

Вода на свой вкус (вступление)… Дальше… Базовий принцип: Будь-який об`єкт у природі - унікальний; унікальні об`єкти - типізовані. В природі не існує двох об’єктів, для яких співпадають абсолютно всі ознаки, і це теоретично дозволяє здійснювати ідентифікацію.

Опять Вода: поняття ознак, класифікація обєктів за ознаками, навчання, правила розпізнавання, навчальної вибірки, контрприкладу.

Задача розпізнання без учителя (кластерного аналізу). Класи попередньо не задаються; система повинна сама розділити відомі їй об’єкти на класи.

Зразок у розумінні "класу" визначається як деяка сукупність об’єктів, що мають спільні властивості, або певні спільні ознаки. Більш формально: об’єкти, для яких виконується відношення еквівалентності, або у крайньому разі відношення толерантності, у своїй сукупності складають образ.

Відношення еквівалентності = симетричності+рефлексивності+транзитивності. Відношення толерантності = симетричність+рефлексивність. Більш природним, ніж через відношення толерантності, видається визначення зразку (класу) у рамках теорії нечітких множин.

Системи розпізнавання: розробка системи розпізнавання та власне розпізнавання. 2) Власне розпізнавання - в три етапи: отримання первинної інформації; виділення ознак; класифікація. 1) Розробка системи розпізнавання: формування навчальної вибірки; вибір інформативної множини ознак; навчання.

Прості спеціалізовані методи розпізнавання: співставлення з еталоном, зондів, маркування, квазитопологічного розпізнання. Ці методи вимагають детального вивчення об’єктів, що розпізнаються. Навчання фактично відсутнє, і об’єкти, які розпізнаються, мало змінюються.

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

1) Статистичні методи розпізнавання. Типова постановока задачі: Заданий певний набір класівK₁, … , K_M. Для кожного класу заданий деякий набір його представників. Потрібно для будь-якого об’єкту визначити, до якого класу він відноситься. Кожний об’єкт характеризується певним набором ознак, тобто відображається на деяку точку простору ознак. Цей набір ознак є фіксованим та спільним для всіх об’єктів.

Навчальній вибірці відповідає матриця данихY=(y_ij; i =1,…,q; j = 1, … , n+1). Тут q - загальна кількість представників усіх класів, n - кількість ознак (розмірність простору ознак) y_in+1 - клас, до якого відноситься i- й об’єкт. Будь - якому об’єктові відповідає вектор даних x = (x _j; j = 1,…,n). При цьому природно визначити відстань у просторі ознак, яка являтиме собою мірило схожості об’єктів.

Статистичні методи явно або неявно спираються на гіпотезу компактності. Вважається, що класові відповідає компактна множина точок у деякому просторі ознак. Різні типи ознак: дихотомічні (ознака може бути присутня або відсутня; наприклад - є крила або немає крил); номінальні (наприклад, колір: червоний, синій, зелений і т.п.); порядкові (наприклад, "великий" - "середній" - "маленький"); кількісні. Метрики для кількісних ознак: евклідова відстань та зважена євклідова відстань. Для некількісних: відстані Хеммінга, Кендала, Юла, Рассела і Рао та ін.

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

Теорема Котельникова (теорема Шеннона, теорема відліків) (про частоту дискретизації):Н ехай для функції u(t) визначене перетворення Фур’є, і спектр цієї функціїї неперервний та обмежений смугою частот від 0 до F. Тоді функція повністю визначається своїми дискретами, взятими через інтервали часу t =1 / (2F). Перетворення Фур’є U(f) функції u(t) визначається за формулою :

До класичних методів виділення ознак належать глобальні перетворення: лінійні або нелінійні. До таких перетворень відносяться перетворення Фур"є, Уолша, Хоара. Ознаки - спектральні коефіцієнти відповідних рядів => різке скорочення розмір. простору ознак ("стиск даних").

Попередньою обробкою є також зменшення шумів (фільтри Калмана, Вінера) Статистичні методи розпізнавання: а)імовірнісні та б)детерміністські.

а)Ймовірнісні методи. Матриця даних - набір реалізації деякого випадкового процесу. Класичним є байєсівській підхід. Iдея: мiнiмiзацiя ризику, пов’язаного з помилковим рiшенням. (Його можна розрахувати, якщо відомі умовні густини розподілу векторів ознак за умови, що об’єкт належить до певного класу.)

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

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

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

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

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

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

6. Поняття діалогової системи та її компоненти.

Системи обробки природньої мови – СОПМ.

Спілкуванням – коммунікативна взаємодія.

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

Мета діалога визначає структуру діалогу. Структура діалогу може розглядатись на трьох рівнях: глобальному, тематичному і локальному. Глобальний рівень визначає загальні властивості вирішуваних задач. Тематичний рівень визначається алгоритмом вирішення поставленої задачі і розподілом ролей між учасниками діалогу. На локальному рівні аналізуються конкретні пари “запит - відповідь”.

Узагальнена схема СОПМ

Серед обов`язкових функцій СОПМ можна виділити наступні:

• з нової стрічки ведення діалогу - визначення його структури і ролі, яку виконує пара користувач - система на даному кроці діалогу;

• розуміння - перетворення отримуваних від користувача висловлень на природній мові (ПМ) в висловлення мови внутрішнього задання;

• обробка висловлень - формування і визначення завдань для вирішення задач і підзадач данного кроку діалогу;

• генерація - формування вихідних висловлень природньою мовою.

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

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

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

7. Теорія ігор. Експліцитні та імпліцитні дерева гри.

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

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

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

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

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

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

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

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

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

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

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

Перший гравець має m стратегій i = 1, 2, ..., m, другий – n стратегій j = 1, 2, ..., n. Кожній парі стратегій (i, j) поставлено у відповідність число а_ij, яке виражає виграш першого гравця за рахунок другого гравця, якщо кожен з гравців візьме свою стратегію.

Кожен із гравців робить один хід: перший гравець вибирає свою i-ту стратегію ( ), а другий – свою j-ту стратегію ( ), після чого перший одержує виграш а_ij за рахунок другого (якщо а_ij< 0, то це означає, що перший гравець винен другому суму |а_ij|). На цьому гру закінчують.

Кожну стратегію гравців ,  часто називають чистою стра­тегією.

Якщо розглянути матрицю

                               ,

то проведення кожної партії матричної гри за матрицею А зводиться до вибору першим гравцем i-го рядка, а другим – j-го стовпця й одержання першим гравцем  (за рахунок другого) виграшу а_ij.

Головним у дослідженні ігор є поняття оптимальних стратегій гравців. У це поняття інтуїтивно вкладають такий зміст: стратегія гравця є оптимальною, якщо застосування цієї стратегії забезпечує йому найбіль­ший гарантований виграш за будь-яких стратегій іншого гравця. Враховуючи це, перший гравець досліджує матрицю виграшів А у такий спо­сіб: для кожного значення i ( ) визначають мінімальне значення ви­грашу, залежно від стратегій другого гравця:

                                                    ( ),

тобто мінімальний виграш для першого гравця за умови, що він візьме свою i-ту чисту стратегію, далі із цих мінімальних виграшів відшукують таку стратегію i = i_про, за якої цей мінімальний виграш буде максимальним, тобто знаходять

                                             .                                          

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

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

                                              .                                          

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

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

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

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

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

Змішаною стратегією гравця називають повний набір імовірностей застосування його чистих стратегій.

Таким чином, якщо перший гравець має m чистих стратегій 1, 2, ..., m, то його змішана стратегія x – це набір чисел x = (x₁, ..., x_m), які задо­вольняють відношенню

                                         

Аналогічно для другого гравця, який має n чистих стратегій, змішана стратегія y – це набір чисел:

                         

Середній виграш першого гравця у матричній грі з матрицею А виражають у вигляді математичного очікування його виграшів:

                                    

Перший гравець має на меті за рахунок зміни своїх змішаних стратегій х максимально збільшити свій середній виграш Е(А, х, y), а другий – за рахунок своїх змішаних стратегій зробити Е(А, х, y) мінімальним, тобто для розв’язання гри необхідно знайти такі х і y, за яких досягають верхньої ціни гри:

                                             

Аналогічною має бути ситуація і для другого гравця, тобто нижня ціна гри є такою:

                                          

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

              

Величину Е(А, х^о,у^о) називають ціною гри і позначають через v.

Оптимальні змішані стратегії та ціну гри називають розв’язком матричної гри

Теорема (про мінімакс).Для матричної гри з будь-якою матрицею А величини  і  існують і є рівними.

Вaжливою частиною більшості ігрових програм є процедура аналізу «дерева логічних можливостей».

Існує два типи дерев: дерева гри і дерева цілей. Гілки в дереві гри задають можливі ходи, ходи у відповідь і т. д. Дерево цілі показує, що деякої початкової цілі можна досягти, коли буде досягнуто певних підці­лей; у свою чергу аналогічно перевіряють досягнення підцілей. Оскільки де­рева мають тенденцію сильно розростатись, виникає потреба ефективного виділення істотних частин дерева. Дерево гри може бути експліцитним та імпліцитним. Експліцитне дерево гри задають у явному вигляді, імплі­цитне ж дерево задають виділенням початкової позиції і правил формування дерева.

Корінь цього дерева збігається з початковою позицією. Кожен вузол цього дерева характеризується номером гравця, що має робити хід. Дуги відповідають ходам, тобто, якщо в позиції 1 можливий хід, який переводить позицію 1 в позицію 2, то з позиції 1 до позиції 2 йде орієнтована дуга, яка відповідає цьому ходу. Право вибору ходу в позиції 2 належить, звичайно, уже іншому гравцеві. Кожен вузол дерева корисно характеризувати також його рівнем, тобто відстанню від кореня. Якщо на k-му рівні право вибору ходу належить одному з гравців, то на (k + 1)-му рівнівоно переходить до його суперника.

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

Для будь-якої гри, що завершується за скінченну кількість ходів, є теоретично можливим побудувати повне дерево гри, що охоплює всі можливі позиції. Почнемо аналіз дерева з завершальних позицій (листків дерева). Розглянемо довільні завершальні позиції, які мають одного бать­ка. Нехай для визначеності це α-вершини. Кожна завершальна позиція має оцінку, що збігається з функцією виграшу та є результатом гри. Ясно, що гравець В, якому належить право вибору ходу у батьків­ській вершині, вибере хід, що мінімізує цю оцінку (мінімізує його програш). Ця мінімаль­на оцінка передається даній вершині знизу.

Нехай всі наступники довільної β-вершини уже проаналізовані та кож­ному передано знизу певну оцінку. Загальне правило можна сформулювати у такий спосіб: з β-вершини має бути зроблений хід, що веде до позиції-наступника з найменшою оцінкою.

За допомогою аналогічних міркувань можна встановити правило, згід­­но з яким повинен вибирати ходи гравець А: з α-вершини має бути зроблений хід, що веде до позиції-наступника з найбільшою оцінкою.

Такий аналіз можна зробити для будь-якої позиції, включаючи почат­кову. Ця процедура носить назву мінімаксної процедури.

8. Метод резолюцій як основа логічного виведення.

Метод резолюцій – логічне числення у мові логіки предикатів першого порядку, що використовує єдине правило виведення (т.зв. правило резолюції). Для мови численні висловлювань це правило формулюється так: із формул  та , де  - елементарна формула, виводиться формула , а з  – виводиться "порожня" формула. Цього єдиного правила достатньо для встановлення того, чи є тотожно хибною довільна задана формула числення висловлювань, що подана в кон’юнктивній нормальній формі (КНФ). А саме, кон’юнкція скінченої множини М формул числення висловлювань, кожна з яких є диз’юнкцією елементарних формул і/чи їх заперечень, тотожно хибна тоді і тільки тоді, коли за допомогою правила резолюції із М виводиться порожня формула. Для логіки предикатів першого порядку правило резолюції формулюється більш складно - з використанням процедури уніфікації. Метод резолюцій вперше запропонував Дж.Робінсон в 1964. Його застосовують в мовах логічного програмування, при пошуку доведень теорем на ЕОМ, в доведеннях правильності програм, в системах планування поведінки роботів, в "питально-відповідальних" системах та ін. системах штучного інтелекту. Існують різні модифікації методу резолюцій, а також його узагальнень.

9. Мова функціонального програмування ЛІСП.

За однiєю з класифiкацiй мови програмування (МП) дiляться на процедурнi, якi також називаються операторними або iмперативними та декларативнi мови. До класу декларативних мов вiдносяться функцiональнi або апплiкативнi - Лiсп,.

Функцiональна програма складається з сукупностi визначених функцiй. Функцiї, в свою чергу, можуть викликати iншi функцiї. Обчислення починається з виклику деякої функцiї. Чисте функцiональне програмування не має присвоєнь та засобiв передачi керування. Повторнi обчислення здiйснюються за допомогою рекурсiї, яка є основним засобом функцiонального програмування.

Робота з Лiспом нагадує роботу з карманним калькулятором: користувач вводить вираз (вiн обов'язково повинен закiнчуватися символом та мати збалансовану кiлькiсть дужок), який читає машина, потiм обчислює (iнтерпретує), та видає результат. Цей процес введення-читання-обчислення-видачi результату буде вiдбуватися в циклi доти, доки користувач не введе команду (SYSTEM), яка завершує роботу з muLisp i передає керування операцiйнiй системi.

Приклад програми:

Напишемо функцію MEMBER, яка має два аргументи: nam - символ та lst - список і яка повинна перевірити чи належить символ списку.

(DEFUN MEMBER (nam lst)

((NULL lst) NIL)

((EQL nam (CAR lst)) T)

(MEMBER nam (CDR lst)) )

10. Мова логічного програмування ПРОЛОГ.

Числення предикатiв - математична основа мови.

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

Логiку предикатiв, в деякiй мiрi, можна вважати спецiальним математичним апаратом формалiзацiї людського мислення. Звiдки, мови програмування логiчного типу є найбiльш зручними, для роботи з базами знань.

Факти та правила.

При побудовi речень Прологу використовується той же пiдхiд що й в предикатних логiках. Спочатку вiдкидаємо всi несуттєвi слова. Потiм трансформуємо речення, виставляючи на перше мiсце вiдношення.

Факти

В Пролозi зв'язок мiж об'єктами називається фактом. Факти можуть виражати як властивостi, так i вiдношення.

Запити

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

Узагальнення

1. Програма на Пролозi будується iз двох типiв фраз (речень): фактiв i правил. Факти - це вiдношення, або ж властивостi, про якi ви, програмiст, знаєте, що вони iстиннi. Правила - це залежнi вiдношення; вони дозволяють Прологу робити виведення, порiвнюючи одну частину iнформацiї з iншою.

2. Правила Прологу складаються з трьох частин: голови, символу, тiла.

Голова - це факт, який буде вiрним, якщо деяка кiлькiсть умов виконається. Голову ще iнодi називають заключенням, або ж вiдношенням залежностi. Символ - вiддiляє голову правила вiд тiла; може бути текстовим типу or або ж if. Тiло - це множина умов (або список файлiв), котрi повиннi бути iстинними, для того щоб Пролог мiг довести, що голова правила вiрна.

Як змiннi отримують свої значення

В Пролозi не має операцiї присвоєння. Змiннi Прологу отримують свої значення, порiвнюючи їх з константами у фактах i правилах.

Поки змiнна не отримає свого значення, вона називається вiльною, а коли отримує значення - зв'язаною. Але вона залишається зв'язаною тiльки на час, який необхiдний для отримання одного розв'зку на запит, потiм Пролог звiльнює її, повертає i шукає альтернативнi розв' язки.