Підручник призначений для студентів вищих навчальних закладів, які навчаються за спеціальностями "Комп'ютерні науки" та "Прикладна математика". Метою підручника є ознайомлення студентів з основами теорії штучного інтелекту. Розглядаються основні методи роботи зі знаннями, зокрема з нечіткими та недостовірними; планування цілеспрямованих дій та прийняття рішень; ігрові задачі; розпізнавання образів та нейронні мережі. ЗМІСТ Від авторів З Вступ 5 ЧАСТИНА 1 НЕФОРМАЛЬНИЙ ВСТУП ДО ПРЕДМЕТА ШТУЧНОГО ІНТЕЛЕКТУ Розділ 1. Природний і штучний інтелект 1.1. Інтуїтивне розуміння поняття "інтелект" 7 1.2. Приклади інтелектуальних задач 9 1.3. Аналіз основних визначень поняття "інтелект" 11 1.4. Тест Тьюринга і фатнчний діалог 12 1.5. Метод комп'ютерної реалізації фалічного діалогу 13 Контрольні запитання 15 Теми для обговорення 15 Задачі і вправи 16 Розділ 2. Кібернетичні системи 2.1. Поняття кібернетичної системи 16 2.2. Класифікація кібернетичних систем 17 2.3. Керування кібернетичними системами 17 2.4. Контур керування та зворотний зв'язок 18 Контрольні запитання 20 Теми для обговорення 20 Розділ 3. Інтелект як високооргаиізована кібернетична система 3.1. Алгоритмічний і декларативний підходи до керування 21 3.2. Поповнення первинних інструкцій 22 3.3. Формалізація понять алгоритмічності та декларативності 22 3.4. Квазіалгоритми та джерела квазіалгоритмічності 23 3.5. Інтелектуальні системи із загальнокібернетнчних позицій 25 3.6. Типова схема функціонування інтелектуальної системи 27 3.7. Класифікація основних напрямів досліджень 28 3.8. Соціальні наслідки інтелектуалізації комп'ютерних технологій 29 Контрольні запитання 30 Теми для обговорення 31 ЧАСТИНА II МОДЕЛІ ПОДАННЯ ЗНАНЬ І МЕТОДИ ЛОГІЧНОГО ВИВЕДЕННЯ Розділ 4. Знання як інформаційна основа інтелектуальних систем 4.1. Знання і деякі підходи до їх подання 32 4.2. Вербально-дедуктивне визначення знань 34 4.3. Експертні системи 35 4.4. Дані та знання 36 4.5. Зв'язки між інформаційними одиницями 37 4.6. Проблема винятків 40 4.7. Властивості знань 41 4.8. Неоднорідність знапь. Області і рівні знань 42 4.9. База знань як об'єднання простіших одиниць 43 4.10. Бінарні предикати і тріада "об'єкт-атрибут-значення" ............ 44 4.11. Проблема неточних і неповних знань 45 Контрольні запитання 45 Теми для обговорення 46 Розділ 5Семантичні мережі 5.1. Визначення та класифікація семантичних мереж 46 5.2. Семантичні мережі u пам'яті людини 48 5.3. Трирівнева архітектура семантичних мереж 49 5.4. Асиміляція нових знань иа основі семантичних мереж 50 5.5. Різні способи задания семантичних мереж 51 5.6. Логічне виведення на семантичних мережах 55 5.7. Процедурні і розділені семантичні мережі 56 Контрольні запитання 57 Теми для обговорення 57 Розділ в. Фреймові моделі 6.1. Фрейми та слоти: базові поняття 58 6.2. Конкретизація, ієрархія та наслідування фреймів 58 6.3. Поповнення первинних описів на основі фреймових моделей 59 6.4. Мережі подібностей і відмінностей 61 6.5. Фрейми та об'ектно-орієнтоване програмування 63 6.6. Поняття про мову UML 65 Контрольні запитання 65 Теми для обговорення 66 Розділ 7. Логічні моделі та метод резолюцій 7.1. Логічні побудови та логічні моделі 66 7.2. Короткий вступ до числення предикатів 67 7.3. Фразова форма запису логічних формул 71 7.4. Аналіз і доведення теорем 74 7.5. Побудова теорії певної області знань 78 7.6. Від формальної логіки до логічного програмування 80 7.7. Мова Пролог і логічно програмування 86 7.8. Основні ідеї Прологу 87 7.9. Як працює Пролог 90 Контрольні запитання 91 Теми для обговорення 92 Задачі і вправи 92 Розділ 8. Продукційні моделі 8.1. Характеристика продукційннх моделеіі 93 8.2. Продукції та мережі виведення 95 8.3. Типова схема роботи експертної системи па базі продукції! . . . 96 8.4. Пряме та зворотне виведення 96 8.5. Типові дисципліни виконання продукції! 97 8.6. Основні стратегії вирішення конфліктів у продукційннх системах 98 Контрольні запитання 100 Тема для обговорення 100 ЧАСТИНА III ФОРМАЛІЗАЦІЯ НЕДОСТОВІРНИХ І НЕЧІТКИХ ЗНАНЬ Розділ 9. Модальні логіки 9.1. Алстнчні та епістсмічні логіки 101 9.2. Тризначна логіка Лукасевича 101 9.3. Логіка знання 102 9.4. Семантика можливих світів 103 9.5. Основи теорії можливостей 104 Контрольні запитання 104 Тема для обговорення 105 Розділ 10. Логічне виведення за недостовірних знань 10.1. Поняття про неточне логічне виведення 105 10.2. Деякі визначення з теорії ймовірностей 106 10.3. "Об'єктивна" та "суб'єктивна" невизначеність 108 10.4. Загальні принципи неточного виведення 110 10.5. Точкові та інтервальні міри неточності 111 10.6. Проблема комбінування свідоцтв 112 10.7. Приклади застосування мір достовірності 112 10.8. Деякі формалізації мір ризику за неточного логічного виведення 113 10.9. Деякі проблеми виведення 115 10.10. Схема EMYC1N 116 Контрольні запитання 117 Теми для обговорення 118 Задачі і вправи 118 Розділ 11. Логічне виведення за нечіткої інформації 11.1. Інтуїтивно поняття нечіткості 119 11.2. Функція належності як основна характеристика нечіткої множини 119 11.3. Основні операції над нечіткими множинами 121 11.4. Нечітке логічне виведення 122 11.5. Метод центру тяжіння композиції максимум-мінімум 123 Контрольні запитання 124 Теми для обговорення 125 Задачі і вправи 125 ЧАСТИНА IV МОДЕЛІ І МЕТОДИ ПРИЙНЯТТЯ РІШЕНЬ Розділ 12. Основні підходи до планування цілеспрямованих дій 12.1. Планування цілеспрямованих дій і прийняття рішень 126 12.2. Новини перебір як найочевидніший метод вирішення оптнмізацііпіої задачі 128 12.3. Евристичний пошук 128 12.4. Експоненційна складність евристичного пошуку 129 12.5. Пошук у глибину і пошук у ширину 130 12.6. Простір задач і простір станін 131 Контрольні запитання 132 Теми для обговорення 132 Розділ 13. Аналіз складності алгоритмів розв'язку інтелектуальних задач 13.1. Автоматний спосіб задания алгоритму 133 13.2. Клас функцій, обчислюваних за Тьюрингом 136 13.3. Моделі РАМ і РАСИ 137 13.4. Складність алгоритмів 139 13.5. Задачі класу Р і NP 143 Контрольні запитання 145 Розділ 14. Планування в просторі станів 14.1. Основні поняття теорії графів 146 14.2. Способи задания графів 148 14.3. Дерева 151 14.4. Способи зберігання дерев 152 14.5. Пошук у глибину і ширину 155 14.6. Остові дерева 155 14.7. Ейлерові шляхи 158 14.8. Знаходження нанкоротших шляхів у графі 159 14.9. Загальна схема алгоритму Харта, Нільсона і Рафасля 165 Контрольні запитання 169 Теми для обговорення 169 Задачі і вправи 169 Розділ 15. Планування в просторі задач 15.1. Базові поняття 170 15.2. Метод "поділяй і пануй" 172 Контрольні запитання 175 Задачі і вправи 175 Розділ 16. Жадібні алгоритми 16.1. Основні поняття 176 16.2. Градієнтний метод 177 16.3. Жадібні алгоритми для задачі цілочислового програмування 178 16.4. Матроіди 182 16.5. Алгоритми Пріма і Крускала 185 Контрольні запитання 189 Розділ 17. Динамічне програмування 17.1. Основні поняття 190 17.2. Принцип оптимальності Беллмана 191 17.3. Рекурентні рівняння в динамічному програмуванні 192 17.4. Числа Фібоначчі 192 17.5. Задача про критичний шлях 194 17.6. Задача пошуку найкоротшого шляху 195 Контрольні запитання 196 Тема для обговорення 196 Задачі і вправи 196 Розділ 18. Бектрскінг 18.1. Основні поняття 198 18.2. Базовий алгоритм 199 18.3. Рекурсивна схема 200 18.4. Типові задачі 200 18.5. Сума підмножин 205 18.6. Гамільтонові цикли 206 Контрольні запитання 207 Теми для обговорення 207 Задачі і вправи 208 Розділ 19. Виріпгувачі інтелектуальних задач 19.1. Базові поняття 208 19.2. Загальний вирішувач задач 209 19.3. Деякі інші методики 211 Контрольні запитання 212 Теми для обговорення 212 Розділ 20. Ігрові задачі 20.1. Ігрові задачі як задачі прийняття рішень 212 20.2. Основи теорії однокрокових ігор 213 20.3. Клас позиційних ігор, для яких існує оптимальна стратегія 214 20.4. Дерево гри та мінімаксна процедура 215 20.5. Обмеження глибини перебору 218 20.G. Альфа-бста-відтинання 221 20.7. Деякі графові моделі аналізу ігрових задач 220 20.8. Огляд сучасних шахових програм 228 20.9. Деякі підходи до самонавчання ігрових програм 229 Контрольні запитання 230 Теми для обговорення 231 Задачі і вправи 231 Розділ 21. Евристичні алгоритми 21.1. Обмежуючі правила та евристики як засіб скорочення перебору 233 21.2. Задача розфарбування графу 235 21.3. Точні та евристичні методи розфарбування 237 Контрольні запитання 243 ЧАСТИНА V БАЗОВІ ПАРАДИГМИ ПГГЕЛЕКТУАЛЬНОЇ ДІЯЛЬНОСТІ Розділ 22. Загальиоіїггелсктуальїіі метапроцедури 22.1. Базові поняття 244 22.2. Поняття про ситуаційне керування 245 22.3. Семіотичні моделі та мови опису ситуацій 245 22.4. Основні загальпоінтелектуальні метапроцедури 246 Контрольні запитання 249 Теми для обговорення 250 Розділ 23. Навчання і самонавчання 23.1. Базові визначення 250 23.2. Автомати я лінійною тактикою 251 23.3. Формування та засвоєння понять 253 23.4. Базові поняття теорії індуктивних висновків 254 23.5. Правила Мілля щодо формування гіпотез 255 23.6. Індуктивна перевірка гіпотез і парадокс Хемиеля 255 23.7. Поняття про генетичні алгоритми 256 Контрольні запитання 256 Теми для обговорення 257 Розділ 24. Розв'язок задач за допомогою моделювання 24.1. Основні визначення 257 24.2. Класифікація моделей 259 24.3. Математичне моделювання 260 24.4. Задача розміщення 265 24.5. Мережі Нетрі та їх використання 271 24.6. Властивості мереж Нетрі 276 24.7. Застосування мереж Петрі в машинній побудові зв'язних тестів 277 Контрольні запитання 280 ЧАСТИНА VI РОЗПІЗНАВАННЯ ОБРАЗІВ Розділ 25. Основні принципи розпізнавання 25.1. Основні постановки задач розпізнавання 281 25.2. Класи та їх властивості 282 25.3. Модельні описи класів. Розпізнавання як зіставлення 284 25.4. Постановка задачі і основні режими розпізнавання 285 25.5. Розпізнавання як прийняття рішені 287 25.6. Класифікація основних методів розпізнавання 288 25.7. Поняття про допустимі перетворення 289 Контрольні запитання 290 Теми для обговорення 290 Розділ 26. Розпізнавання в просторі ознак 26.1. Загальна характеристика дискримінантних методів розпізнавання 291 26.2. Типи ознак, міри відстаней 291 26.3. Вектори та матриці ознак 292 26.4. Гіпотеза компактності 292 26.5. Типова схема розпізнавання в просторі ознак 294 26.6. Роздільні функції. Лінійні роздільні функції 295 26.7. Метод найближчого сусіда 296 26.8. Байссівські методи розпізнавання 296 Контрольні запитання 298 Теми для обговорення 298 Задачі і вправи 298 Розділ 27. Синтаксичні методи розпізнавання 27.1. Загальна характеристика синтаксичних методів розпізнавання 299 27.2. Формальні граматики і мови 300 27.3. Класифікація граматик за Хомським 300 27.4. Приклад опису зображень на основі формальних граматик . . . 302 27.5. Основні методи граматичного розбору 302 27.6. Засоби опису складніших зображень 304 Контрольні запитання 305 Теми для обговорення 305 Задачі і вправи 305 Розділ 28. Основні методи попередньої обробки сигналів і зображень 28.1. Суть попередньої обробки сигналів і зображень 306 28.2. Отримання первинних ознак на основі дискретизації 306 28.3. Ланцюговий код Фрімена 308 28.4. Парамстризація неперервних функцій на основі лінійних ортогональних перетворень 309 28.5. Інтегральне перетворення Карунена-Лоева 310 Контрольні запитання 312 Теми для обговорення 313 Задачі і вправи 313 ЧАСТИНА VII НЕЙРОННІ МЕРЕЖІ Розділ 29. Загальна характеристика конекціопістського підходу до побудови систем штучного інтелекту 29.1. Конекціоністськніі підхід як спроба моделювання людського мозку 314 29.2. Основні сфери застосування З Ні Контрольні запитання 319 Теми для обговорення 319 Розділ ЗО. Модельні нейрони 30.1. Модельні нейрони як порогові елементи 319 30.2. Повнота системи модельних нейронів 320 30.3. Процедура Уїдроу-Хопфа 321 30.4. Сигмоїдальні активаційні функції 321 Контрольні запитаний 322 Розділ 31. Псрсептрони та сучасні нейронні мережі 31.1. Персептрон Розенблатта 322 31.2. Загальна характеристика сучасних неііронних мереж 323 31.3. Штучна ненронна мережа Хопфілда 325 31.4. Загальна схема зворотного розповсюдження помилок 326 31.5. Використання модифікованої мережі Хопфілда при розв'язку задачі розпізнавання літер 327 Контрольні запитання 333 ЧАСТИНА VIII РОЗУМІННЯ І СПІЛКУВАННЯ Розділ 32. Розуміння природної мови 32.1. Основні задачі, пов'язані з обробкою природної мови 334 32.2. Типова схема обробки природної мови 335 32.3. Рівні розуміння 335 32.4. Глибинні відмінки 336 32.5. Типова схема аналізу речень на основі глибинних відмінків 337 32.6. Розширені мережі переходів 338 Контрольні запитання 338 Теми для обговорення 338 Література 339 Предметний покажчик 352