Základní matematické pojmy

Question 1

Abeceda

Answer 1

Konečná množina prvků zvaných symboly

Question 2

Argument

Answer 2

Vstup funkce

Question 3

Binární relace

Answer 3

Relace, jejíž doménou jsou množiny párů (dvojic, 2-tic)

Question 4

Booleovská operace

Answer 4

Operace na logických hodnotách (true/false nebo 1/0)

Question 5

Kartézský produkt

Answer 5

Operace na množině produkující množinu všech n-tic prvků dané množiny

Question 6

Komplement

Answer 6

Operace na množině produkující množinu všech prvků, které nejsou přítomny v dané množině

Question 7

Konkatenace

Answer 7

Operace, která spojuje řetězce jedné množiny dohromady s řetězcem z druhé množiny

Question 8

Konjunkce

Answer 8

Booleovská operace AND (pravdivá pokud oba operandy jsou 1)

Question 9

Cyklus v grafu

Answer 9

Cesta v grafu, která začíná i končí ve stejném uzlu

Question 10

Orientovaný graf

Answer 10

Graf, ve kterém jsou hrany mezi uzly znázorněny šipkou vyjadřující směr propojení

Question 11

Disjunkce

Answer 11

Booleovská operace OR (pravdivá, pokud alespoň jeden argument je 1)

Question 12

Doména / Definiční obor

Answer 12

Množina možných vstupů funkce. Definiční obor zobrazení
z množiny X do množiny Y tvoří právě ty prvky množiny X, pro něž je definován obraz v množině Y.

Question 13

Hrana

Answer 13

Úsečka v grafu

Question 14

Element, prvek

Answer 14

Objekt v množině

Question 15

Prázdná množina

Answer 15

Množina bez prvků

Question 16

Prázdný řetězec

Answer 16

Řetězec s velikostí 0

Question 17

Ekvivalence

Answer 17

Binární relace, která je reflexivní, symetrická a tranzitivní

Question 18

Funkce

Answer 18

Operace, která každé vstupní hodnotě z definičního oboru přiřazuje výstupní hodnotu z oboru hodnot

Question 19

Graf

Answer 19

Kolekce bodů (vrcholů) a úseček, které tyto body propojují (hrany)

Question 20

N-tice

Answer 20

Relace n objektů. Oproti množině zde záleží na pořadí

Question 21

Jazyk

Answer 21

Množina řetězců nad abecedou

Question 22

Vrchol

Answer 22

Bod grafu

Question 23

Pár, dvojice

Answer 23

N-tice dvou elementů

Question 24

Predikát

Answer 24

Funkce, jejíž obor hodnot je {PRAVDA, NEPRAVDA}

Question 25

Obor hodnot

Answer 25

Množina, jejíž prvky jsou používány jako výstupní hodnoty funkce. Obor hodnot zobrazení
z množiny X do množiny Y tvoří množina všech hodnot množiny Y, kterých zobrazení T nabývá.

Question 26

Množina

Answer 26

Skupina objektů (prvků)

Question 27

Symbol

Answer 27

Prvek abecedy

Question 28

Strom

Answer 28

Propojený graf bez cyklů

Question 29

Průnik

Answer 29

Množina, obsahující společné prvky dvou množin, na které je průnik aplikován

Question 30

Definice nedeterministického automatu NFA

Answer 30

Pětice (Q,Sigma, delta, q0, F):
Q - konečná množina stavů
Sigma - konečná abeceda
delta - Q x Sigma s epsilon -> P(Q) - přechodová funkce (stav, symbol z abecedy, podmnožina stavů)
q0 e Q - startovní stav
F podmnožina Q - příjmací stavy

Question 31

Regulární jazyk

Answer 31

Jazyk pro který existuje konečný automat, který jej přijímá

Question 32

Definice deterministického automatu

Answer 32

Pětice (Q, Sigma, delta, q0, F)
Q - konečná množina stavů
Sigma - konečná abeceda
delta - přechodová funkce stav, symbol -> stav Q x Sigma -> Q
q0 e Q - počáteční stav
F podmnožina Q - množina příjmacích stavů

Question 33

Regulární výraz

Answer 33

Stejně jako aritmetický výraz tvoří čísla, Regulární výraz tvoří jazyk
Formální definice:
R je regulární výraz pokud R je:
1. symbol abecedy
2. epsilon, prázdný řetězec
3. prázdná množina
4. (R1 U R2)
5. (R1 o R2)
6. R1*
R1 a R2 musí být Regulární výraz

Question 34

Pumping lemma

Answer 34

Věta dokazující, že jazyk je regulární.
Pokud A je reg. jazyk, pak existuje číslo p (pumpovací délka), kde pokud s je řetězec délky alespoň p, může být rozdělen do 3 částí s = xyz splňující tyto podmínky:
1. pro každé i větší nebo rovno 0, xyiz náleží A
2. délka y větší než nula
3. délka xy menší rovno p