Okruhy otázek :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Požadavky znalostí ke státní závěrečné zkoušce

Platné od 20.9.2006

- Základy matematiky
- Základy informatiky - obor Obecná informatika
- Základy informatiky - obor Programování
- Základy informatiky - obor Správa počítačových systémů

### Základy matematiky

1. Čísla
  Vlastnosti přirozených, celých, racionálních, reálných a komplexních čísel. Posloupnosti a limity. Cauchyovské posloupnosti.
2. Základy diferenciálního počtu
  Reálné funkce jedné reálné proměnné. Spojitost, limita funkce v bodě (vlastní i nevlastní). Některé konkrétní funkce (polynomy, racionální lomené funkce, goniometrické a cyklometrické funkce, logaritmy a exponenciální funkce). Derivace: definice a základní pravidla, věty o střední hodnotě, derivace vyšších řádů. Některé aplikace (průběhy funkcí, Newtonova metoda hledání nulového bodu, Taylorův polynom se zbytkem).
3. Posloupnosti a řady funkcí
  Spojitost za předpokladu stejnoměrné konvergence. Mocninné řady. Taylorovy řady. Fourierovy řady.
4. Integrál
  Primitivní funkce, metody výpočtu. Určitý (Riemannův) integrál, užití určitého integrálu. Vícerozměrný integrál a Fubiniho věta.
5. Základy teorie funkcí více proměnných
  Parciální derivace a totální diferenciál, věty o střední hodnotě, extrémy funkcí více proměnných, věta o implicitních funkcích.
6. Metrické prostory
  Definice metrického prostoru, příklady. Spojitost a stejnoměrná spojitost. Kompaktní prostory a jejich vlastnosti, úplné prostory.
7. Diferenciální rovnice
  Soustavy lineárních diferenciálních rovnic prvního řádu resp. lineární rovnice n-tého řádu s konstantními koeficienty. Jejich řešení a speciální vlastnosti.
8. 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.
9. Vektorové prostory
  Základní vlastnosti vektorových prostorů, podprostory, generování, lineární závislost a nezávislost. Věta o výměně. Konečně generované vektorové prostory, base. Lineární zobrazení.
10. Skalární součin
  Vlastnosti v reálném i komplexním případě. Norma. Cauchy-Schwarzova nerovnost. Kolmost. Ortogonální doplněk a jeho vlastnosti.
11. Řešení soustav lineárních rovnic
  Lineární množiny ve vektorovém prostoru, jejich geometrická interpretace. Řešení soustavy rovnic je lineární množina. Frobeniova věta. Řešení soustavy úpravou matice. Souvislost soustavy řešení s ortogonálním doplňkem.
12. Matice
  Matice a jejich hodnost. Operace s maticemi a jejich vlastnosti. Inversní matice. Regulární matice, různé charakteristiky. Matice a lineární zobrazení, resp. změny souřadných soustav.
13. Determinanty
  Definice a základní vlastnosti determinantu. Úpravy determinantů, výpočet. Geometrický smysl determinantu. Minory a inversní matice. Cramerovo pravidlo.
14. Vlastní čísla a vlastní hodnoty
  Vlastní čísla a vlastní hodnoty lineárního operátoru resp. čtvercové matice. Jejich výpočet, základní vlastnosti. Uvedení matice na diagonální tvar v případě různých vlastních čísel. Informace o Jordanově tvaru v obecném případě.
15. Základy lineárního programování
  Simplexová metoda. Věty o dualitě (bez důkazu).
16. Diskrétní matematika
  Uspořádané množiny. Množinové systémy, párování, párování v bipartitních grafech (systémy různých reprezentantů). Kombinatorické počítání. Princip inkluze a exkluze. Latinské čtverce a projektivní roviny.
17. Teorie grafů
  Základní pojmy teorie grafů, reprezentace grafu. Stromy a jejich základní vlastnosti, kostra grafu. Eulerovské a hamiltonovské grafy. Rovinné grafy, barvení grafů.

