====== Kybernetika a umělá inteligence ====== * Stránky předmětu: http://informatika.felk.cvut.cz/moodle2/course/view.php?id=4 ** Nástřel řešení příkladů k testu (rozhodně ne 100% kvalitní): ** ====== 1 ===== 1.1. Kybernetika zkoumá [ ] složité systémy, ale nikoliv jejich vzájemné abstraktní analogie [ ] principy řízení, ale nikoliv principy regulace zpětnou vazbou [X] informaci a jeji přenos 1.2. Princip zpětné vazby lze pozorovat v systémech [X] technických [X] biologických [X] sociálních 1.3. Dynamikou systému rozumíme [ ] rychlost konvergence stavu k ustálené hodnotě; pro divergující stav není dynamika definována [ ] rychlost divergence stavu od počáteční hodnoty; pro konvergující stav není dynamika definována [X] vývoj stavu v čase 1.4. Diskrétní dynamický systém je charakterizován těmito vlastnostmi: [ ] stavová veličina je diskrétní, tj. nabývá vždy jedné ze spočetné množiny hodnot [ ] čas je diskrétní veličina, tj. nabývá vždy jedné hodnoty ze spočetné množiny hodnot [X] stav v daném okamžiku jednoznačně vyplývá ze stavu v předchozím okamžiku 1.5. Pro stavový vektor spojitého dynamického systému obecně platí: [ ] žádná složka vektoru nesmí být rovna časové derivaci jiné složky [ ] je-li systém deterministický, žádná složka vektoru nesmí být rovna derivaci jiné složky [ ] je-li systém stochastický, žádná složka vektoru nesmí být rovna derivaci jiné složky 1.6. V orientovaném lineárním dynamickém systému [X] vstupní veličiny nejsou ovlivňovány stavem [X] výstupní veličiny neovlivňují stav [ ] stav neovlivňuje výstupní veličiny 1.7. Asymptotickou stabilitou dynamického systému rozumíme [X] konvergenci stavu k ustálené hodnotě [ ] nepřítomnost kmitů v časovém průběhu stavu [ ] přítomnost kmitů v časovém průběhu stavu 1.8. Vlastní čísla matice stabilního dynamického lineárního systému vždy leží [X] v levé komplexní polorovině, jde-li o systém spojitý [X] uvnitř jednotkového kruhu se středem 0+0j komplexní roviny, jde-li o systém diskrétní [ ] v levém polokruhu jednotkového kruhu se středem 0+0j komplexní roviny 1.9. Stabilitu dynamického systému lze vždy analyticky dokázat, [X] je-li systém lineární [ ] je-li systém nelineární [ ] je-li systém diskrétní 1.10. Chaotické dynamické chování může nastat [X] pouze v nelineárním systému [ ] pouze v diskrétním systému [ ] pouze ve spojitém systému ====== 2 ====== 2.1. Množství Shannonovské informace v symbolu [ ] stoupá s rostoucí pravděpodobností tohoto symbolu [X] klesá s rostoucí pravděpodobností tohoto symbolu [ ] je nezávislé na pravděpodobnosti tohoto symbolu 2.2. Informační entropie zprávy je [X] součtem množství informace všech symbolů ve zprávě [ ] střední hodnotou informace ve zprávě, tj. množství informace připadající na jeden symbol [ ] funkcí pravděpodobnostního rozložení symbolů ve zprávě 2.3. Informační entropie náhodné veličiny [X] je měřítkem neurčitosti její hodnoty [ ] je definována pouze pro nezáporné veličiny [ ] je definována pouze pro veličiny nabývající hodnot z konečné množiny 2.4. Informační entropie systému [ ] je [ ] je [ ] je hodnot definována pouze pro stabilní dynamické systémy měřítkem neuspořádanosti systému nekonečná, pokud stavová veličina systému může nabývat více než dvou 2.5. Informační entropie H(S) diskrétní náhodné proměnné S s pravděpodobnostním rozložením P(s) [X] dosahuje maximální hodnoty, je-li P(s) rovnoměrné [ ] dosahuje minimální hodnoty, je-li P(s) rovnoměrné [ ] nezávisí na P(s) 2.6. Informační entropie H(S) diskrétní náhodné proměnné S s pravděpodobnostním rozložením P(s) [ ] dosahuje maximální hodnoty, pokud pro nějaké s platí P(s) = 1 [X] dosahuje minimální hodnoty, pokud pro nějaké s platí P(s) = 1 [ ] nezávisí na P(s) 2.7. Nechť diskrétní náhodná veličina S nabývá n možných hodnot. [X] Informační entropie H(S) není nikdy nižší než logaritmus n (při základu 2) [ ] Informační entropie H(S) není nikdy vyšší než logaritmus n (při základu 2) [X] Informační entropie H(S) je vždy nezáporná 2.8. Hodnota informační entropie makrostavu [ ] stoupá s počtem mikrostavů odpovídajících tomuto makrostavu [ ] klesá s počtem mikrostavů odpovídajících tomuto makrostavu [ ] je nezávislá na počtu mikrostavů odpovídajících tomuto makrostavu 2.9. Druhou termodynamickou větu lze správně interpretovat takto: [X] teplo nepřechází ze studenějšího tělesa na teplejší [X] entropie termodynamického systému se samovolně nemění [ ] entropii termodynamického systému lze snížit jen dodáním energie z vnějšku systému 2.10. Informační entropii lze spočítat výhradně u systémů [ ] termodynamických [ ] termodynamických a lingvistických [X] jejichž každý stav má svou známou pravděpodobnost ====== 3 ====== 3.1. Nechť X a Y jsou diskrétní náhodné veličiny. Potom nutně [X] H(X|Y) je nezáporná [X] H(X|Y) není větší než H(X) [ ] H(X|Y) není větší než H(Y) 3.2. Nechť X a Y jsou diskrétní náhodné veličiny. Potom nutně [X] H(X,Y) = H(Y,X) [ ] H(X|Y) = H(Y|X) [X] T(X:Y) = T(Y:X) 3.3. Nechť X a Y jsou nezávislé diskrétní náhodné veličiny. Potom nutně [ ] H(X,Y) je nekonečná [X] H(X|Y) = H(X) [ ] H(X) = H(Y) 3.4. Nechť X a Y jsou diskrétní náhodné veličiny a existuje funkce f, tak že X=f(Y). Potom nutně [ ] H(X|Y) = 0 [ ] H(Y|X) = 0 [X] H(X|Y) je menší nebo rovna H(X) 3.5. Nechť U, V, X, Y jsou spojité (reálné) náhodné veličiny a c,d reálné nenulové konstanty takové, že U=cV, X=dY. Potom nutně [ ] H(U) = H(V) [ ] H(X) = H(Y) [ ] T(U:X) = T(V:Y) 3.6. Kódováním rozumíme výhradně [X] zobrazení z jedné abecedy do druhé [X] zobrazení z množiny posloupností znaků jedné abecedy do množiny posloupností znaků druhé abecedy [ ] převod zpráv do tvaru nesrozumitelného jiné osobě, než je zamýšlený příjemce 3.7. Kompresní kódování [X] může snížit průměrnou délku zpráv [ ] může zvýšit průměrnou délku zpráv [ ] může snížit entropii kódu 3.8. Nechť L je průměrný počet bitů připadajících na jeden znak zdroje při binárním kódování. Platí [X] Neexistuje kódování takové, že L je nižší než entropie zdroje. [ ] Neexistuje kódování takové, že L-1 je nižší než entropie zdroje. [X] Vždy existuje kódování takové, že L-1 je nižší než entropie zdroje. 3.9. Uvažujme kód, který každému zdrojovému znaku Z přiřadí slovo obsahující N opakování znaku Z. Při jeho použití [X] lze rozpoznat až N-1 chyb v jednom slově tohoto kódu. [ ] nelze opravit více než N/2 chybných znaků jednom slově tohoto kódu. [ ] nelze opravit N/2 chybných znaků v jednom slově tohoto kódu, je-li N sudé. 3.10. Kapacita komunikačního kanálu mezi zdrojem X a příjemcem Y závisí na [ ] fyzické rychlosti přenosu jednoho bitu kanálem [ ] vzájemné informaci T(X:Y) [ ] pravděpodobnostním rozložení znaků zdroje ====== 4 ====== 4.1. Uvažujte nekonečnou zprávu 000111000111000111... [X] tuto zprávu lze komprimovat [ ] tuto zprávu nelze komprimovat, protože P(0)=P(1) [ ] každý n-tý znak je statisticky nezávislý na prvním až (n-1)ním znaku 4.2. Turingův stroj [ ] byl prvním sériově vyráběným osobním počítačem [X] je matematickým modelem pro výpočetní procesy [X] může implementovat jakýkoliv algoritmus, což je dokázáno matematickou větou. 4.3. Kompresní algoritmus, který jakoukoliv zprávu zakóduje do zprávy kratší a jednoznačně dekódovatelné [ ] existuje pouze pro binární zprávy [ ] existuje, ale nelze implementovat Turingovým strojem [X] neexistuje 4.4. Algoritmická entropie (tj. Kolmogorovská složitost) zprávy [ ] je funkcí pravděpodobnostního rozložení symbolů v této zprávě [ ] je délka nejdelšího programu generujícího tuto zprávu [X] je délka nejkratšího programu generujícího tuto zprávu 4.5. Výpočet algoritmické entropie jakékoliv zprávy [X] není obecně možný, jde o nerozhodnutelný problém. [ ] lze vždy spočítat v čase rostoucím maximálně exponenciálně s délkou zprávy [ ] je vždy možný, jde-li o zprávu v binárním kódu přijme zdrojový kód libovolného programu P a jeho D a rozhodne v konečném čase, zda se program P na vstupu 4.6. Algoritmus, který libovolná vstupní data D zastaví, či zacyklí: [ ] existuje pouze pro binárně kódované programy P [ ] existuje, ale nelze implementovat Turingovým strojem [X] neexistuje 4.7. Konzistentní formální systém, v němž lze dokázat všechny aritmetické zákonitosti, [X] obsahuje i tvrzení v tomto systému nedokazatelná [ ] je nutně úplný, tj. lze v něm dokázat jakékoliv tvrzení formulovatelné jazykem tohoto systému [ ] neexistuje ====== 5 ====== 5.1. Paměťová náročnost prohledávání do šířky stavového prostoru reprezentovaného stromem o hloubce d a faktorem větvení b je [ ] bd [X] b^d [ ] d^b 5.2. Časová náročnost prohledávání do šířky stavového prostoru reprezentovaného stromem vzrůstá [ ] lineárně s rostoucí hloubkou stromu [X] exponenciálně s rostoucí hloubkou stromu [ ] exponenciálně s rostoucím faktorem větvení 5.3. Časová náročnost prohledávání do hloubky stavového prostoru reprezentovaného stromem vzrůstá [ ] lineárně s rostoucí hloubkou stromu [X] exponenciálně s rostoucí hloubkou stromu [ ] exponenciálně s rostoucím faktorem větvení 5.4. Paměťová náročnost prohledávání do hloubky stavového prostoru reprezentovaného stromem o hloubce d a faktorem větvení b je [X] bd [ ] b^d [ ] d^b 5.5. Algoritmus prohledávání do hloubky s iterativně se zvyšující hloubkou prohledávání při prohledávání stavového prostoru, který neobsahuje cykly [ ] je paměťově náročnější než prohledávání do šířky [ ] je paměťově stejně náročné jako prohledáváni do šířky [X] je paměťově méně náročné než prohledávání do šířky 5.6. Prohledávání do hloubky má nižší paměťovou náročnost oproti prohledávání do šířky v případě, že [ ] stavový prostor má faktor větvení b vždy menší než je jeho hloubka d (b ≤ d) [ ] stavový prostor neobsahuje cykly [ ] velikost OPEN seznamu nepřekročí faktor větvení (b ≤ |OPEN|) ====== 6 ====== 6.1. Přípustná heuristika h [X] zaručí nalezení nejlepšího řešení [X] zaručí nalezení řešení v nejkratším čase [X] vždy zabrání zacyklení prohledávacího algoritmu 6.2. Heuristika h je přípustná, když [X] h(n) ≤ h*(n) ∀ n [ ] h(n) ≤ h*(n0) ∀ n [ ] h(n) ≤ h*(n{goal}) ∀ n 6.3. Heuristika h je přípustná, když [ ] h(n_0) ≤ h(n) ∀ n [X] h(n) ≤ h*(n) ∀ n [ ] h*(n) ≤ h*(n_{goal}) ∀ n 6.4. Heuristika h je přípustná, když [ ] g(n) ≤ g*(n) ∀ n [X] h(n) ≤ h*(n) ∀ n [X] f(n) ≤ f*(n) ∀ n 6.5. Heuristika h1 je více informovaná (dominuje) heuristice h2 když [X] h2(n) ≤ h1(n) ≤ h*(n) ∀ n [ ] h1(n) ≤ h1*(n) ale neplatí h2(n) ≤ h2*(n) ∀ n [ ] h2(n) ≤ h2*(n) ale neplatí h1(n) ≤ h1*(n) ∀ n 6.6. Je-li heuristika monotónní [ ] není přípustná [ ] je přípustná [X] je lokálně přípustná 6.7. A* nalezne optimální řešení [X] existuje-li, [X] je-li h přípustná [ ] pouze neobsahuje-li stavový prostor cykly 6.8. Se vzrůstající kvalitou heuristiky h algoritmus A* [ ] nalezne kvalitnější řešení [X] prohledá menší část stavového prostoru [ ] nalezne větší počet správných řešení ====== 7 ====== 7.1. Nevýhodou lokálního prohledávání stavového prostoru pomocí algoritmu hill- climbing je, že: [ ] prohledávání je neúplné [ ] stavový prostor je nekonečný [ ] prohledávání může uváznout v lokálním minimu 7.2. Tendenci algoritmu hill-climbing uvíznout v lokálním extrému lze částečně řešit: [X] opakovaným restartem algoritmu z náhodně vybraných počátečních bodů [ ] opakovaným restartem algoritmu ze stejného počátečního bodu [ ] náhodným restartem algoritmu ze stejného počátečního bodu 7.3. Genetický algoritmus: [ ] optimalizuje počet chromozómů v populace [X] optimalizuje fitness funkci [ ] optimalizuje pravděpodobnost křížení ====== 8 ====== 8.1. Při rozhodování za neurčitosti za rozhodovací strategii považujeme: [X] pravidlo pro výběr rozhodnutí na základě pozorovaných příznaků [ ] postup, jenž nám zajistí optimální rozhodnutí pro aktuální vnitřní stav [ ] funkci, která hodnotí kvalitu všech rozhodnutí přes všechny stavy 8.2. Kritérium MiniMax při rozhodování za neurčitosti: [X] volí rozhodovací strategii, která minimalizuje maximální riziko přes všechny možné vnitřní stavy [ ] je založeno na znalosti apriorního pravděpodobnostního rozložení stavů [ ] volí vnitřní stav s minimálním rozdílem mezi apriorní a aposteriorní pravděpodobností (před a po pozorování příznaků) 8.3. Bayesovská optimální strategie: [X] minimalizuje střední riziko [X] je založena na znalosti apriorního pravděpodobnostního rozložení stavů [ ] lze ji sestrojit "bod po bodu", tj. nalezením optimálního rozhodnutí pro jednotlivá pozorování příznaků. 8.4. Pro bayesovský klasifikátor platí: [ ] objekt vždy přiřadí do nejpravděpodobnější třídy ve smyslu pravděpodobnosti třídy podmíněné daným příznakovým vektorem [ ] množství dat nutných k odhadu výše zmíněné podmíněné pravděpodobnosti roste lineárně s požadovanou přeností odhadu [ ] minimalizuje střední chybu klasifikace 8.5. Naivní bayesovská klasifikace je postup, který: [ ] není prakticky využitelný, protože na rozdíl od bayesovské klasifikace je jeho složitost exponenciální vzhledem k počtu příznaků (složek příznakového vektoru) [ ] předpokládá rovnost příznaků v rámci dané třídy [X] předpokládá nezávislost mezi příznaky (složkami příznakového vektoru) 8.6. O perceptronu lze prohlásit: [X] jde o lineární klasifikátor [ ] jde o nejjednodušší trojvrstvou dopřednou neuronovou síť, která umožňuje implementovat jednoduché logické funkce jako je AND, OR nebo XOR [ ] nejde o neuronovou síť, protože u něj nepozorujeme emergentní jevy nutné pro toto pojmenování 8.7. Klasifikace metodou nejbližších sousedů (kNN) je založena na myšlence podobnosti. Jde o podobnost mezi: [ ] podobnost mezi příznakovými vektory reprezentujícími (klasifikované) objekty [ ] vzájemnou podobnost pro dvojice testovacích příkladů [X] podobnost mezi třídami trénovacích a testovacích příkladů 8.8. Klasifikace metodou nejbližších sousedů (kNN): [ ] je lineární metodou - rozhodovací hranice je vždy lineární [ ] čím vyšší je počet sousedů (k), tím je klasifikace přesnější (výpočetní složitost ale roste exponenciálně s k a proto volíme k malá) [ ] při optimálně zvoleném k se kNN klasifikátor shoduje s Bayesovským klasifikátorem 8.9. O trénovací chybě klasifikátoru lze prohlásit: [X] jde o relativní četnost nesprávně klasifikovaných příkladů v trénovacích datech [X] pro klasifikátor podle nejbližšího souseda (1-NN) je tato chyba nulová [ ] je nevychýleným odhadem středního rizika klasifikátoru 8.10. O testovací chybě klasifikátoru lze prohlásit: [ ] je vždy vyšší nebo rovna trénovací chybě, která je optimistickým odhadem středního rizika klasifikátoru [ ] pro klasifikátor podle nejbližšího souseda (1-NN) je tato chyba nulová [ ] je nevychýleným odhadem středního rizika klasifikátoru ====== 9 ====== 9.1. Algoritmus minimax, používaný pro prohledávání konečného herního stromu [X] je úplný [ ] má lineární časovou náročnost [X] má lineární paměťovou náročnost 9.2. Algoritmus minimax, používaný pro prohledávání konečného herního stromu [X] je optimální [X] má exponenciální časovou náročnost [ ] má exponenciální paměťovou náročnost 9.3. Algoritmus založený na alfa/beta prořezávání stavového prostoru umožní prohloubit hloubku prohledávání při zachování stejné časové náročnosti [X] na dvojnásobek [ ] až na dvojnásobek [ ] až o třetinu 9.4. Kvalitu alfa/beta prořezávání stavového prostoru zásadním způsobem ovlivňuje [ ] hloubka stavového prostoru [ ] faktor větvení [ ] uspořádání následníků (expandantů) 9.5. Alfa/beta prořezávání stavového prostoru [X] zachovává úplnost [ ] nezmění časovou náročnost [X] nezmění optimalitu algoritmu minimax 9.6. Při hraní her s prvkem náhody [ ] klesá význam prohledávání do velké hloubky herního stromu [ ] klesá význam alfa/beta prořezávání [ ] klesá efektivní faktor větvení 9.7. Omezení hloubky prohledávaného herního stromu (cut-off) search [ ] zachovává úplnost [ ] nahrazuje přesné hodnoty užitku (utility) uzlu odhadem [ ] zabraňuje horizontálnímu efektu 9.8. Šachový algoritmus DeepBlue, který porazil Kasparova, prohledával stavový prostor do hloubky v řádech [ ] desítek tahů [ ] stovek tahů [ ] tisíců tahů 9.9. Algoritmus TDGammon, který hraju hru Backgamon na mistrovské úrovni, prohledává stavový prostor do hloubky v řádech [ ] desítek [ ] stovek [ ] tisíců 9.10. Hodnoty, které vrací funkce eval při prohledávání herního stromu s omezenou hloubkou (cut-off search) při hrách bez prvku náhody [ ] musejí být přesné [ ] nemusejí být přesné, ale stačí když jsou monotónně transformované s ohledem na reálné hodnoty [ ] nemusejí být přesné, ale stačí když jsou lineárně transformované s ohledem na reálné hodnoty 9.11. Hodnoty, které vrací funkce eval při prohledávání herního stromu s omezenou hloubkou (cut-off search) při hrách s prvkem náhody [ ] musejí být přesné [ ] nemusejí být přesné, ale stačí když jsou monotónně transformované s ohledem na reálné hodnoty [ ] nemusejí být přesné, ale stačí když jsou lineárně transformované s ohledem na reálné hodnoty ====== 10 ====== 10.1. Pokud jsou a,b,c,d atomické formule, pak Výraz a & b & c -> d je [X] trojargumentový predikát [ ] pravidlo modus ponens [X] formule jazyka predikátové logiky 10.2. Formalismus sémantické sítě umožňuje [ ] řešit konflikty [ ] vyvozovat děděním [ ] modularizovat znalosti 10.3. Součástmi produkčního systému jsou [X] báze pravidel [X] interferenční stroj [X] báze dat 10.4. Relace ISA se v systému rámců využívá [ ] k dědění vlastností [X] k označení konkrétní instance generického rámce [ ] k označení relace mezi generickými rámci 10.5. Relace AKO se v systému rámců využívá [X] k dědění vlastností [ ] k označení konkrétní instance generického rámce [ ] k budování ontologií 10.6. Scénář je [ ] časová posloupnost predikátových výrazů [X] posloupnost rámců [ ] soubor podmínek pro aktivaci pravidel produkčního systému 10.7. Výraz matka(petr, jana). Je [ ] trojargumentovým predikátovým výrazem [X] elementárním faktem [ ] tvrzením, které může nabývat hodnot T a F [//to by tam nesměla být ta tečka//] 10.8. Povinnou položkou každého rámce je [ ] odkaz k podřazenému rámci [//povinný je odkaz k nadřazenému//] [X] jméno rámce [ ] nastavená hodnota počtu povolených položek 10.9. Předností znalostních taxonomií je [ ] efektivní řešení konfliktů [ ] zpětné řetězení pravidel [ ] vysoká modularita znalostí 10.10. Prohledávání stavového prostoru lze formalizovat produkčním systémem pokud [ ] nepoužíváme backtracking [ ] se prohledává jenom do šířky [ ] pokud není třeba řešit konflikty ====== 11 ====== 11.1. Expertní systémy diagnostické [ ] generují vhodnou posloupnost operátorů pro dosažení cíle [ ] jsou vhodné pro návrh terapie v medicíně [ ] uvažují n(n-1) možných hypotéz, kde n je počet listových tvrzení 11.2. Expertní systémy s tabulí využívají stratgeie [ ] řízení tokem dat [ ] řízení peer-to-peer (já-pán ty-pán) [X] typu démon 11.3. Obecný model pro práci s neurčitou informací vždy zahrnuje [ ] vzorec pro výpočet neurčitosti logické kombinace tvrzení [ ] odhady neurčitostí pravidel [ ] vzorec pro kombinaci vlivu více cest uvažování 11.4. Kompozicionální model pro práci s neurčitou informací vyžaduje brát do úvahy [ ] hodnotu kompozicionálního predikátu pro vágnost [ ] všechny podmíněné a sdružené pravděpodobnosti tvrzení [ ] podmínku nezávislosti všech tvrzení 11.5. Listový uzel inferenční sítě je [ ] nedotazovatelný [ ] cílový [ ] mezilehlý 11.6. Mezilehlý uzel inferenční sítě může být [ ] listovým [ ] dotazovatelným či nedotazovatelným [ ] ohodnocený měrou důvery 11.7. Ve fuzzy modelu pro práci s neurčitou informací platí [ ] CF (E1 & E2) = max {CF (E1); CF(E2)} [ ] CF (E1 & E2) = CF(E1) + CF(E2) – CF(E1).CF(E2) [ ] CF (E1 & E2) = CF(E1) + CF(E2) 11.8. Míra postačitelnosti lambda v Pseudobayesovském modelu pro práci s neurčitou informací leží [ ] v intervalu <0,1) [ ] v intervalu (0, nekonecno) [ ] v intervalu (1, P(H/E)) 11.9. Na začátku konzultace expertního systému je aktuální model tvořen: [ ] nulovými měrami důvěry ve všechna tvrzení [ ] expertovými odhady síly pravidel [ ] apriorními měrami důvěry, které dodal uživatel 11.10. Grafem inferenční sítě může být [X] orientovaný strom [X] les [ ] orientovaný graf s cykly ~~DISCUSSION~~