Львівський національний університет імені Івана Франка

Факультет прикладної математики та інформатики

Кафедра програмування

 

Дисципліна          Дисципліна спеціалізації

 

Назва курсу   Вступ до штучного інтелекту (Introduction to AI)

 

Викладач --- Ярослав Андрійович КАРДАШ, ас. кафедри програмування

Istructor --- Yaroslav KARDASH, chair of programming

 

Спеціальність       Прикладна математика та інформатика

 

Курс           2                           Семестр      4

 

Кількість годин і звітність

 

 

4семестр

Лекції

17

Лабораторні заняття

34

залік

 

Breaf course annotation

 

This course --- Introduction to AI is aimed to practical mastering of the several notions of AI and devoted to gaining practical skills on the basis of game programming.

For this reason we emphasize goals of course as following:

·       Familiarizing with agent technology of intelligent systems building;

·       Learning knowledge representations forms;

·       Mastering of uninformed methods of search in state space;

·       Examination of heuristics methods of search;

·       Programming a set of games using discussed algorithms and appropriate for games heuristics.

 

Коротка аннотація курсу

 

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

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

·        Опанування агентною технологією побудови інтелектуальних програм;

·        Вивчення можливих форм представлення знань;

·        Розгляд різноманітних простих алгоритмів пошуку в просторі станів;

·        Вивчення еврестичних методів пошуку;

·        Запрограмуванням ряду ігор з використанням розглянутих алгоритмів пошуку та відповідних для ігор евристик.

 

Література:

1.     Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach. Upper Saddle River: “Prentice Hall”, 1995. – 932 p.

2.     Джордж Ф. Люгер. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е изд. /Пер. с англ. М.; «Вильямс», 2003. – 864 с.

3.     В. Н. Бондарев, Ф. Г. Аде. Искусственный интеллект, учебное пособие для высших учебных заведений. Севастополь: Изд-во СевНТУ, 2002. – 615 с.

4.     М. М. Глибовець, О. В. Олецький. Штучний інтелект, підручник для студентів вищих навчальних закладів. К.: Видавничий дім “КМ Академія”, 2002. – 365 с.

 

 

Вимоги до здачі заліку:

·        знання теоретичного матеріалу (20% від загального рішення);

·        реалізація завдань протягом семестру (20% від загального рішення);

·        реалізація трьох вибраних ігор (30% від загального рішення);

Перші троє осіб, що найшвидше здали ігри не будуть здавати теорію!

·        наявність доброго конспекту (20% від загального рішення);

·        роздрук змісту 2х журналів за рік (10% від загального рішення):

v    Communications of ACM, 1984-2003
portal.acm.org  -> ACM Digital Library -> Magazines -> Communications of ACM -> archive: 1984 – 2003 рр. http://portal.acm.org/browse_dl.cfm?linked=1&part=magazine&idx=J79&coll=portal&dl=ACM&CFID=1665957&CFTOKEN=93220778

v    ACM Intelligence, 1999-2001
portal.acm.org -> ACM Digital Library -> Magazines -> intelligence -> archive: 1999 – 2001 рр.
http://portal.acm.org/toc.cfm?id=J372&idx=J372&type=periodical&coll=portal&dl=ACM&part=magazine&WantType=Magazines&title=intelligence&CFID=16614437&CFTOKEN=76013350 ;

v    IEEE Computer, 1988-2003
http://www.computer.org/computer/archives.htm

v    IEEE Intelligent Systems and Their Applications, 1988-2003
http://www.computer.org/intelligent/archives.htm

 

Зміст одного числа журналу (наприклад, четвертого числа за 1984 р. Communications of ACM, (4)1984) повинен займати не більше одного листка формату А4, тобто зміст одного числа журналу повинен вміщатися на 2-х сторінках. Розмір шрифта для друку змісту журналу — 12 пунктів. Кожен студент повинен роздрукува­ти зміст 2-х журналів за один рік, тобто повинно бути 12 листків, якщо журнал виходить раз у місяць, і 6 листків, якщо журнал виходить раз на два місяці, а в сумі 24 або 12 листків, в залежності від типу журналів.

 

Список студентів, які повинні роздрукувати зміст відповідних журналів за рік:

 

1.      Артеменко Наталя

Communications of ACM, 1984

IEEE Computer, 1996

2.      Білонога Михайло

Communications of ACM, 1985

IEEE Computer, 1997

3.      Біляк Роман

Communications of ACM, 1986

IEEE Computer, 1998

4.      Брич Геннадій

Communications of ACM, 1987

