Úvod do teoretické informatiky

• Souhrn předmětů (prvků) chápaných jako celek/ Kolekce vzájemně odlišitelných objektů - prvků.
• Definice výčtem x charakteristickou vlastností - M = {1,2,3}, M = {x∈R; x<4}
• Na pořadí nezáleží, duplicity nejsou možné {1,2,2}={2,1},{1,2}={2,1}
• Velikost = |X|; X = {1,2,2}; |X| = 2
  • Nekonečná x Konečná
  • Prázdná množina = ∅,|∅| = 0 != {∅}, |{∅}| = 1
• Prvek x náležící do množiny M značíme x ∈ M, čteme prvek x náleží do množiny M
• Podmnožina P množiny M = všechny prvky množiny P jsou obsaženy v množině M (značíme ⊆)
  • ∀ A: ∅ ⊆ A
  • M⊆M
  • P={1}, M={1,2} => P⊆M
• Operace na množinách
  • Průnik => M ∩ N = bude obsahovat prvky, které se vyskytují v M i v N
  • Sjednocení => M ∪ N = bude obsahovat prvky, které se vyskytují v M nebo v N (tzn. i ty co jsou v obou)
  • Rozdíl => M - N = bude obsahovat prvky, které jsou v M, ale nejsou v N
  • Doplněk => M' nebo = všechny prvky z universa, které M neobsahuje
  • Kartézský součin => M x N = bude obsahovat uspořádané dvojice - první člen z M druhý z N
  • Potenční množina 2^M -
  Relace
  • Libovolný vztah mezi skupinou prvků jedné nebo více množin
  • Klasifikace dle arity - unární, binární, ternární,... n-ární - množina uspořádaných n-tic
  • Binární relace = množina uspořádaných dvojic, např. R = {(a,a),(b,b),(c,c)}
  • U binární relace je možno definovat vlastnosti jako je reflexivita, symetrie, antisymetrie, tranzitivita
  • Zobrazení z množiny X do množiny Y je relace R ⊆ X × Y , kde platí, že pro každý prvek x ∈ X existuje právě jeden prvek y ∈ Y tak že (x, y) ∈ R.
  • Detailnější rozepsání vlastností binárních relací
    • Reflexivita = každý prvek z množiny je v relaci sám se sebou
      • Příkladem reflexivní relace je identita, relace "být menší nebo rovno", relace dělitelnosti, atd.
    • Ireflexivita = žádný prvek z množiny není v relaci sám se sebou
      • Příkladem ireflexivní relace je relace "být menší než"
    • Symetrie = pokud je prvek a v relaci s b, pak je b v relaci s a; (a,b) -> (b,a)
      • Příkladem symetrické relace je identita, nerovnost nebo vlastnost typu "mít stejné znaménko"
    • Antisymetrie = pokud je (a,b) i (b,a) pak musí platit, že a = b
      • Příkladem antisymetrické relace je relace "být menší nebo rovno".
    • Asymetrie = silná antisymetrie = pokud je prvek a v relaci s b, pak b v relaci s a není; (a,b) -> !(b,a)
      • Příkladem asymetrické relace jsou relace "nerovno", "být menší než" nebo "být větší než".
    • Trazitivita = pokud existuje (a,b) a (b,c) pak existuje i (a,c)
      • Příkladem tranzitivní relace je opět relace "být menší nebo rovno", identita, či relace "být příbuzný" na množině lidí.
    • Úplnost - Pro každou dvojici platí, že exituje buď (a,b) nebo (b,a) (nebo i obojí)
      • Příkladem úplné relace je například relace ≤ na libovolné číselné množině.
  Funkce
  • Funkce je název pro zobrazení z nějaké množiny M do množiny čísel (většinou reálných nebo komplexních), nebo do vektorového prostoru
  • Alt.: Funkce na množině M ⊂ R je předpis, který každému číslu z množiny D přiřazuje právě jedno R.
  • Množinu M nazvýváme Definičním oborem funkce a R nazýváme Oborem hodnot funkce.
  • U funkcí můžeme rozhodnovat o mnohých vlastnostech (spíše záležitost matematiky ale co)
    • Monotónnost funkce - určuje zda funkce v daném intervalu klesá či stoupá
    • Sudá funkce - symetrická podle osy Y -> f(x) = -f(x)
    • Lichá funkce - symetrická podle osy X a Y -> -f(x) = f(-x)
    • Prostá funkce - hodnoty pro různá x z definičního oboru se vždy liší; funkce v celém definičním oboru je stále rostoucí, nebo stále klesající
    • omezenost
    • lokální/globální minima/maxima
    • grafy a podrobnosti zde

