10 Flashcards
Rozklad množin
systém množin, které pokrývají původní množinu a žádné 2 nemají společné prvky
Kartézský součin
množina uspořádaných n-tic (AxB = {(a,b) | a¢A and b¢B)
Relace (binární)
Vyjadřuje vztah prvků jedné množiny k prvkům druhé množiny;
Podmnožina kart. součinu.
Relace ekvivalence
reflexivní, symetrická, tranzitivní
Reace částečné uspořádání
reflexivní, antisymetrická, tranzitivní
Zobrazení
binární relace, kdy každý prvek z 1. množiny se namapuje na nejvýše jeden prvek z 2. množiny.
Vlastnosti zobrazení (jaké může být?)
injektivní, surjektivní, bijektivní
Injektivní zobrazení
prostá,
Surjektivní zobrazení
Každý prvek z B má alespoň 1 prvek z A
Bijektivní zobrazení
(zobrazení Na) Každý prvek z B má právě jeden z A
Svaz
Uspořádatelá množina. Množina A s relací R je svazem, pokud pro každou dvouprvkovou podmn. (v relaci R) lze definovat minimum a maximum.
Grupa
Množina s binární operací, na které je uzavřená. (3 axiomy: asociativita, existence neutrál. a inverz. prvku)
Limita (definice)
Fce f má v bodě a limitu b když:
1) a je hromadným bodem mn Df.
2) k libovolnému okolí U(b) limity b existuje okolí U(a) bodu a tak, že f zobrazí redukované okolí bodu a do redukovaného okolí limity b.
Limita obecně - lim_x->a f(x) = b
funkční hodnota v bodě a se blíží číslu b
Derivace obecně
okamžitá rychlost změny; směrnice tečny ke grafu funkce
Derivace vzorec
f’(x) = lim_h->0 ( f(x+h) - f(x) ) / h
Primitivní funkce (k funkci f)
zderivováním vzikne původní fuknce f
Neurčitý integrál (funkce f)
soustava všech primitivních funkcí F(x) k f(x)
Určitý integrál
plocha pod grafem, Newton-Leibnitzova formule - [ F(x) ]ab, F(b) - F(a)
Číslená soustava
uspořádaná množina symbolů (číslic)
Základ soustavy
báze, radix - max. počet číslic v soustavě
polyadická soustava
číslo získáme součtem mocnin základu vynásobených číslicí
Zápis čísla
poziční, polynomiální
Algebra
Definuje množinu prvků, množinu operátorů, axiomy a teorémy
Booleove algebra
šestice (B, +, *, ‘, 0, 1)
axiomy bool. algebry
komutativnost, distributivnost, neutralita 0 a 1, komplementarita
teorémy bool. algebry
asociativita, agresivita 0 a 1, deMorgan, idempotance, sousednost
Princip duality
umožňuje realizovat obvod s pomocí 1 operace a komplementu proměnných
Množina definice
Množina je souhrn objektů, které nazýváme prvky množiny. Prvky se neopakují, může být uspořádaná. Zapsána výčtem či predikátem.
Gradient (derivace…)
Gradient je vektor parciálních derivací podle jednotlivých proměnných.
potenční množina
Množina všech podmnožin dané množiny; obsahuje 2^X prvku
Jazyk
libovoná podmnožina Sigma* (= všechny řetězce nad abecedou Sigma)
Abeceda
konečná, neprázdná množina symbolů
Retězec
posloupnost symbolů nad abecedou
Fundamentální modely pro regulářní jazyky jsou
regulární výrazy a konečné automaty
Převod KA na determ. KA
ostranění e-přechodů, odstranění nedeterminismu (sloučení stavů)
Operace nad jazyky
konkatenace, mocnina, iterace, reversace
mocnina
i=0 L^0={e}; i<0 L^i=LL^i-1
iterace
sjednocení mocnin
Konečný automat KA
pětice (Q, Sigma, R, s, F)
R pravidla typu pa->q; p,q$Q; a$Sigma + {e}
Gramatika
čtveřice (N, T, P, S)
neterminály, terminály, pravidla, poč. neterminál
Založena na konečné množina pravidel, které generují rětezce daného jazyka.
Jazyk generovaný gramatikou L(g) =
= {w: w$T, s => w}
Regulární výraz (definice)
řetězec popisující regulární jazyk
Zásobníkový automat
sedmice (Q, Sigma, Gama, R, s, S, F)
pravidla Apa -> wq
determ. ZA
Z každé konfigurace může provést max. jeden přechod.
konfigurace ZA
řetězec GamaQSigma (stav zásobníku, aktuální stav, stav páský)
rozšíření ZA
může číst více než jen jeden symlob ze zásobníku
(stejně silný jako ZA), používá se u syntax. anal. zdola nahoru
přijmutí jazyka
koncový stav nebo prázdný zásobník
ne-BKG gramatika
pravidla mají na levé straně více než jen jeden neterminál
Využití BKG
syntax. analýza
Využití regulární gramatiky (RV, …)
lex. analýza
Překladač
Program, jehož vstupem je text zdrojového kódu (zdrojový program) a výstupem cílový program.
Syntax. shora / zdola
Shora: Od počátečního neterminálu vyjadřujeme aplikací pravidel terminály, ZA, LL-gramatiky
Zdola: Aplikací pravidel na tokeny se snažíme dostak k počátečnímu neterminálu. Rozšířený ZA, precedenční analýza, LR gramatika
Derivační strom
Znázroňuje aplikaci jednotlivých pravidel. Konc. uzly jsou terminály.
Byte kód
Je to instrukční sada navržená pro snadnou přenositelnost mezi platformami. Např. tříadresný kód.
Regulární matice
Determinant různý od nuly. Čtvercová NxN, N=hodnost matice. Existuje inverzní, vlastní čísla jsou nenulová.
Stavový prostor
Definován dvojicí (S,O): stavy, operátory, kterými lze měnit stavy.
Úloha
Dvojice (s0, G): poč. stav, množina cílových stavů
Řešení úlohy
posloupnost operátorů z s0 do G (~cesta v grafu)
Hodnoticí kritéria
úplnost, optimálnost, časová a paměť. náročnost
UCS
úplná, optimální; exp; Fronta open; + ceny přechodů
Backtracking
neúplný, neoptimální; jako DFS, ale generuje jen jeden uzel -> nízká pamět. náročnost.
Informované metody
mají informaci o cílovém stavu; ohodnocení = cena uzlu (součet přechodů po sem) + odhad (heuristika) do cíle
Greedy search
jen heuristika
A-star
nejznámější informovaná; náročnost záleží na heuristice - je to spodní odhad skutečné ceny cesty
Lokální prohledávání (metody)
Hillclimbing; simulované žíhání
Hill-climbing
jako greedy, ale končí když nenajde uzel s lepším ohodnocením; pouze uzel Current a Next (nízká paměť náročnost); najde pouze cílový stav, ale ne cestu k němu
Simulované žíhání
snaží se překonat lokální extrémy vedoucí k neúspěchu u Hill-climg.
Metody hraní her (princip, co najdou?)
Nalezení tahu hráče, který je právě na řadě
Min-max
Na tahu hráč A: volej rekurzivně pro všechny uzly a vrať maximum.
Na tahu hráč B: volej rekurzevně pro všechny uzly a vrať minumum.
Je-li uzel listový, vrať jeho hodnotu.
Alpha-beta
Rozšíření Min-maxu. Zamezení zbytečnému prohledávání. Podmínka if alpha>=beta zastav.
Výhody OOP
analogie mezi objekty reálného světa;
znovupoužitelnost (blackbox);
dědičnost
Třída
vzor pro instanciaci objektů, obsahuje třídní proměnné a metody (rozhraní)
Objekt
Entita zapouzdřující stavové informace a poskytující sadu operací nad tímto objektem (částmi).
Rozhraní
Množina zpráv, které se třída zavazuje rozumět; Obsahuje jméno, parametry a return type;
Metoda
Zapouzdřená funkce objektu - obsahuje implementaci reakce na zprávu.
Abstrakce
počítačový pohled na problém reálného světa
Invariant
část kódu, kde se hodnoty proměnných při opak. průchodu nemění.
Zapouzdření
skrytí implementace, dostupné rozhraní; umožňuje znovupoužitelnost
Polymorfismus
reakce na stejnou zprávu se liší v závislosti na konkrétním objektu; řeší se tabulkou virtuálních metod
pozdní vazba
při překladu se nedá rozhodnout, která metoda se má použít, do tabulky virt. metod se dají všechny varianty a za běhu se vybere.
Dědičnost
způsob implementace sdíleného chování; dědění: implementace x rozhraní
Nevýhody OOP
někdy neexistuje analogie mezi real-world; nelze porušit zapouzdření; výsledný kód je pomalejší; režie na uložení obj. v paměti
Dědičnost u beztřídních J.
Odkaz na prototyp; je v rodičovském slotu (použitje se při delegaci)
Rys
objekt, který obsahuje sdílené chování