### Základy informatiky - obor Obecná informatika

1. 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.
2. Automaty a jazyky
  Chomského hierarchie, třídy automatů a gramatik, determinismus a nedeterminismus. Uzávěrové vlastnosti tříd jazyků.
3. Algoritmy a datové struktury
  Časová složitost algoritmů, složitost v nejhorším a průměrném případě. Třídy složitosti P a NP, převoditelnost, NP-úplnost. Metoda ,,rozděl a panuj'' - aplikace a analýza složitosti. Binární vyhledávací stromy, vyvažování, haldy. Hašování. Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě. Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu, toky v sítích. Tranzitivní uzávěr. Algoritmy vyhledávání v textu. Algebraické algoritmy - DFT, Euklidův algoritmus. Základy kryptografie, RSA, DES. Pravděpodobnostní algoritmy - testování prvočíselnosti. Aproximační algoritmy.
4. Databáze
  Podstata a architektury DB systémů. Konceptuální, logická a fyzická úroveň pohledů na data. Relační datový model, relační algebra. Algoritmy návrhu schémat relací, normální formy, referenční integrita. Základy SQL. Transakční zpracování, vlastnosti transakcí. Organizace dat na vnější paměti, B-stromy a jejich varianty.
5. Architektury počítačů a sítí
  Architektury počítače. Procesory, multiprocesory. Vstupní a výstupní zařízení, ukládání a přenos dat. Architektury OS. Procesy, vlákna, plánování. Synchronizační primitiva, vzájemné vyloučení. Zablokování a zotavení z něj. Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování. Systémy souborů, adresářové struktury. Bezpečnost, autentifikace, autorizace, přístupová práva. ISO/OSI vrstevnatá architektura sítí. TCP/IP. Spojované a nespojované služby, spolehlivost, zabezpečení protokolů.
6. Programovací jazyky
  Principy implementace procedurálních programovacích jazyků, oddělený překlad, sestavení. Objektově orientované programování. Neprocedurální programování, logické programování. Generické programování.

### Základy informatiky - obor Programování

1. Základy teoretické informatiky
  Logika – jazyk, formule, sémantika, tautologie. Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost. Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky. Automaty – Chomského hierarchie, třídy automatů a gramatik, determinismus a nedeterminismus.
2. Algoritmy a datové struktury
  Časová složitost algoritmů, složitost v nejhorším a průměrném případě. Třídy složitosti P a NP, převoditelnost, NP-úplnost. Binární vyhledávací stromy, vyvažování, haldy. Hašování. Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě. Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu. Tranzitivní uzávěr. Algoritmy vyhledávání v textu. Algebraické algoritmy - DFT, Euklidův algoritmus. Základy kryptografie, RSA, DES.
3. Databáze
  Podstata a architektury DB systémů. Konceptuální, logická a fyzická úroveň pohledů na data. Algoritmy návrhu schémat relací, normální formy, referenční integrita. Transakční zpracování, vlastnosti transakcí, uzamykací protokoly, zablokování. ER-diagramy, metody návrhů IS. SQL. Indexy, triggery, uložené procedury, uživatelé, uživatelská práva. Vícevrstevné architektury. Vazba databází na internetové technologie. Organizace dat na vnější paměti, B-stromy a jejich varianty.
4. Programovací jazyky a překladače
  Principy a základy implementace objektově orientovaných jazyků a jazyků s blokovou strukturou, běhová podpora vyšších programovacích jazyků. Oddělený překlad, sestavení, řízení překladu. Neprocedurální programování. Struktura překladače, lexikální, syntaktická analýza. Interpretované jazyky, virtuální stroje. Pojmy a principy objektového návrhu. Generické programování a knihovny. Návrhové vzory.
