slama.dev

Příprava na státnice (MFF UK)

vydáno 15. 4. 2022

Tento článek obsahuje mou přípravu na státní zkoušky z Obecné informatiky pro akademický rok 2021/2022 (tj. nová akreditace). Podrobné informace o všech specializacích jsou k dispozici v tomto PDF (informace na této stránce jsou z 1.6.2022 updatu tohoto dokumentu).

U každé časti tématu je jeden nebo více odkazů (🔗) na zdroje, ze kterých je možné se téma učit. U celých předmětů jsou vždy odkazy na zdroje (ať už se jedná poznámky, slidy či skripta). Pokud je u předmětu symbol kartičky (🃏), tak je zahrnut v tomto Anki balíčku, ze kterého může být dobré si celý předmět zopakovat.

Obecná

Matematika

      • odmocnina ze dvou je iracionální
      • R\mathbb{R} je nespočetná množina
      • Posloupnosti reálných čísel a jejich limity
      • 🔗 🔗
      • definice, aritmetika limit
      • věta o dvou policajtech, limity a uspořádání
      • definice částečného součtu a součtu
      • geometrická řada, harmonická řada
      • Reálné funkce jedné reálné proměnné.
      • 🔗
        • definice, aritmetika limit
        • vztah s uspořádáním
        • limita složené funkce
        • funkce spojité na intervalu
        • 🔗
        • nabývání mezihodnot
        • nabývání maxima
      • definice a základní pravidla pro výpočet
      • l’Hospitalovo pravidlo
      • vyšetření průběhu funkcí: extrémy, monotonie a konvexita/konkavita
      • Integrály a jejich aplikace
      • 🔗
      • primitivní funkce: definice a metody výpočtu (substituce, per-partes)
      • Riemannův integrál: definice, souvislost s primitivní funkcí (Newtonovým integrálem)
      • aplikace
        • odhady součtu řad (konečných i nekonečných)
        • obsahy rovinných útvarů
        • objemy a povrchy rotačních útvarů v prostoru
        • délka křivky
    • Algebra a lineární algebra
    • Lingebra 1 a 2 [skripta] 🃏
      • Grupy a podgrupy (definice, příklady, komutativita)
      • 🔗
      • Tělesa (definice, charakteristika tělesa, konečná tělesa)
      • 🔗
      • Vektorové prostory a podprostory.
      • 🔗
      • vlastnosti a základní pojmy (lineární kombinace, lineární obal, generátory, lineární závislost a nezávislost, báze, dimenze, souřadnice) a jejich použití
      • praktická dovednost testování lineární závislosti a nezávislosti, nalezení báze, určení dimenze atp.
      • skalární součin a jeho vlastnosti
      • norma a vztah se skalárním součinem, příklady
      • kolmost, ortonormální báze, její vlastnosti a použití (nalezení souřadnic a projekce)
      • Skalární součin, norma.
      • 🔗
      • Soustavy lineárních rovnic a množina řešení.
      • 🔗
      • metody řešení, Gaussova a Gaussova-Jordanova eliminace, odstupňovaný tvar matice a jeho jednoznačnost (bez důkazu)
      • Matice a operace s maticemi (součet, součin, transpozice)
      • 🔗 🔗 🔗
      • interpretace součinu matic pomocí skládání lineárních zobrazení
      • hodnost matice a její transpozice
        • vlastní čísla a vlastní vektory matice a jejich geometrický význam a vlastnosti, vícenásobná vlastní čísla, spektrální poloměr
        • 🔗
        • charakteristický polynom, vztah vlastních čísel s kořeny polynomů
        • 🔗
      • vlastnosti binárních relací (reflexivita, symetrie, antisymetrie, tranzitivita)
      • Ekvivalence a rozkladové třídy.
      • 🔗
      • Částečná uspořádání.
      • 🔗
      • základní pojmy
        • výška a šířka částečně uspořádané množiny, věta o dlouhém a širokém
        • 🔗
      • typy funkcí (prostá, na, bijekce)
      • počty různých typů funkcí mezi dvěma konečnými množinami
      • Permutace a jejich základní vlastnosti (počet a pevný bod).
      • 🔗
      • Kombinační čísla a vztahy mezi nimi, binomická věta a její aplikace.
      • 🔗
      • Princip inkluze a exkluze.
      • 🔗
      • obecná formulace (a důkaz)
      • použití (problém šatnářky, Eulerova funkce pro počet dělitelů, počet surjekcí)
      • Hallova věta o systému různých reprezentantů, vztah k párování v bipartitním grafu.
      • 🔗
      • princip důkazu a algoritmické aspekty (polynomiální algoritmus pro nalezení SRR)
      • Základní pojmy, základní příklady grafů.
      • 🔗
      • Souvislost grafů, komponenty souvislosti, vzdálenost v grafu.
      • 🔗
      • definice a základní vlastnosti (existence listů, počet hran stromu)
      • ekvivalentní charakteristiky stromů
      • definice a základní pojmy (rovinný graf a rovinné nakreslení grafu, stěny)
      • Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití)
      • definice dobrého obarvení
      • vztah barevnosti a klikovosti grafu
      • Hranová a vrcholová souvislost grafů, Mengerovy věty.
      • 🔗
      • Orientované grafy, silná a slabá souvislost.
      • 🔗
      • definice sítě a toku v ní
      • existence maximálního toku (bez důkazu)
      • princip hledání maximálního toku v síti s celočíselnými kapacitami (například pomocí Ford-Fulkersonova algoritmu)
    • Pravděpodobnostní prostor, náhodné jevy, pravděpodobnost
      • definice těchto pojmů, příklady
      • základní pravidla pro počítání s pravděpodobností
      • nezávislost náhodných jevů, podmíněná pravděpodobnost
      • Bayesův vzorec
    • Náhodné veličiny a jejich rozdělení
      • diskrétní i spojitý případ
      • popis pomocí distribuční funkce a pomocí pravděpodobnostní funkce/hustoty
      • střední hodnota
        • linearita střední hodnoty
        • střední hodnota součinu nezávislých veličin
        • Markovova nerovnost
      • rozptyl
        • definice
        • vzorec pro rozptyl součtu (závislých či nezávislých veličin)
      • práce s konkrétními rozděleními: geometrické, binomické, Poissonovo, normální, exponenciální
    • Limitní věty
      • zákon velkých čísel
      • centrální limitní věta
    • Bodové odhady
      • alespoň jedna metoda pro jejich tvorbu
      • vlastnosti
    • Intervalové odhady: metoda založená na aproximaci normálním rozdělením
    • Testování hypotéz
      • základní přístup
      • chyby 1. a 2. druhu
      • hladina významnosti
    • Syntaxe
      • znalost a práce se základními pojmy syntaxe výrokové a predikátové logiky (jazyk, otevřená a uzavřená formule, instance formule, apod.)
      • normální tvary výrokových formulí
        • prenexní tvary formulí predikátové logiky
        • znalost základních normálních tvarů (CNF, DNF, PNF)
        • převody na normální tvary
        • použití pro algoritmy (SAT, rezoluce)
    • Sémantika
      • pojem modelu teorie
      • pravdivost, lživost, nezávislost formule vzhledem k teorii
      • splnitelnost, tautologie, důsledek
      • analýza výrokových teorií nad konečně mnoha prvovýroky
    • Extenze teorií
      • schopnost porovnat sílu teorií
      • konzervativnost, skolemizace
    • Dokazatelnost:
      • pojem formálního důkazu, zamítnutí
      • schopnost práce v některém z formálních dokazovacích systémů (např. tablo metoda, rezoluce, Hilbertovský kalkul)
      • Věty o kompaktnosti a úplnosti výrokové a predikátové logiky
      • 🔗 🔗 🔗
      • znění a porozumění významu
      • použití na příkladech, důsledky
      • pojem kompletnosti a její kritéria, význam pro rozhodnutelnost
      • příklady rozhodnutelných a nerozhodnutelných teorií

