5

Question 1

Definice pojmů analogie

Answer 1

1 analogie gramatiky základním prvkem jazyka jsou písmena abecedy, ty skládají slova , věty . Gramatika jsou pravidla pro tvorbu slov které říkají které posloupnosti písmen tvoří slova a které ne jazyk je množina všech slov
2 analogie gramatiky základním prvkem jsou dále nedělitelné slova . Místo abecedy se vychází ze slovníku . Gramatika jsou pravidla pro sestavování vět ze slov . Jazyk je množina všech vět

Question 2

Co je to slovo

Answer 2

Libovolná konečná i prázdná posloupnost znaků abecedy

Question 3

Co je to jazyk

Answer 3

Libovolná podmnožina množiny všech slov

Question 4

Co je to gramatika

Answer 4

Soubor pravidel, který nám pomoci přepisovacích pravidel umožní vytvořit všechna slova jazyka z počátečního symbolu. Počáteční symbol nepatří do abecedy . Terminální symbol proměnná která se dále nahrazuje, neterminální symbol - prvek abecedy jazyka

Question 5

Co je to generativní gramatika

Answer 5

Uspořádaná čtveřice G= (Vn, Vt, P, S)
Vn — množina neterminálních znaků
Vt — množina terminálních znaků
P — množina přepisovacích pravidel
S — počáteční symbol

Question 6

Jaká je hierarchie gramatik podle chomskeho

Answer 6

L0 všechny gramatiky a jimi generované jazyky
L1 kontextová gramatika ( uderzujeme kontext, který obklopuje neterminální znak z prava i leva
L2 bezkontextova gramatika (nevyžaduje dodržení původního tvaru
L3 regulární gramatika

Question 7

Co jsou to regulární výrazy

Answer 7

Jedná se o sekvenci znaku které definují nějaký vzor
# číslo
$ písmeno
a-Z 0-9
| nebo
* opakovaní
Můžeme používat pro vyhledávání nebo filtrování uživatelského vstupu

Question 8

Výpočetní složitost

Answer 8

Časová složitost jak dlouho algoritmus poběží v závislosti na velikosti vstupních dat
Prostorová složitost kolik paměti je potřeba k vykonání algoritmu v závislosti na velikosti vsuonich dat

Question 9

Co je asymptotická složitost

Answer 9

Udává funkci jak bude narůstat výpočetní složitost v závislosti na velikosti vstupních dat
F náleží O(n ) funkce f roste maximálně jako N
F náleží o(n ) funkce f roste pomaleji než n
F náleží ø(n ) růst f a n je srovnatelny

Question 10

Jaké jsou asymptotické třídy

Answer 10

• 0(1) = konstantní (doba nezálezi na velikosti vstupu)
• O(log n) = logaritmický rüst (napr. vyhledávání ve strukturách typu binární strom)
  O(n*log n) = chytré sort algoritmy (quick sort)
• O(n) = lineární rüst
• O(n2) = kvadratický rust (primitivní sort algoritmy)
• 0(n3) = kubický rüst
• O(nk) = polynomiální rúst pro néjaké prirozené císlo k
• O(n!) = faktoriální rüst

Question 11

Jaké jsou třídy složitosti

Answer 11

P - obsahuje zvládnutelné problémy pro větší množství dat je náročné řeší se deterministicky
NP obsahuje problémy které jsou řešeny nedeterministickými turingovymi stroji
NPH to jsou nejtěžší problémy z NP
NPC velmi těžké , když ale vyřešíme můžeme vyřešit všechny NP P i NPC problémy