• Výrok - "Jana zmokla" = atomický výrok -> nedá se rozložit
• Složený výrok - "Jestliže pršelo, Jana zmokla" - rozložitelný na atomické výroky "Pršelo" a "Jana zmokla"
• Logické spojky - spojují atomické výroky do složených = ¬,∧,∨,→,↔
• Formule = atomické nebo složené výroky; Pravdivost formulí - vyhodnocují se binárně (0 x 1) (T x F)
• Pravdivostní ohodnocení
  • Tautologie - pravdivá ve všech ohodnoceních
  • Splnitelná - existuje alespoň jedno pravdivé vyhodnocení
  • Kontradikce - neexistuje ani jedno pravdivé vyhodnocení ( = není splnitelná)
  • Ekvivalence = dvě formule jsou ekvivalentní, jestliže mají při stejném ohodnocení "v" stejnou pravdivostní hodnotu
• Logické vyplývání - pokud jsou pravdivé předpoklady, pak i závěr je pravdivý - ověření pomocí rezoluční metody
• Ekvivalentní operace popsány v tomto PDF

Normálové formy - specifický tvar formule, který je ekvivalentní k původnímu

• DNF - Disjunktivní normálová forma - elementární konjunkce spojené disjunkcemi, př. (p∧q)∨(¬p∧r)∨(p)
• CNF/KNF - Konjunktivní normálová forma - elementární disjunkce spojené konjunkcemi, př. (p∨¬q)∧(¬p∨r)∧(p)
• Úplná K/D normálová forma - v každé části (konjunktu/disjunktu) se vyskytují všechny literály právě jednou, př. (p∨q∨r)∧(¬p∨¬q∨r) = UKNF

• Zavedení proměnných
• Universum - Množina prvků ze kterých můžeme vybírat do proměnných
• Valuace - přiřazení prvků universa proměnným
• Predikáty - vrací pravda/nepravda
  • Arita - nulární, unární - n-ární, popisují vlastnosti, či vztahy 0 - n proměnných
• Kvantifikátory - ∀x = pro všechny x platí, ∃x = existuje alespoň jedno x, nelze je aplikovat na konstanty
• Formule predikátové logiky
  • Atomické formule - mohou obsahovat konstanty (nulární fce), funkce, predikáty a rovnosti
  • Jinak mohou obsahovat kvantifikátory, logické spojky
• Termy - výrazy složené z proměnných, konstant a funkcí reprezentující prvky universa
• pomocné symboly = "(" + ")"

• Nejjednodušší formální jazyk. Formální jazyk je množina slov nad nějakou abecedou.
• Abeceda = neprázdná konečná množina symbolů/znaků
• Slovo = konečná posloupnost znaků z konkrétní abecedy
• Jazyk = množina (některých) slov tvořených symboly z dané abecedy
• Délka slova = počet symbolů, prázdné slovo = slovo o délce 0
• Zřetězení slov = OST · RAVA = OSTRAVA
• Operace na jazycích = sjednocení, průnik, doplněk, rozdíl, zřetězení, iterace
• Iterace jazyka = zřetězení libovolného počtu (0-n) slov z jazyka
• Regulární jazyk = prázdný jazyk + jazyk obsahující právě jeden znak z abecedy + jazyky vzniklé operacemi popsanými výše nad těmito jazyky
• Zrcadlový obraz slova w = w^R je slovo w zapsané "pozpátku" AHOJ -> JOHA

