Otázky IO
Teoretické základy informatiky
Z prvních tři následujících okruhů, neskládají zkoušku ti, kteří mají v kombinaci matematiku.
- Množiny a relace (zobrazení, funkce, rozklady a ekvivalence)
- Elementární kombinatorika (variace, kombinace a permutace)
- Uspořádání (relace uspořádání, uspořádané množiny a svazy, číselné obory)
- 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)
- Predikátová logika prvního řádu (syntax, sémantika, prenexace, skolemizace,
unifikace, rezoluce)
- Prolog (SLD-rezoluce, SLD-stromy, výpočetní mechanismus Prologu, základy
programování v Prologu)
- Důkazy programů (dokazování vlastností programů, induktivní metody, invarianty
cyklů)
- 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ů)
- 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)
- 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)
- 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)
- 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ů)
- 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).
- 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)
- Třídění (základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním)
- Grafové algoritmy (procházení grafu do hloubky a do šířky, složitost
procházení grafu)
Programové, informační a výpočetní systémy
- 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.)
- 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í)
- 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)
- 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)
- 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í.
- 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í)
- 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í)
- 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í)
- 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)
- 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ů)
- Základy datového modelování (návrh datových struktur; ER
diagramy; entity, atributy, vztahy; grafické vyjádření)
Odpovědný kontakt:
doc. RNDr. Vojtěch Řehák, Ph.D.