Otázky IO

Teoretické základy informatiky

1. Množiny a relace (zobrazení, funkce, rozklady a ekvivalence)
2. Elementární kombinatorika (variace, kombinace a permutace)
3. Uspořádání (relace uspořádání, uspořádané množiny a svazy, číselné obory)
4. Výroková logika (syntax, sémantika, odvozovací systém výrokové logiky, důkazy ve výrokové logice, pravdivost a dokazatelnost logických formulí, rezoluce)
5. Predikátová logika prvního řádu (syntax, sémantika, prenexace, skolemizace, unifikace, rezoluce)
6. Prolog (SLD-rezoluce, SLD-stromy, výpočetní mechanismus Prologu, základy programování v Prologu)
7. Důkazy programů (dokazování vlastností programů, induktivní metody, invarianty cyklů)
8. Rekurze (rekurzivní definice funkcí, funkce vyššího řádu, částečná aplikace, curryifikace, definice funkcí rekurzivně a pomocí kombinátorů, definice vyšších funkcí bez použití formálních parametrů)
9. Vyhodnocování výrazů (pořadí vyhodnocování, striktní a normální redukce, líná redukce, efektivita nekonečné datové struktury, definice funkcí nad nekonečnými strukturami)
10. Regulární jazyky (regulární jazyky, způsoby jejich reprezentace, vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami)
11. Konečné automaty (definice, konstrukce konečného automatu, minimalizace konečného automatu, převod nedeterministického konečného automatu na deterministický automat)
12. Bezkontextové jazyky (definice, vlastnosti, způsoby jejich reprezentace, konstrukce bezkontextové gramatiky a zásobníkového automatu, normální formy bezkontextových gramatik, použití lematu o vkládání pro bezkontextové jazyky, uzávěrové vlastností bezkontextových jazyků)
13. Zásobníkové automaty (definice, převod bezkontextové gramatiky na zásobníkový automat). Syntaktická analýza (syntaktická analýza shora dolů a zdola nahoru, průběh analýzy daného slova).
14. Datové struktury a jejich implementace (seznam, zásobník, fronta, binární strom, obecný strom, vyhledávací stromy a jejich modifikace. Implementace binárních a vyhledávacích stromů a operací nad nimi)
15. Třídění (základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním)
16. Grafové algoritmy (procházení grafu do hloubky a do šířky, složitost procházení grafu)

Programové, informační a výpočetní systémy

1. Výpočetní systémy I (číselné soustavy, vztahy mezi číselnými soustavami, zobrazení čísel v počítači, principy provádění aritmetických operací. Booleova, Shefferova a Piercova algebra, kombinační a sekvenční logické obvody.)
2. Výpočetní systémy II (Procesory, jejich parametry a architektury. Architektura Intel.Vnitřní a vnější paměti a principy jejich funkce. Vstupní a výstupní zařízení počítače a jejich připojování)
3. Programování (strukturované programování v imperativním jazyce, datové a řídicí struktury programovacích jazyků, datové typy, procedury a funkce, bloková a modulární struktura programu)
4. Objektově orientované programování (základní pojmy OOP, zapouzdření, dědičnost, polymorfizmus, objektové programování v imperativním jazyce, spolupráce objektů. Událostmi řízené programování. Výjimky)
5. Operační systémy (achitektury operačních systémů, rozhraní operačních systémů. Procesy, synchronizace procesů, uváznutí a metody ochrany proti uváznutí. Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění.
6. Plánování v operačních systémech (správa a plánování činnosti procesorů. Systémy souborů. Správa a plánování činnosti V/V zařízení)
7. Počítačové sítě (topologie, přístupové metody a architektury počítačových sítí (Ethernet, Fast Ethernet, Token-ring, ATM, . . .). Bezdrátové komunikační technologie. Model OSI. Protokol TCP/IP. Propojování počítačových sítí a směrování informací)
8. Databáze I (relační model, relační schéma, klíče relačních schémat, integritní omezení, relační algebra, spojování relací)
9. Databáze II (funkční závislosti; klíče relačních schémat; Armstrongovy axiómy; dekompozice relačních schémat; normální formy obecně, 1NF, 2NF, 3NF, Boyce-Coddova NF, vztahy mezi NF; převody relačních schémat do NF)
10. SQL (syntaxe a sémantika příkazů; vestavěné funkce, triggery, uložené procedury, příkazy pro definici dat; transakční zpracování; atomické operace; optimalizace dotazů)
11. Základy datového modelování (návrh datových struktur; ER diagramy; entity, atributy, vztahy; grafické vyjádření)