Základní matematické pojmy Flashcards

1
Q

Abeceda

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Argument

A

Vstup funkce

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Binární relace

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Booleovská operace

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Kartézský produkt

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Komplement

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Konkatenace

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Konjunkce

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Cyklus v grafu

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Orientovaný graf

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Disjunkce

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Doména / Definiční obor

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Hrana

A

Úsečka v grafu

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Element, prvek

A

Objekt v množině

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Prázdná množina

A

Množina bez prvků

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Prázdný řetězec

A

Řetězec s velikostí 0

17
Q

Ekvivalence

A

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

18
Q

Funkce

A

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

19
Q

Graf

A

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

20
Q

N-tice

A

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

21
Q

Jazyk

A

Množina řetězců nad abecedou

22
Q

Vrchol

23
Q

Pár, dvojice

A

N-tice dvou elementů

24
Q

Predikát

A

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

25
Obor hodnot
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á.
26
Množina
Skupina objektů (prvků)
27
Symbol
Prvek abecedy
28
Strom
Propojený graf bez cyklů
29
Průnik
Množina, obsahující společné prvky dvou množin, na které je průnik aplikován
30
Definice nedeterministického automatu NFA
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
31
Regulární jazyk
Jazyk pro který existuje konečný automat, který jej přijímá
32
Definice deterministického automatu
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ů
33
Regulární výraz
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
34
Pumping lemma
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
35