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

• Wikipedie
• WolframMathWorld

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.

• [1]

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.

• [2]
• [3]
• [4]
• [5]

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.

• [6]
• [7]

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)