Uvod do umělé inteligence, řešení problémů Aleš Horák E-mail: hales@fi.muni.cz http://nip.fi.muni.cz/uui/ Obsah: ► Co je "umělá inteligence" ► Organizace předmětu PB016 ► Řešení problémů Úvod do umělé inteligence 1/12 1/19 Co je "umělá inteligence" Co je "umělá inteligence" ? ■ > sli.do/uui Úvod do umělé inteligence 1/12 2/19 Co je "umělá inteligence" Co je "umělá inteligence" _-i- /~\ (— i High Level Expert Group, A definition of Al, 2019 Artificial intelligence (Al) systems are software (and possibly also hardware) systems designed by humans that, given a complex goal, act in the physical or digital dimension by perceiving their environment through data acquisition, interpreting the collected structured or unstructured data, reasoning on the knowledge, or processing the information, derived from this data and deciding the best action(s) to take to achieve the given goal. Al systems can either use symbolic rules or learn a numeric model, and they can also adapt their behaviour by analysing how the environment is affected by their previous actions. Úvod do umělé inteligence 1/12 3/19 Co je "umělá inteligence" Co je "umělá inteligence" ► systém, který se chová jako člověk Turingův test (1950) zahrnuje: ► zpracování přirozeného jazyka (NLP) ► reprezentaci znalostí (KRepresentation) ► vyvozování znalostí (KReasoning) ► strojové učení ► (počítačové vidění) ► (robotiku) od 1991 - Loebnerova cena (Loebner Prize) —± každý rok $4.000 za "nejlidštější" program, nabízí $100.000 a zlatá medaile za složení celého Turingova testu (od 2019 bez odměn) Úvod do umělé inteligence 1/12 4/19 Co je "umělá inteligence" ► systém, který myslí jako člověk ► snaha porozumět postupům lidského myšlení - kognitivní (poznávací) věda ► využívá poznatků neurologie, neurochirurgie,.. . např. Angela Friederici: Language Processing in the Human Brain Max Planck Institute of Cognitive Neuroscience, Leipzig měření "Event Related Potentials" (ERP) v mozku -jako potvrzení oddělení syntaxe a sémantiky při zpracování věty ► 2013-2023 Human Brain Project, Geneva, Švýcarsko Úvod do umělé inteligence 1/12 6/19 Co je "umělá inteligence" ► systém, který myslí rozumně od dob Aristotela (350 př.n.l.) ► náplň studia logiky ► problém - umět najít řešení teoreticky x prakticky (složitost a vyčíslitelnost) ► problém - neúplnost a nejistota vstupních dat ► systém, který se chová rozumně (inteligentně) inteligentní agent - systém, který ► jedná za nějakým účelem ► jedná samostatně ► jedná na základě vstupů ze svého prostředí ► pracuje delší dobu ► adaptuje se na změny Úvod do umělé inteligence 1/12 7/19 v Co je "umělá inteligence" Cím se budeme zabývat? v Cím se budeme zabývat? ► základní struktury a algoritmy běžně používané při technikách programovaní pro inteligentní agenty ► strategie řešení, prohledávání stavového prostoru, heuristiky, . .. ► s příklady ve cvičení v jazyce Python Úvod do umělé inteligence 1/12 8/19 v Co je "umělá inteligence" Cím se budeme zabývat? Náplň předmětu O úvod do UI, řešení problémů © prohledávání stavového prostoru © dekompozice problému, problémy s omezujícími podmínkám O hry a základní herní strategie B logický agent, výroková logika B pravdivost, dokazatelnost, důkazové metody průběžná písemka B logika prvního řádu a intenzionální logika □ rezoluční metoda, úvod do logického programování □ modálni logiky, vícehodnotové logiky ® reprezentace a vyvozování znalostí ® učení, rozhodovací stromy, neuronové sítě ® zpracování přirozeného jazyka Úvod do umělé inteligence 1/12 9/19 Organizace předmětu PB016 Organizace předmětu PB016 Hodnocení předmětu: ► dotazníky na cvičení (11 x 2 = max 22 bodů) nutná podmínka k závěrečné zkoušce > 8 bodů ► průběžná písemka (max 20 bodů) • v y2 semestru - v týdnu po 6. přednášce, pro všechny jediný termín ► závěrečná písemka (max 58 bodů) • dva řádné a jeden opravný termín ► hodnocení - součet bodů (max 100 bodů) ► známka A za > 92 bodů známka E za > 64 bodů ► rozdíly zk, k, z - různé limity ► někteří mohou získat extra body ve cvičení (max l/cvičení) • oprava chyby v materiálech • samostatná aktivita nad rámec zadání • nadprůměrné elegantní řešení Úvod do umělé inteligence 1/12 10 / 19 Organizace předmětu PB016 Základní informace Základní informace ► web stránka předmětu -http://nlp.fi.muni.cz/uui/ ► slajdy i cvičení - průběžně doplňovány v interaktivních osnovách ► kontakt na přednášející - Aleš Horák , Luboš Popelínský (Subject: PB016 ...) ► literatura: • Russell, S. a Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd ed., Prentice Hall, 2010. (prezenčně v knihovně) • slajdy a cvičení na webu předmětu Úvod do umělé inteligence 1/12 11 / 19 Organizace předmětu PB016 Cvičení Lviceni ► materiály viz interaktivní osnova cvičení ► probíhat budou formou online událostí na univerzitním Google Meet • každý obdrží emailem pozvánku k události od příslušného cvičícího jakmile potvrdíte účast, měla by událost být viditelná ve vašem Google kalendáři • pro připojení se ke cvičení stačí kliknout na Google Meet odkaz spojený s událostí ► platforma pro řešení úkolů je Google Colaboratory na sdíleném Google disku • Jupyter notebooky (Python + Markdown/LaTeX) ► cvičení jsou povinná (možné max 3 neomluvené absence) Úvod do umělé inteligence 1/12 12 / 19 v Řešení problémů Problém osmi dam Problém osmi dam úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné neohrožovaly. celkem pro 8 dam existuje 92 různých řešení 13 / 19 Úvod do umělé inteligence 1/12 Řešení problémů Problém osmi dam I Problém osmi dam I datová struktura - osmiprvková množina {(Xi,yi),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8)} solution ={(1,4), (2,2), (3,7), (4,3), (5,6), (6,8), (7,5), (8,1)} function N-Queens(a7 <— 8, queens <— {}) if length (queens) = n then print queens # řešení else for qx <— 1 to n do for <7y «— 1 to n do if NoAttack(<7x, qy, queens) then N-Queens(n, queens + {(qx, <7y)}) function NoAttack(<7x, qy, queens) for (7 G queens do if <7x = q[l] or <7y = q[2] or abs(q[l]-qx) = abs(<7[2]-<7y) then return False return True N-Queens(8) {(8,4), (7,2), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} {(7,2), (8,4), (6,7), (5,3), (4,6), (3,8), (2,5), (1,1)} v Řešení problémů Problém osmi dam II Problém osmi dam II počet možností u řešení I = 648 = 281474 976 710 656 při neopakování pozic 64 • 63 • 62 ... • 57 = 178 462 987 637 760 omezení stavového prostoru - každá dáma má svůj sloupec {(I,y1),(2,y2),(3,y3),(4,y4),(5,y5),(6,y6),(7,y7),(8,y8)} počet možností u řešení II = 88 = 16 777 216 function N-Queens(a7 «— 8, queensy «— []) if length (queensy) = n then print queensy # řešení else for <7y ^— 1 to n do if NoAttack(<7y, queensy) then N-Queens(/i, queensy + [<7y]) function NoATTACK(qy, queensy) qx = length (queensy) + 1 for / ^— 1 to length(queensy) do if <7y = queensy[i] or abs(/-qrx) = abs(queensy[i]-qy) then return False Uvod do umělé inteligence 1/12 15 / 19 v Řešení problémů Problém osmi dam III Problém osmi dam k souřadnicím x a y u = x - y v = x + y přidáme i souřadnice diagonály u a v Dx = [1..8] —> Du = [-7..7] Dy = [1..8] Du = [2..16] u > v