IEEE Computer, 1999

5.      Василів Олег

Communications of ACM, 1988

IEEE Computer, 2000

6.      Держило Іван

Communications of ACM, 1989

IEEE Computer, 2001

7.      Ковбасюк Олександра

Communications of ACM, 1990

IEEE Computer, 2002

8.      Кремінь Віталій

Communications of ACM, 1991

IEEE Computer, 2003

9.      Куп’як Степан

Communications of ACM, 1992

IEEE Intelligent Systems, 1988

10.  Куцик Володимир

Communications of ACM, 1993

IEEE Intelligent Systems, 1989

11.  Куч Ігор

Communications of ACM, 1994

IEEE Intelligent Systems, 1990

12.  Мазуркевич Микола

Communications of ACM, 1995

IEEE Intelligent Systems, 1991

13.  Микитюк Андрій

Communications of ACM, 1996

IEEE Intelligent Systems, 1992

14.  Мобіс Вікторія

Communications of ACM, 1997

IEEE Intelligent Systems, 1993

15.  Остасюк Юрко

Communications of ACM, 1998

IEEE Intelligent Systems, 1994

16.  Пігура Тарас

Communications of ACM, 1999

IEEE Intelligent Systems, 1995

17.  Процюк Юрій

Communications of ACM, 2000

IEEE Intelligent Systems, 1996

18.  Пуцята Юрій

Communications of ACM, 2001

IEEE Intelligent Systems, 1997

19.  Синюта Юрій

Communications of ACM, 2002

IEEE Intelligent Systems, 1998

20.  Соломенчук Павло (с)

Communications of ACM, 2003

IEEE Intelligent Systems, 1999

21.  Соломенчук Петро

IEEE Computer, 1988

IEEE Intelligent Systems, 2000

22.  Сулій Олег

IEEE Computer, 1989

IEEE Intelligent Systems, 2001

23.  Тупичак Ігор

IEEE Computer, 1990

IEEE Intelligent Systems, 2002

24.  Чулик Мар’ян

IEEE Computer, 1991

IEEE Intelligent Systems, 2003

25.  Чума Олександр

IEEE Computer, 1992

ACM Intelligence, 1999

26.  Широчук Василь

IEEE Computer, 1993

ACM Intelligence, 2000

27.  Шлапак Роман

IEEE Computer, 1994

ACM Intelligence, 2001

28.  Яремчук Назарій

IEEE Computer, 1995

Communications of ACM, 1983

 

Зміст курсу

Тема 1. Вступ. Структура курсу, вимоги до здачі заліку. Визначення штучного інтелекту 2 год.

 

ШІ — наука про інтелектуальні програми.

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

Сфери застосування штучного інтелекту:

-         ігри;

-         експертні системи;

-         розуміння людської мови;

-         планування та робототехніка;

-         машинне навчання;

-         комп’ютерне бачення (розпізнавання образів);

-         планування, пошук та задачі роботики;

-         автоматичні міркування та доведення теорем;

-         моделювання роботи людського інтелекту;

-         середовища та мови ШІ;

-         м’які обчислення  та інтелектуальні системи;

-         моделювання знань.

Тема 2. Моделі представлення знань, 2 год.

Вступ. Найбільш вживані класи представлення знань.

Продукційна система представлення знань. Умовна частина продукції (антецедент, засновок — англ. термін premise/anticedent). Дієва частина продукції (консеквент, виснновок — result/con­clu­sion/consequence). Декларативні знання. Процедурні знання або мета-знання/правила. Пере­ваги та недоліки застосування правил.

Семантичні мережі. Означення семантичної мережі. Типи відношень на семантичній мережі. (“a kind of”/”is” —  атрибутивні, “has a part” — “частина-ціле”, “functional”, клас — елемент кла­су, властивість — значення, приклад елемента класу, кількісні, просторові, часові, логічні). Властивість наслідування семантичних мереж.

Фрейми. Означення фрейма. Слоти, фасети (фасети-значення, фасети-замовчувані значення, фа­сети-діапазони). Демони у фреймах, тип демонів (при додаванні, при потребі, при усунен­нні).. Ієрархії слотів, наслідування властивостей фреймами в ієрархії слотів.

Тема 3. Інтелектуальні агенти, 4 год.

