Dialogové systémy
Dialogové systémy
UdLdUdZC,   dLNUULy d
vyhledávací stromy
Luděk Bártek
Laboratoř vyhledávání a dialogu, Fakulta Informatiky Masarykovy Univerzity,
Brno
jaro 2022
Dotazovací systémy pro relační databáze
Dialogové systémy
Luděk Bártek
Databáze, atributy a vyhledávací stromy
Struktura databáze je určena relačním schématem (systémem atributů).
Systém se snaží na základě uživatelem zadaných hodnot atributů (ne nezbytně všech) nalézt požadovanou odpověď.
Pawlakův informační systém
Dialogové systémy
Luděk Bártek
Databáze, atributy a vyhledávací stromy
Autor — Zdzislaw I. Pawlak (1926 — 2006), polský matematik, člen polské Akademie věd.
Pawlakův informační systém - čtveřice S =      T, V, f)
■ U - množina objektů
■ T - množina atributů
■ V - množina hodnot atributů
■ f : Ux T -> V
Pawlakův informační systém formálně popisuje vztahy mezi objekty, jejich atributy a jejich hodnotami.
Souvislost s dialogovými systémy - hledání minimální množiny hodnot atributů, které nám určují jednotlivé objekty.
Pawlakův informační systém
Príklad
Dialogové systémy
Luděk Bártek
Dotazovací systémy pro relační databáze
Databáze, atributy a vyhledávací stromy
	Prveki	Prvel<2	Prveks	Prvek^
Atríbuti	1	1	0	0
Atríbut2	0	1	1	1
Atributy	1	1	1	0
□ i5P
Pawlakův informační systém
Vyhledávací strom
Dialogové systémy
Luděk Bártek
Databáze, atributy a vyhledávací stromy
Konstrukce vyhledávacího stromu pro Pawlakův IS:
Q Postupně bereme jednotlivé atributy obsažené v IS a
ptáme se na jeho přítomnost (hodnotu). B Listy jsou jednotlivé prvky uložené v IS.
Souvislost s dialogovým rozhraním (s iniciativou systému):
■ Na každé úrovni stromu se ptáme na hod not u/přítomnost odpovídajícího atributu.
■ Uživatelova odpověď určuje pokračování dialogu.
Lze použít i dialog se smíšenou iniciativou:
Uživatel zadá hodnoty libovolného počtu atributů. Systém odpověď zpracuje a doptá se na chybějící hodnoty.
Pawlakův informační systém
Příklady vyhledávacích stromů
Dialogové systémy
Luděk Bártek
Dotazovací systémy pro relační databáze
Databáze, atributy a vyhledávací stromy
atribut.
atribut
atribut
prvek2       prvekl  prvek3 prvek4
Obrázek: Vyhledávací strom pro Pawlakův IS 4
Obrázek: Jiný vyhledávací strom pro Pawlakův IS
Pawlakův informační systém
Zajímavé problémy
Dialogové systémy
Luděk Bártek
Databáze, atributy a vyhledávací stromy
Z daného systému atributů vybrat minimální systém jednoznačně rozlišující jednotlivé prvky.
	Prveki	Prvel<2	Prveks	Prvek^
atríbuti	1	1	1	0
atríbut2	1	1	0	1
atributy	1	0	1	1
atributy	1	1	0	0
atríbuts	1	0	1	0
■ Bylo dokázáno, že tento problém je NP-úplný.
Na základě atributů vybrat optimální vyhledávací strom
■ Kritérium - např. výška stromu - problém je opět NP-úplný.
Existují aproximativní algoritmy.
Dotazovací systémy
Příklady
Dialogové systémy
Luděk Bártek
Databáze, atributy a vyhledávací stromy
Všeobecný dotazovací systém Start
Dotazovací systém pro klinické lékaře Hermes
Neudržovaný dotazovací systém U10 z NLP Fl - aktuálně neprístupný
Chatboty na Bot Libre, s možností tvorby vlastního chatbota.