• Výpočetní model generující formální jazyky
• Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu
• Konečný automat = deterministický = vždy je jasný počáteční stav, vždy je jasné do jakého stavu se přejde při daném vstupu, vždy jsou jasné přijímací stavy.
• Formálně je konečný automat definován jako uspořádaná pětice (Q, Σ, δ, q0, F) (názvy se mohou lišit)
  • Q = neprázdná množina stavů
  • Σ = neprázdná množina vstupních symbolů (abeceda)
  • δ = pravidla přechodů mezi stavy (pro každý stav, n pravidel (n=počet symbolů v abecedě))
  • q0 = počáteční stav (právě jeden)
  • F = množina přijímacích stavů

Zpracovává vstup a generuje výstup

• Řídící tok - sekvence vykonávání jednotlivých kroků, včetně větvení a cyklů
• Dva typy instrukcí - instrukce pracující s daty, instrukce ovlivňující řídící tok(větvení, cykly, návraty,...)
• Algoritmus je vykonáván strojem - např. reálný stroj, virtuální stroj, matematický model
• Stroj pracuje po krocích, v každém kroku se nějak změní konfigurace = popis celkového stroje(paměť, stav)
• Výpočet algoritmu - začíná se v počáteční konfiguraci, každý krok přejde do jiné konfigurace, výpočet končí v koncové konfiguraci
• Invarianta - podmínka, která musí být splněna vždy, na konkrétním místě v algoritmu
  • např invarianta pro cyklus i=0;while(i<10){i++} je, že 0 >= i <= 10. Jelikož posledním krokem v cyklu bude, že se i nastaví na 10 a kdykoliv to je mimo, to do cyklu vůbec nespadne.
  • pro každý řídící stav (vrchol grafu řídícího toku) lze určit invariantu
• Korektnost - Žádná nepovolená operace, výpočet je konečný, výstup odpovídá zadání.

• idealizované modely počítače používané pro výpočet složitosti
• Definují množinu povolených operací
• Turingův stroj
  • Church-Turingova teze = ke každému algoritmu existuje Turingův stroj
  • Respektive pokud nelze problém popsat Turingovým strojem, není tento problém algoritmcky rozhodnutelný
  • Formálně je Turingův stroj šestice
    1. Množina vnitřních stavů
    2. Konečná abeceda symbolů na pásce
    3. Konečná množina vstupních symbolů (podmnožina abecedy)
    4. počáteční stav
    5. Přechodová funkce vpravo, či vlevo
    6. Množina koncových stavů
• RAM stroj
  • Z hlediska výpočetní síly ekvivalentní Turingovu stroji
• Lambda kalkulus
• Konečný automat

Pro rozhodovací problém P neexistuje žádný algoritmus. Tato problematika je zkoumána vědním oborem - Teorií vyčíslitelnosti. Každý algoritmus který je rozhodnutelný, lze zároveň přeložit do jazyka Turingova stroje.
Příkladem takových to problémů je např. Problém zastavení

• U algoritmů řešíme zpravidla dva typy složitosti
  • Časovou složitost - jak závisí doba výpočtu na množství vstupních dat
  • Paměťovou náročnost - jak závisí množství použité paměti na množství vstupních dat
• Velikost vstupu - hodnota udávající velikost vstupu - počet prvků v sekvenci, počet znaků v řetězci, atp.
• přesnou dobu výpočtu můžeme uvádět jako počet kroků nebo počet sekund
• Zpravidla se zaobíráme nejhorším případem, někdy je však vhodné se zaobírat i průměrným případem
• U funkce vyjadřující časovou složitost nám většinou stačí odhad - zanedbáme méně významné členy an^2+b => n^2

• Popisují jak rychle daná funkce roste
• O(f) - množina všech funkcí, které rostou nejvýše tak rychle jako f
• Ω(f) – množina všech funkcí, které rostou alespoň tak rychle jako f
• Θ(f) – množina všech funkcí, které rostou stejně rychle jako f

• For experts:
• Interpretace = každému predikátovému symbolu je určena nějaká n-ární relace z daného Universa