Визначення агента. Раціональний агент. Міра успішності виконання. Залежність раціонального агента від 1) міри успішності виконання, 2) послідовності сприйняття, 3) знання про навко­лиш­нє середовище, 4) дій, які може здійснити агент. Визначення ідеального раціонального агента. Ві­дображення між послідовностями сприйняття та діями. Ідеальне відображення. Автоно­м­ність. Агентна програма та архітектура. Взаємовідношення між агентом, архітектурою та прог­ра­мою. Софтботи. Приклади типів агентів та їх PAGE-опис. Скелет агентної програми. Агент, базований на табличному перегляді (агент, що приводиться в рух таблицею). Приклад таксі-ро­бо­та. Сприйняття, дії, цілі та середовище (PAGE) таксі-робота. Прості рефлексивні агенти. Пра­вило умова-акція. Агенти, які зберігають опис навколишнього світу. Внутрішній стан агента. Аге­н­ти, базовані на цілях. Пошук та планування в контексті базованого на цілях агента. Аген­ти, базовані на корисності. Зовнішнє середовище агентів. Доступність/недоступність, визна­че­ність/невизначеність, епізодичність/неепізодичність, статичність/динамічність, дискрет­ність/не­пе­рервність зовнішнього середовища. Програми симуляції середовищ (базовий симулятор; си­му­лятор, що зберігає опис міри виконання роботи агента).

Тема 4. Розв’язування задач через пошук, 4 год.

Агент для розв’язання задач. Постановка задачі: формулювання цілі, формулювання задачі, по­шук та розв’язок. Фаза виконання. Програма простого агента для розв’язання проблем. Ти­пи за­дач: задача з одним станом, задача з багатьма станами, задачі з обставинами, чергування пошу­ку та виконання. Добре визначені задачі та розв’язки: поняття задачі, початкового стану, опера­тори (функція наслідування), простір станів, шлях у просторі станів, цільовий тест, кошт шля­ху, розв’язок. Тип даних “Problem”. Простір множини станів для задачі з багатьма станами. Оці­нка міри роз­в’я­зу­ван­ня задачі: кошт пошуку та загальний кошт. Абстрагування від деталей за­­дачі: вибір станів та дій. Пошук розв’язків. Ге­не­­ра­ція нових станів. Роз­ширення ста­ну. Стра­те­гія пошуку. Дерево пошуку. Нефоримальний опис алгоритму за­га­ль­но­го пошуку. Структури да­них для дерев пошуку. Структура даних “no­de”. Передній край алго­ритму пошуку. Черга вер­шин. Формальна версія алгоритму пошуку. Стратегії пошуку: неінформовані або сліпі та інфор­мо­вані або евристичні. Критерії оцінювання стратегій пошука — повнота, складність за часом, склад­ність за простором, оптимальність. По­шук в ширину, алгоритм пошуку в ширину. Пошук з уніформним коштом. Пошук в глибину, ал­горитм пошуку в глибину. Пошук з обмеженою гли­биною. Пошук з ітеративним заглиблен­ням. Двонапрямлений пошук. Порівняння стратегій по­­шуку. Уникнення повторюваних станів.

Тема 5. Інформовані методи пошуку, 2 год.

Пошук спочатку найкращого. Функція оцінки. Алгоритм  пошуку спочатку найкращого. Міні­мі­зація оціненого кошту для досягнення цілі: жадібний пошук. Поняття евристичної функції. Ев­ристична функція “віддалі по прямій до цілі”. Мінімізація загального кошту шляху: A*-по­шук. Властивості A*-пошуку: оптимальність, повнота та складність. A*-пошук з ітеративним за­глибленням

Тема 6. Ігри, 2 год.

Мінімаксний алгоритм для двоособових ігор. Алгоритм альфа-бета відтинання. Прикла­ди за­дач. Задача хрестики-нолики. Фор­му­лювання задачі. Гра “вісім фішок”: формулю­ва­ння задачі. За­дача про вісьмох ферзів: фор­му­лювання за­да­чі. Задача криптоарифметики: фор­мулювання за­да­чі. За­дача прибирання по­ро­хо­тя­гом: фор­му­лювання задачі. Задача про міссіо­не­рів та кані­ба­лів: фо­р­мулювання задачі. Гра “п’ят­надцять фішок”: формулювання проблеми. За­дача про ко­мі­­во­я­же­ра: формулювання про­б­ле­ми. Задача ре­версі: формулювання проблеми.

Тема 7. Евристики для ігор, 2 год.

Придумування евристичних функцій. Можливі евристики для хрестиків-ноликів. Евристика для гри у вісім фішок. Розв’язання задач для восьми ферзів та криптоарифметики як задач задово­ле­ння обмежень. Розв’язання для задачі про місіонерів та канібалів. Розв’язання задачі для ко­мівояжера.