Informatika

    • Regulární jazyky.
      • regulární gramatiky
      • konečný automat, jazyk přijímaný konečným automatem
      • deterministický a nedeterministický automat, lambda přechody
      • regulární výrazy
      • Kleeneho věta
      • iterační (pumping) lemma pro konečné automaty
    • Uzávěrové vlastnosti
    • Bezkontextové jazyky.
      • bezkontextové gramatiky, jazyk generovaný gramatikou
      • zásobníkový automat, třída jazyků přijímaných zásobníkovými automaty
    • Turingův stroj.
      • gramatika typu 0
      • diagonální jazyk
      • univerzální jazyk
    • Chomského hierarchie.
      • určení ekvivalence či inkluze tříd jazyků generovaných výše uvedenými automaty a gramatikami
      • schopnost zařazení konkrétního jazyka do Chomského hierarchie (zpravidla sestrojení odpovídajícího automatu či gramatiky a důkaz iteračním lemmatem, že jazyk není v nižší třídě)
    • Algoritmy a datové stuktury
    • ADS 1 a 2 [Průvodce, GA] 🃏
      • Časová a prostorová složitost algoritmů.
      • 🔗
      • čas a prostor výpočtu pro konkrétní vstup
      • časová a prostorová složitost algoritmu
      • měření velikosti dat
      • složitost v nejlepším, nejhorším a průměrném případě
      • asymptotická notace
      • třídy P a NP
      • převoditelnost problémů, NP-těžkost a NP-úplnost
      • příklady NP-úplných problémů a převodů mezi nimi
      • Metoda "rozděl a panuj".
      • 🔗
      • princip rekurzivního dělení problému na podproblémy
      • výpočet složitosti pomocí rekurentních rovnic
      • Master theorem (kuchařková věta)
      • aplikace
        • Mergesort
        • násobení dlouhých čísel
        • Strassenův algoritmus
      • Binarní vyhledávací stromy.
      • 🔗
      • definice vyhledávacího stromu
      • operace s nevyvažovanými stromy
      • AVL stromy (definice)
      • Hešování s přihrádkami a s otevřenou adresací.
      • 🔗
      • Třídící algoritmy.
      • 🔗
      • primitivní třídicí algoritmy (Bubblesort, Insertsort)
      • třídění haldou (Heapsort)
      • Quicksort
      • dolní odhad složitosti porovnávacích třídicích algoritmů
      • přihrádkové třídění čísel a řetězců
        • Nejkratší cesty (Dijkstra, BF).
        • 🔗
        • Minimální kostry (Jarník, Borůvka).
        • 🔗
      • Euklidův algoritmus.
      • 🔗
    • Koncepty pro abstrakci, zapouzdření a polymorfismus.
      • související konstrukty programovacích jazyků
        • třídy, rozhraní, metody, datové položky, dědičnost, viditelnost
      • (dynamický) polymorfismus, statické a dynamické typování
      • jednoduchá dědičnost
        • virtuální a nevirtuální metody v C++ a C#
        • defaultní metody v Javě
      • vícenásobná dědičnost a její problémy
        • vícenásobná a virtuální dědičnost v C++
        • interfaces v Javě a C++
      • implementace rozhraní (interface)
    • Primitivní a objektové typy a jejich reprezentace.
      • číselné a výčtové typy
      • ukazatele a reference v C++
      • hodnotové a referenční typy v C#
      • imutabilní typy a boxing/unboxing v C# a Javě
    • Generické typy a funkcionální prvky (procedurálních programovacích jazyků).
      • šablony (templates) a statický polymorfismus v C++
      • generické typy v Javě a C# (bez omezení typových parametrů)
      • typy reprezentující funkce v C++, C#, nebo Javě
      • lambda funkce a funkcionální rozhraní
    • Manipulace se zdroji a mechanizmy pro ošetření chyb.
      • správa životního cyklu zdrojů v případě výskytu chyb
        • RAII v C++, using v C#, try-with-resources v Javě
      • konstrukce pro obsluhu a propagaci výjimek
    • Životní cyklus objektů a správa paměti.
      • alokace (alokace statická, na zásobníku, na haldě)
      • inicializace (konstruktory, volání zděděných konstruktorů)
      • destrukce (destruktory, finalizátory)
      • explicitní uvolňování objektů, reference counting, garbage collector
    • Vlákna a podpora synchronizace.
      • reprezentace vláken v programovacích jazycích
      • specifikace funkce vykonávané vláknem a základní operace na vlákny
      • časově závislé chyby a mechanizmy pro synchronizaci vláken
    • Implementace základních prvků objektových jazyků.
      • základní objektové koncepty v konkrétním jazyce (Java, C++, C#)
      • implementace a interní reprezentace primitivních typů
      • implementace a interní reprezentace složených typů a objektů
      • implementace dynamického polymorfismu (tabulka virtuálních metod)
    • Nativní a interpretovaný běh, řízení překladu a sestavení programu.
      • reprezentace programu, bytecode, interpret jazyka
      • just-in-time (JIT) a ahead-of-time (AOT) překlad
      • proces sestavení programu, oddělený překlad, linkování
      • staticky a dynamicky linkované knihovny
      • běhové prostředí procesu a vazba na operační systém
    • Architektura počítačů a OS
    • Principy poč. [poznámky] 🃏, Poč. systémy [slidy]
      • reprezentace a přístup k datům v paměti, adresa, adresový prostor
      • ukládání jednoduchých a složených datových typů
      • základní aritmetické a logické operace
      • Instrukční sada, vazba na vyšší programovací jazyky.
      • 🔗
      • Implementovat běžné programové konstrukce vyšších jazyků (přiřazení, podmínka, cyklus, volání funkce) pomocí instrukcí procesoru
      • Zapsat běžnou konstrukci vyššího jazyka (přiřazení, podmínka, cyklus, volání funkce), která odpovídá zadané sekvenci (vysvětlených) instrukcí procesoru
      • Podpora pro běh operačního systému.
      • 🔗
      • privilegovaný a neprivilegovaný režim procesoru
      • jádro operačního systému
      • Rozhraní periferních zařízení a jejich obsluha.
      • 🔗 🔗
      • Popsat roli řadiče zařízení při programem řízené obsluze zařízení (PIO), pro zadané adresy a funkce vstupních a výstupních portů implementovat programem řízenou obsluhu zadaného zařízení (myš, disk)
      • Popsat roli přerušení při programem řízené obsluze zařízení (PIO), na úrovni vykonávání instrukcí popsat reakci procesoru (hardware) a operačního systému (software) na žádost o přerušení
      • Základní abstrakce, rozhraní a mechanizmy OS pro běh programů, sdílení prostředků a vstup/výstup.
      • 🔗
      • neprivilegované (uživatelské) procesy
      • sdílení procesoru
        • procesy, vlákna, kontext procesu a vlákna
        • přepínání kontextu, kooperativní a preemptivní multitasking
        • plánování běhu procesů a vláken, stavy vlákna
      • sdílení paměti
        • Vysvětlit rozdíl mezi virtuální a fyzickou adresou a identifikovat, zda se v zadaném kontextu či fragmentu kódu používá virtuální nebo fyzická adresa
        • Na zadaném příkladu identifikovat a vysvětlit význam komponent virtuální a fyzické adresy (číslo stránky, číslo rámce, offset)
        • Pro konkrétní adresy a obsah jednoúrovňové stránkovací tabulky řešit úlohy překladu adres
        • Vysvětlit roli virtuálních adresových prostorů v ochraně paměti procesů a vláken
      • sdílení úložného prostoru
        • soubory, analogie s adresovým prostorem
        • abstrakce a rozhraní pro práci se soubory
      • Paralelismus, vlákna a rozhraní pro jejich správu, synchronizace vláken.
      • 🔗
      • časově závislé chyby (race conditions)
      • kritická sekce, vzájemné vyloučení
      • základní sychronizační primitiva, jejich rozhraní a použití
        • zámky
        • aktivní a pasivní čekání

Specifická

Z následujících témat je třeba umět všechna z 1-3 a dvě z 4-7 (vybírá se v SISu).

      • Vytvořující funkce.
      • 🔗
      • použití vytvořujících funkcí k řešení lineárních rekurencí
      • zobecněná binomická věta (formulace)
      • Catalanova čísla (příklad kombinatorické interpretace, odvození vzorce)
      • Odhady faktoriálů a kombinačních čísel.
      • 🔗 🔗
      • (n/e)nn!n(n/e)n(n/e)^n \le n! \le n(n/e)^n
      • (n/k)k(nk)(en/k)k(n/k)^k \le \binom{n}{k} \le (en/k)^k
      • 22m/(2m)(2mm)22m/2m2^{2m}/(2 \sqrt{m}) \le \binom{2m}{m} \le 2^{2m} / \sqrt{2m}
      • Ramseyova věta (formulace konečné a nekonečné verze pro p-tice, důkaz verze p=2p=2 pro 2 barvy)
      • Ramseyova čísla (definice, pro 2 barvy horní odhad z důkazu Ramseyovy věty a dolní odhad pravděpodobnostní konstrukcí)
      • Extremální kombinatorika
      • 🔗
      • obecné povědomí co extremální kombinatorika studuje
      • Turánova věta (formulace, Turánovy grafy)
      • Erdös-Ko-Radoova věta (formulace)
      • Samoopravné kódy.
      • 🔗
      • přehled o používané terminologii
      • vzdálenost kódu a její vztah k počtu opravitelných a detekovatelných chyb
      • Hammingův odhad (formulace a důkaz)
      • perfektní kódy (definice a příklady, Hammingův kód bez přesné konstrukce)
    • Základy sítí
    • Sítě [slidy] 🃏
    • Taxonomie počítačových sítí.
    • Architektura ISO/OSI.
    • Přehled síťového modelu TCP/IP.
    • Směrování.
    • Koncept adresy, portu, socketu.
    • Architektura klient/server.
    • Základy fungování protokolů HTTP, FTP a SMTP.
    • Riemannův integrál jedno- i vícerozměrný
    • Funkce více proměnných
      • parciální derivace: definice a výpočet
      • výpočet extrémů pomocí paricálních derivací
      • existence extrémů pro funkce několika reálných proměnných
      • vázané extrémy: výpočet pomocí Lagrangeových multiplikátorů
    • Metrický prostor
      • definice a základní příklady
      • otevřené a uzavřené množiny: definice, příklady
      • spojitost funkce na metrickém prostoru
      • kompaktnost: definice a důsledky pro extrémy funkcí více proměnných
      • stejnoměrná spojitost
    • Základy lineárního a celočíselného programování.
      • dualita lineárního programování, Farkasovo lemma
        • simplexová metoda, pivotovací pravidla
        • 🔗
    • Kombinatorická geometrie
      • konvexní obal objektů
      • mnohostěny
      • Minkowski-Weylova věta
    • Základy matematického programování
      • unimodularita, Königovo lemma, toky v sítích, souvislost s dualitou LP
      • vážené maximální párování v bipartitních grafech a jeho primárně-duální algoritmus
    • Celočíselné programování.
      • řádová funkce, existence a submodularita
      • hladový algoritmus
      • Aproximační algoritmy pro kombinatorické problémy:
      • 🔗
      • definice: aproximační poměr, aproximační schéma
        • nezávislé množiny
        • 🔗
        • množinové pokrytí
        • 🔗
    • Použití lineárního programování pro aproximační algoritmy.
        • algoritmy pro splnitelnost (MAXSAT, pravděpodobnostní zaokrouhlování)
        • 🔗
        • vrcholové a množinové pokrytí (deterministické zaokrouhlování, primárně-duální algoritmus)
        • 🔗
    • Využití pravděpodobnosti při návrhu algoritmů.
        • minimální globální řez v grafu
        • 🔗
        • hashování a jeho využítí pro slovník s konstantním časem vyhledávání
        • 🔗
        • pravděpodobnostní testování maticových a polynomiálních identit
        • 🔗
        • paralelní algoritmus pro hledání maximální nezávislé množiny
        • 🔗
        • paralelní algoritmy pro hledání párování (bipartitní grafy)
        • 🔗
      • Dynamické programování.
      • 🔗
      • princip dynamického programování (řešení podproblémů od nejmenších k největším)
        • aplikace: nejdelší rostoucí podposloupnost, editační vzdálenost
        • 🔗 🔗
      • Výpočetní model RAM.
      • 🔗
      • Komponenty silné souvislosti orientovaných grafů.
      • 🔗
      • tranzitivní uzávěr (Floyd-Warshal)
      • komponenty silné souvislosti orientovaných grafů
      • toky v sítích (Dinicův a Goldbergův algoritmus)
      • Toky v sítích (FF, Diniz, Goldberg).
      • 🔗 🔗
      • algoritmy Knuth-Morris-Pratt a Aho-Corasicková
      • Diskrétní Fourierova transformace, aplikace.
      • 🔗 🔗
      • diskrétní Fourierova transformace a její aplikace
      • výpočet Fourierovy transformace algoritmem FFT
      • RSA (šifrování, dešifrování a generování klíčů)
      • 🔗
      • Aproximační algoritmy a schémata (cestující, batoh).
      • 🔗 🔗
      • poměrová a relativní chyba
      • aproximační schémata
      • příklady: obchodní cestující, batoh
      • Paralelní třidění pomocí komparátorových sítí.
      • 🔗
    • Červeno-černé stromy a jejich vyvažování

    • ❌ Geometrie ❌
    • Základy KVG
    • Základní věty o konvexních množinách (Hellyho, Radonova, o oddělování).
    • Minkowského věta o mřížkách.
    • Konvexní mnohostěny (zákadní vlastnosti, V-mnohostěny, H-mnohostěny, kombinatorická složitost).
    • Geometrická dualita.
    • Voroného diagramy, arrangementy (komplexy) nadrovin, incidence bodů a přímek, základní algoritmy výpočetní geometrie (konstrukce arrangementu přímek v rovině, konstrukce konvexního obalu v rovině).
    • ❌ Pokročilá diskrétní matematika ❌
    • Kombagra 2, Teorie množin
    • Barvení grafů (Brooksova a Vizingova věta).
    • Tutteova věta.
    • Extremální kombinatorika (Turánova věta, Erdös-Ko-Radoova věta).
    • Kreslení grafů na plochách.
    • Množiny a zobrazení.
    • Subvalence a ekvivalence množin.
    • Dobré uspořádání.
    • Axiom výběru (Zermelova věta, Zornovo lemma).

Poděkování