Відповіді по СІІ - Стор 2
21. Ігри. Мінімаксні методи. Альфа-бета алгоритм.
Підгроюрозуміють пошук за умов протидії. 2 супротивника, ходи робляться по черзі за умов повної визначеності. Вивчає теорію ігор. На відміну від простих завдань пошуку, рішення дуже важко. Наприклад, у шахах дерево пошуку
10 ^ 154 вузлів.Дерево гри- визначається можливими ходами супротивників. Т.к. ходи противників робляться по черзі, у дереві «шари» ходів різних противників перемежовуються.
1) функція визначення наступника– повертає список пар «допустимих хід, стан»;
2) функція корисності(результат) для будь-якого можливого термінального стану (закінчення гри).
Мінімаксне (мм) значеннядля вузла дерева – наш найвищий результат гри, який можна досягти з даного вузла. Ми робимо найкращі ходи, тобто. вибираємо ходи з найбільшим мм-значенням. Противник робить найкращі ходи, тобто. вибирає ходи з найменшим мм значенням.Мінімаксний алгоритм- обчислює мм-значення для поточного стану.
Альфа-бета відсіканнядозволяє не розглядати ті вершини, для яких заздалегідь відомо, що вони не оптимальні. Значення 7 у галузі «7» більше, тому противник піде по галузі 5 (йому потрібен мінімум). Тому гілка «7» можна виключити із розгляду. Аналогічно, значення 3 менше, ніж 5, а нам потрібний максимум. Тому гілка "3" можна виключити.
22. Генетичні алгоритми. Основні принципи. Застосування.
Це евристичний спосіб вирішення завдання, що нагадує процеси еволюції у природі. Представляє собою послідовний підбір і комбінування параметрів, що шукаються. Дозволяє знайти неточне задовільне рішення для завдання. Стадії генетичного алгоритму:
0)Визначення початкової популяції.Населення- набір способів вирішення задачі (особін).
1) Визначенняфункції корисності для кожної особини.
3) Мутація та/або схрещування (кросовер).
4) Повернення до 1) або закінчення за деякою умовою.
Селекція.Вибір особин, що беруть участь у кроці 3. Проводиться за результатами ф. корисності. Нехай нам потрібне N особин. Підходи вибору:
1) пропорційний (ставлення ціле (ф.п./ф.п.средн) для особини – скільки разів бере участь, якщо 0.8 Швидкість 0.25 то Винищувач
На графіку «Вага-Швидкість» ці типи можна відокремити прямою лінією. Завдання мережі – визначити, який бік від лінії перебуває зразок. На вхід мережі подаються швидкість та вага. Наступний шар визначає лінійну залежність цих параметрів.
У деяких випадках не можна відокремити зразки одного класу від зразків іншого класу прямою лінією. У цьому випадку проблема називаєтьсянелінійною. Вона може бути вирішена лише багатошаровими мережами.
26 *. Розв'язання задач кластеризації за допомогою нейронних мереж.
27. Асоціативні мережі.
Асоціативні мережі- нейронні мережі, які можуть за неповним зразком відтворити його вигляд. Це використовується, наприклад, у оптичному розпізнаванні символів.
Мережа Хопфілдає такою мережею. У ньому кожен елемент пов'язані з усіма іншими, але з пов'язані з собою. За один крок оновлюється лише один елемент мережі (це робиться у випадковому порядку).
1. Вхідний зразок визначає початковий стан елементів мережі.
2. Випадково вибирається елемент для оновлення.
3. Вибраний елемент отримує сигнали з інших.
4. Перехід до 2, поки не буде досягнуто сталого стану (тобто мережа рекурентна).
Функція активації –sgn, тобто значення на виході кожного нейрона – знак його стануsgn(NET). Матриця коефіцієнтів передачі зв'язків обчислюється яктрансп(X)*X, де X - вектор-зразок, який потрібно запам'ятати (правильний). На діагоналі матриці слід встановити нулі, т.к. сам із собою елемент не зв'язується.
28. Логічні програми. Основні конструкції.
Логічна програма вирішує завдання, у яких використовуються поняття математичної логіки. Використовуються декларативні (описові) мови програмування, до програм можна додавати новіпропозиції: факти, правила, питання. Основна конструкція -предикат- визначає властивість для одного або кількох об'єктів:
Це бувфакт- конкретний предикат над конкретнимиконстантами.Правиловизначає новий предикат на основі існуючих, використовуючизмінні:
дідусь (X, Y): - Батько (X, Z), батько (Z, Y).
Правила може бути визначенорекурсивно, тобто. через самих себе:
предок (X, Y): - Батько (X, Y).
предок (X, Y): - Батько (X, Z), предок (Z, Y)
Кома розуміється як кон'юнкція «І», крапка з комою – диз'юнкція «АБО». Після завданняпитання(під час обчислення) змінніконкретизуються(з допомогою операції зіставлення):
29. Декларативний та процедурний зміст Пролог-програми.
Декларативний сенсвизначає, чи є ціль досяжною і, якщо так, то при яких значеннях змінних.Процедурний зміствизначає, як виконуватимуться пропозиції на Пролозі.
Наприклад, якщо записано:
Декларативний зміст: P істинно, якщо істинно Q або S і T.
Процедурний зміст: для обчислення P потрібно обчислити Q, а якщо значення невизначено, обчислити S потім ще T.
Декларативний підхід є кращим з точки зору програмування. Процедурний – з погляду ефективності програм.
30. Списки. Основні операції над списками.
Список – це структура даних, яка або порожня, або складається з голови (це перший елемент) та хвоста (що залишилися). Список є перерахуванням елементів у квадратних дужках через кому. Елемент списку також може бути списком. Операція [XY] у Пролозі поділяє список на ці дві частини:
Списки в Пролозі можуть використовуватися для представлення множини. Найбільш поширені операції: додавання, видалення, перевірка на приналежність елемента списку, конкатенація списків.
1. Приладдя.Перший параметр – елемент, який потрібно перевірити, другий – список. Результат – yes/no.
належить(X, [ZL]) :- належить(X, L).
2. Конкатенація (зчеплення).1, 2 параметр – списки, 3 параметр – результат – їхнє з'єднання.
конк([XL1], L2, [XL3]) :- конк(L1, L2, L3).
3. Додавання.1 параметр – елемент, 2 – список, 3 – результат – список із доданим елементом (на початок списку).
4. Видалення.1 параметр – елемент, 2 – список, 3 – результат – список без елемента X.
видалити(X, [YL], [YL1]) :- видалити(X, L, L1).