• Valuace = při dané intepretaci I s universem U je valuace funkce, přiřazující jednotlivým proměnným prvky z universa
• Pravdivostní hodnoty tedy přiřazujeme při dané interpretaci s daným universem a při dané valuaci
• Model = Valuace při dané intepretaci, ve které je daná věta pravdivá


• For dummies:
• Interpretace = tělo predikátu, co ten predikát vyhodnocuje
• Valuace = přiřazení konkrétních hodnot do proměnných
• Model = když je interpretace při nějaké valuace pravdivá, tak se jedná o model

1. Převod na CNF
2. Každá elementární disjunkce je klauzulí
3. Jedná se o důkaz sporem -> znegujeme závěr a hledáme prázdnou klausuli = spor
4. Jednoliterální klauzule přiřazujeme k jiným klauzulím obsahující opačnou klauzuli a vyvozujeme nové klauzule (b a !b+c => c)
5. Hledáme tak dlouho dokud jdou nalézt nové klauzule, nebo dokud nenajdeme prázdnou klauzuli ⊥

• Oproti deterministickým automatům mohou mít více počátečních stavů
• Oproti DKA pro každý stav nemusí existovat právě tolik pravidel, kolik je velikost množiny přijímaných symbolů. Může jich být více (opakovat se), či méně, či mohou přijímat prázdné slovo.

Dříve bylo definováno co to regulární jazyk je. Jinou definicí by mohlo být, že Regulární jazyk je takový jazyk, který lze popsat konečným automatem (NDKA / DKA). Pak tedy existuje třída regulárních jazyků REG, která obsahuje všechny regulární jazyky. Při výběru x jazyků třídy REG a provedení určité operace, pak znovu dostaneme jazyk třídy REG.

"Uzavřenost množiny nad operací znamená že výsledek operace s libovolnými prvky z množiny bude opět spadat do dané množiny."

Například můžeme říci, že třída REG je užavřena vůči iteraci. Je jednoduché udělat NDKA popsující iteraci - ergo výsledný jazyk je popsatelný konečným automatem - ergo jazyk je regulární.

Ve zkratce - třída REG je uzavřena vůči (nekompletní výčet) - sjednocení, průniku, doplňku, zřetězení, iteraci, či např. zrcadlení

Řetězec popisující celou množinu řetězců, konkrétně regulární jazyk.

Definice regexu:

1. abeceda Σ
2. ∅, ε, a (kde a ∈ Σ) jsou regulární výrazy
3. Jestliže α, β jsou regulární výrazy, pak i (α + β), (α · β), (α*) jsou regulární výrazy

U (α · β) se tečka většinou nepíše (konkatenace) a může se užít přímo αβ.

Jelikož regulární výraz i konečný automat oba popisují regulární jazyk, pak můžeme říci, že každý regulární výraz lze převést na konečný automat a naopak.

Popsáno výše v části 4 a 5 u IKT.

Bezkontextová gramatika je formálně čtveřice G = (Π, Σ, S, P)

• Π = množina neterminálů (A,B,C...)
• Σ = množina terminálů = samotné znaky (a,b,c,.../1,2,3,...)
• S = počáteční neterminál
• P = konečná množina přepisovacích pravidel

Bezkontextový jazyk = jazyk, akceptovaný tzv. zásobníkovým automatem. Jedná se o množinu jazyků jejíž podmnožinou jsou formální jazyky.

Bezkontextový jazyk je množina všech slov generovaná bezkontextovou gramatikou G.

Derivace = posloupnost odvození určitého slova v určité gramatice; rozlišujeme levou a pravou derivaci, dle směru nahrazování neterminálů

Derivační strom = grafická reprezentace derivace.

Ekvivalence gramatik = generují tentýž jazyk; Neexistuje slovo, které by bylo v jedné, ale ne v druhé; Algoritmicky nerozhodnutelné

Nejednoznačnost gramatiky = existují dva různé derivační stromy, jak získat určité slovo v dané gramatice.

Popsáno výše v části 6 - "Výpočetní složitost algoritmů, asymptotická notace"