Otázky B-IVV Informatika ve vzdělávání
Studijní plán Minor
Teoretické základy informatiky- Výroková logika. Syntax, sémantika, odvozovací systém výrokové logiky, důkazy ve výrokové logice, pravdivost a dokazatelnost logických formulí. (IB000)
- Funkce a rekurze. Rekurzivní definice funkcí, rekurzivní datové typy (seznamy, stromy), funkce nad rekurzivními datovými typy. (IB114)
- Datové struktury a jejich implementace. Abstraktní datové typy: seznam, pole, zásobník, fronta, binární strom, obecný strom, vyhledávací strom. Implementace binárních a vyhledávacích stromů a operací nad nimi. (IB113, IB114)
- Grafy. Typy grafů, stromy, stupně vrcholů, orientované grafy, reprezentace grafů. Algoritmy prohledávání grafu do hloubky a do šířky a jejich využití. Komponenty souvislosti. (IB114)
- Třídění. Základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním. (IB114)
- Regulární jazyky. Regulární jazyky, regulární gramatiky, regulární výrazy, konečné automaty. Vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami. (IB110)
- 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. (IB110)
- Vyčíslitelnost. Turingův stroj jako univerzální výpočetní model. Problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Diagonalizace. (IB110)
- Složitost. Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy. (IB110)
- Výpočetní systémy I. Číselné soustavy, vztahy mezi soustavami, zobrazení celého čísla v počítači, aritmetika. Kódy, vnitřní, vnější, detekční a opravné. Procesory, jejich parametry a architektury. (PB150)
- 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. (IB113).
- Operační systémy. Architektury 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. (PB153)
- Počítačové sítě. Topologie, přístupové metody a architektury počítačových sítí (Ethernet, Fast Ethernet, Token-ring, ATM, atd.). Bezdrátové komunikační technologie. Model OSI. Protokol TCP/IP. Propojování počítačových sítí a směrování informací. (PB156)
- 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í. (PB168)
- Databáze II. Dotazovací jazyk SQL (příkaz select, spojování relací, agregační funkce). Zpracování dotazů. Základní principy, příklad. Indexování. Transakce. Vlastnosti transakčního zpracování.
- Softwarové inženýrství. Vývoj software. Specifikace požadavků, analýza a návrh systému, testování, verifikace a validace, provoz systému. Použití UML při vývoje software. (PB007)