5. Architektura počítačů a operačních systémů
  Architektury počítače. Procesory, multiprocesory. Sběrnice, protokoly. Vstupní a výstupní zařízení. Architektury OS. Vztah OS a HW, obsluha přerušení. Procesy, vlákna, plánování. Synchronizační primitiva, vzájemné vyloučení. Zablokování a zotavení z něj. Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace. Systémy souborů, adresářové struktury. Bezpečnost, autentifikace, autorizace, přístupová práva. Druhy útoků a obrana proti nim. Kryptografické algoritmy a protokoly.
6. Sítě a internetové technologie
  Architektura ISO/OSI. Rodina protokolu TCP/IP (ARP, IPv4, IPv6, ICMP, UDP, TCP) - adresace, routing, fragmentace, spolehlivost, flow control, congestion control, NAT. Rozhraní BSD sockets. Spolehlivost - spojované a nespojované protokoly, typy, detekce a oprava chyb. Bezpečnost - IPSec, principy fungování AH, ESP, transport mode, tunnel mode, firewalls. Internetové a intranetové protokoly a technologie - DNS, SMTP, FTP, HTTP, NFS, HTML, XML, XSLT a jejich použití.

### Základy informatiky - obor Správa počítačových systémů

1. Základy teoretické informatiky
  Logika – jazyk, formule, sémantika, tautologie. Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost. Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky. Automaty – Chomského hierarchie, třídy automatů a gramatik, determinismus a nedeterminismus.
2. Algoritmy a datové struktury
  Časová složitost algoritmů, složitost v nejhorším a průměrném případě. Třídy složitosti P a NP, převoditelnost, NP-úplnost. Binární vyhledávací stromy, vyvažování, haldy. Hašování. Sekvenční třídění, porovnávací algoritmy. Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu. Tranzitivní uzávěr. Algoritmy vyhledávání v textu. Algebraické algoritmy - DFT, Euklidův algoritmus. Základy kryptografie, RSA, DES.
3. Databáze
  Podstata a architektury DB systémů. Normální formy. Referenční integrita. Transakční zpracování, vlastnosti transakcí, uzamykací protokoly, zablokování. Základy SQL. Indexy, triggery, uložené procedury, uživatelé, uživatelská práva. Vícevrstevné architektury. Vazba databází na internetové technologie. Správa databázových systémů.
4. Architektura počítačů a operačních systémů
  Architektury počítače. Procesory, multiprocesory. Sběrnice, protokoly. Vstupní a výstupní zařízení, přenos dat. Technologie dálkového přenosu dat. Velkokapacitní záznamová média, zálohování, technologie ukládání a zabezpečení záznamů. Architektury OS. Vztah OS a HW, obsluha přerušení. Procesy, vlákna, plánování. Synchronizační primitiva, vzájemné vyloučení. Zablokování a zotavení z něj. Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace. Systémy souborů, adresářové struktury. Bezpečnost, autentifikace, autorizace, přístupová práva. Druhy útoků a obrana proti nim. Kryptografické algoritmy a protokoly.
5. Sítě a internetové technologie
  Architektura ISO/OSI. Rodina protokolu TCP/IP (ARP, IPv4, IPv6, ICMP, UDP, TCP) - adresace, routing, fragmentace, spolehlivost, flow control, congestion control, NAT. Rozhraní BSD sockets. Spolehlivost - spojované a nespojované protokoly, typy, detekce a oprava chyb. Bezpečnost - IPSec, principy fungování AH, ESP, transport mode, tunnel mode, firewalls. Internetové a intranetové protokoly a technologie - DNS, SMTP, FTP, HTTP, NFS, HTML, XML, XSLT a jejich použití.
6. Administrace systémů
  Instalace systému, plánování síťové topologie, rozklad zátěže . Zabezpečení, systém práv, správa uživatelských účtů. Síťové, systémové a adresářové služby, vzdálený přístup. Zálohování, automatizace úkolů, synchronizace, zotavení systému. Konkrétní souborové systémy. Instalace software, hromadná, vzdálená a odložená instalace. Činnost systému při spouštění a ukončování, konfigurace. Skriptování a shelly. (Student si zvolí konkrétní platformu, buď Windows nebo Unix.)