Úvod do umělé inteligence, řešení problémů
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.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 / 20
Co je “umělá inteligence”
Co je “umělá inteligence”
?
→ sli.do/uui
Úvod do umělé inteligence 1/12 2 / 20
Co je “umělá inteligence”
Co je “umělá inteligence”
Communication on AI for Europe, COM 2018/237 final
High Level Expert Group, A definition of AI, 2019
EU Artificial Intelligence Act, A definition of AI, COM/2021/206 final
‘Artificial intelligence system’ (AI system) means software that is developed with one or more of
the techniques and approaches listed in Annex I and can, for a given set of human-defined
objectives, generate outputs such as content, predictions, recommendations, or decisions
influencing the environments they interact with.
Annex I: 1. Machine learning approaches, including supervised, unsupervised and
reinforcement learning, using a wide variety of methods including deep learning;
2. Logic- and knowledge-based approaches, including knowledge representation,
inductive (logic) programming, knowledge bases, inference and deductive
engines, (symbolic) reasoning and expert systems;
3. Statistical approaches, Bayesian estimation, search and optimization methods.
Úvod do umělé inteligence 1/12 3 / 20
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)
1991–2019 – 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
Úvod do umělé inteligence 1/12 4 / 20
Co je “umělá inteligence”
Turingův test 2023
▶ ChatGPT/Bard nebyly testovány v nastavení podobném Loebnerově
ceně
▶ předpokládá se ale, že by mohly být úspěšné
▶ květen 2023 – AI21 Labs z Tel Avivu uspořádala masívní on-line
experiment Human or Not? s 1.5 mil. účastníků
40 % chatbotů lidi zmátlo
▶ hledá se nový “Turingův test” (ConceptARC, Turing test in Creative
Arts, artificial capable intelligence, ...)
Úvod do umělé inteligence 1/12 6 / 20
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 7 / 20
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 × 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 8 / 20
Co je “umělá inteligence” Čím se budeme zabývat?
Čí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 9 / 20
Co je “umělá inteligence” Čím se budeme zabývat?
Náplň předmětu
1 úvod do UI, řešení problémů
2 prohledávání stavového prostoru
3 dekompozice problému, problémy s omezujícími podmínkami
4 hry a základní herní strategie
5 logický agent. výroková logika
6 důkazové metody a systémy, predikátová logika prvního řádu
7 rezoluční metoda, úvod do logického programování
průběžná písemka z 1–6
8 reprezentace a vyvozování znalostí
9 zpracování přirozeného jazyka
10 učení, rozhodovací stromy, neuronové sítě
11 hluboké učení
12 generativní modely
Úvod do umělé inteligence 1/12 10 / 20
Organizace předmětu PB016
Organizace předmětu PB016
Hodnocení předmětu:
▶ dotazníky na cvičení (12 × 2 = max 24 bodů)
nutná podmínka k závěrečné zkoušce ≥ 10 bodů
▶ průběžná písemka (max 20 bodů)
• v 1/2 semestru – v týdnu po 7. přednášce, pro všechny jediný termín
▶ závěrečná písemka (max 60 bodů)
• dva řádné a jeden opravný termín
▶ hodnocení – součet bodů (max 104 bodů)
▶ známka A za > 95 bodů známka E za > 63 bodů
▶ rozdíly zk, k, z – různé limity
▶ někteří mohou získat extra body ve cvičení (max 1/cvičení)
• oprava chyby v materiálech
• nadprůměrné elegantní řešení
Úvod do umělé inteligence 1/12 11 / 20
Organizace předmětu PB016 Základní informace
Základní informace
▶ web stránka předmětu – 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 <hales@fi.muni.cz>, Luboš
Popelínský <popel@fi.muni.cz> (Subject: PB016 . . . )
▶ literatura:
• Russell, S. a Norvig, P.: Artificial Intelligence: A Modern Approach, 4th ed.,
Prentice Hall, 2020. (prezenčně v knihovně)
• slajdy a cvičení na webu předmětu
Úvod do umělé inteligence 1/12 12 / 20
Organizace předmětu PB016 Cvičení
Cvičení
▶ materiály viz interaktivní osnova cvičení a sdílené disky seminárních
skupin (nasdílí cvičící)
▶ formát cvičení je prezenční dle rozvrhu, pracuje se u počítače
▶ na začátku cvičení odpovědník na znalost tématu přednášky a
vyznačených definic ve sbírce příkladů
▶ 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 13 / 20
Řešení problémů Problém osmi dam
Problém osmi dam
úkol: Rozestavte po šachovnici 8 dam tak, aby se žádné dvě vzájemně
neohrožovaly.
celkem pro 8 dam existuje 92 různých řešení
Úvod do umělé inteligence 1/12 14 / 20
Řešení problémů Problém osmi dam I
Problém osmi dam I
datová struktura – osmiprvková množina
{(x1, y1), (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(n ← 8, queens ← {})
if length(queens) = n then
print queens # řešení
else
for qx ← 1 to n do
for qy ← 1 to n do
if NoAttack(qx , qy , queens) then
N-Queens(n, queens + {(qx , qy )})
function NoAttack(qx , qy , queens)
for q ∈ queens do
if qx = q[1] or qy = q[2] or abs(q[1]-qx ) = abs(q[2]-qy ) 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)}
...
Úvod do umělé inteligence 1/12 15 / 20
Řešení problémů Problém osmi dam II
Problém osmi dam II
počet možností u řešení I = 648 = 281 474 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
{(1, 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(n ← 8, queensy ← [])
if length(queensy ) = n then
print queensy # řešení
else
for qy ← 1 to n do
if NoAttack(qy , queensy ) then
N-Queens(n, queensy + [qy ])
function NoAttack(qy , queensy )
qx = length(queensy ) + 1
for i ← 1 to length(queensy ) do
if qy = queensy [i] or abs(i-qx ) = abs(queensy [i]-qy ) then
return False
return True
Úvod do umělé inteligence 1/12 16 / 20
Řešení problémů Problém osmi dam III
Problém osmi dam III
k souřadnicím x a y −→ přidáme i souřadnice diagonály u a v
u = x − y
v = x + y
Dx = [1..8]
Dy = [1..8]
−→ Du = [−7..7]
Dv = [2..16]
Úvod do umělé inteligence 1/12 17 / 20
Řešení problémů Problém osmi dam III
Problém osmi dam III
po každém umístění dámy aktualizujeme seznamy volných pozic
počet možností u řešení III = 2 057
function N-Queens(n ← 8, queensy ← [], dy ← [], du ← {}, dv ← {})
if length(queensy ) = 0 and length(dy ) = 0 then
return N-Queens(n, [], [ 1.. n], {-(n-1) .. (n-1)}, {2.. (2∗n)})
if length(queensy ) = n then
print queensy # řešení
else
for qy ∈ dy do
qx ← length(queensy ) + 1
qu ← qx − qy
qv ← qx + qy
if qu ∈ du and qv ∈ dv then
N-Queens(n, queensy + [qy ], dy .without(qy ), du − {qu}, dv − {qv })
dy = [1..8], du = {−7..7}, dv = {2..16}
Problém n dam pro n = 100:
řešení I . . . 10400 řešení II . . . 10158 řešení III . . . 1052
Úvod do umělé inteligence 1/12 18 / 20
Řešení problémů Další příklad – posunovačka
Další příklad – posunovačka
počáteční stav (např.)
−→ . . . −→
cílový stav
▶ hra na čtvercové šachovnici m × m s n = m2 − 1 očíslovanými kameny
▶ příklad pro šachovnici 3 × 3, posunování osmi kamenů (8-posunovačka)
▶ stavy – pozice všech kamenů
▶ akce – “pohyb” prázdného místa
☞ Optimální řešení obecné n-posunovačky je NP-úplné
Počet stavů u 8-posunovačky . . . 9!/2 =181 440
u 15-posunovačky . . . 1013
u 24-posunovačky . . . 1025
Úvod do umělé inteligence 1/12 19 / 20
Řešení problémů Reálné problémy řešitelné prohledáváním
Reálné problémy řešitelné prohledáváním
▶ hledání cesty z města A do města B
▶ hledání itineráře, problém obchodního cestujícího
▶ návrh VLSI čipu
▶ navigace auta, robota, . . .
▶ postup práce automatické výrobní linky
▶ návrh proteinů – 3D-sekvence aminokyselin
▶ Internetové vyhledávání informací
Úvod do umělé inteligence 1/12 20 / 20