Informatická souborka
Stará (a čo sa týka informatickej časti nedostatočná) verzia je na http://artax.karlin.mff.cuni.cz/souborky/
Pokúsim sa sem časom naimportovať TeXové zdrojáky, aby šli doplňovať online. (miEro)
Jinak dore zdoje jsou
Obsah
Matematika
Teorie množin
Základní množinové pojmy, axiomy teorie množin. Přirozená čísla a konečné množiny. Subvalence a ekvivalence množin. Spočetné množiny a množiny mohutnosti kontinua. Uspořádání a jeho různé druhy. Dobrá uspořádání, ordinální čísla. Transfinitní indukce. Formulace axiomu výběru.
Teorie grafů
Základní pojmy, reprezentace grafu. Stromy a jejich základní vlastnosti, kostra grafu. Eulerovské a hamiltonovské grafy. Rovinné grafy, barvení grafů. Základní grafové algoritmy.
Vektorové, normované a metrické prostory
Vektorové prostory, prostory se skalárním součinem, normované a metrické prostory – základní pojmy a vlastnosti, příklady, lineární zobrazení. Hilbertův prostor. Pojem úplného a kompaktního prostoru. Věty o pevném bodě, aplikace.
Matice a lineární soustavy
Základy teorie matic, vlastní čísla, vlastní vektory – základní pojmy, vlastnosti. Jordanův tvar matice. Speciální typy matic – symetrické, samoadjungované, unitární, ortogonální. Numerické metody řešení soustav lineárních algebraických rovnic, aproximace vlastních čísel a vlastních vektorů.
Algebraické struktury, polynomická algebra
Grupa, okruh, těleso – definice a příklady. Podgrupa, normální podgrupa, faktorgrupa, ideál. Homomorfismy grup. Dělitelnost a ireducibilní rozklady polynomů. Rozklady polynomů na kořenové činitele pro polynom s reálnými, racionálními, komplexními koeficienty. Násobnost kořenů a jejich souvislost s derivacemi mnohočlenu.
Posloupnosti a řady čísel a funkcí
Limity posloupností a součty řad. Kriteria absolutní a neabsolutní konvergence číselných řad. Stejnoměrná konvergence posloupností a řad funkcí. Mocninné řady. Fourierovy řady. Ortogonální (Fourierovy) řady v Hilbertově prostoru.
Diferenciální a integrální počet
Věta o střední hodnotě a důsledky. Taylorův rozvoj. Určitý a neurčitý integrál, metody výpočtu. Diferenciál funkce více proměnných, skládání diferenciálů, záměnnost parciálních derivací. Věta o implicitních funkcích. Volné a vázané extrémy funkcí více proměnných a jejich výpočet. Základní věty integrálního počtu – o limitním přechodu, o substituci, Fubiniova, derivování integrálu podle parametru.
Obyčejné diferenciální rovnice
Věty o existenci a jednoznačnosti počáteční úlohy pro systémy lineárních a nelineárních rovnic. Vlastnosti řešení. Analytické a numerické metody řešení. Systémy lineárních diferenciálních rovnic 1. řádu s konstantními koeficienty.
Informatika
Počítače a operační systémy
Architektury počítačů. Architektury a funkční jednotky procesorů, typy instrukcí, adresování. Vstupní a výstupní zařízení, komunikace s procesorem, přerušení, DMA. Struktura operačních systémů - monolitické, mikrojádro, virtuální stroje. Správa procesů a vláken, plánování. Meziprocesová komunikace, kritické sekce, vyloučení, synchronizační primitiva, klasické synchronizační problémy. Správa prostředků, zablokování a možnosti jeho řešení, Coffmanovy podmínky, bankéřův algoritmus. Organizace paměti, přidělovací strategie. Virtuální paměť, stránkování a segmentace. Implementace stránkování, stránkovací tabulky, ošetření výpadků, algoritmy výměny stránek, asociativní paměť. Souborové systémy, adresáře, správa volného prostoru, alokační metody. Algoritmy přístupu na disk.
Programovací jazyky
Neprocedurální, procedurální a objektové programovací jazyky. Datové a řídicí struktury vyšších programovacích jazyků a jejich implementace – volání procedur a funkcí, předávání parametrů a návratových hodnot, přístup ke globálním a dynamickým proměnným. Rozdělení paměti v jazycích s blokovou strukturou. Principy objektově orientovaného programování a jejich implementace - třídy a objekty, virtuální metody, dědičnost, polymorfismus.
Překladače
Struktura kompilátoru, fáze překladu, front-end a back-end. Lexikální, syntaktická a sémantická analýza. Konstrukce SLR(1) automatu, operátory First a Follow, funkce SLR(1) parseru. Překlad do vnitřní formy, optimalizace nad vnitřní formou, generování kódu. Druhy chyb při překladu a zotavení z nich.
Databázové systémy
Základní organizace souborů na vnější paměti. Architektury databázového systému. Databázové modely – relační, objektový, objektově-relační. Konceptuální modelování – E-R modely. Pojem dotazu, dotazovacího jazyka. Relační kalkul a algebra. Základy SQL. Metody návrhu relací. Transakce a jejich vlastnosti, paralelní zpracování transakcí, sériové rozvrhy, dvoufázový uzamykací protokol. Zotavení z chyb, žurnály.
Výroková a predikátová logika
Jazyk, formule, sémantika, tautologie. Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost. Věty o kompaktnosti a úplnosti výrokové a predikátové logiky. Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky.
Automaty a jazyky
Chomského hierarchie, charakterizace jednotlivých tříd jazyků prostředky gramatik a automatů, (ne-)determinismus. Uzávěrové vlastnosti. Nerozhodnutelné problémy teorie jazyků.
Algoritmy a jejich složitost
Metody návrhu algoritmů, základní algoritmy (třídění, vyhledávání, kombinatorické). Složitost algoritmů, metoda "rozděl a panuj", dynamické programování. Základní grafové algoritmy (nejkratší cesta, minimální kostra, prohledávání). Amortizovaná složitost. Stromové datové struktury, Fibonacciho haldy. NP-úplnost, příklady NP-úplných úloh.
Lineární programování
Lineární programování, simplexová metoda.
- popsáno např. zde (nějaká diplomka)
