Předmět Základy informatiky (KMI / SZZA1)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / SZZA1 - Základy informatiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

Materiál	Typ	Datum	Počet stažení

Obsah

Formální jazyky a jejich hierarchie. Regulární jazyky (definice, uzávěrové vlastnosti). Konečné automaty deterministické a nedeterministické. Regulární výrazy, automaty s epsilon-přechody. Minimalizace konečného deterministického automatu. Bezkontextové jazyky a jejich vlastnosti (uzávěrové vlastnosti, jednoznačnost). Zásobníkové automaty a jejich modifikace. Deterministické zásobníkové automaty. Deterministické bezkontextové jazyky.Pojem algoritmu, vlastnosti a druhy algoritmů. Pojem složitosti, příklady. Základní pojmy teorie grafů. Průchod grafem do hloubky a do šířky. Hledání cest (Dijsktrův algoritmus), hledání minimální kostry grafu (Kruskalův algoritmus). Základní datové struktury: pole, zásobník, fronta, seznam, stromy. Třídění výběrem, vkládáním, výměnou (bublinkové), Shellovo, složitosti algoritmů. Třídění quicksort, haldou (heapsort), sléváním, složitosti algoritmů. Vyhledávání v poli, binární vyhledávácí stromy, vyvážené, AVL stromy, B-stromy a R-stromy, složitost operací. Hašování, univerzální hašování, dokonalé hašování. Digitální vyhledávání, trie, rozklad na singulární hodnoty a jeho výpočet, vlastnosti SVD, Pagerank vlastnosti a výpočet.Přehled a základní rysy programovacích paradigmat. Dynamický a statický typový systém. Prostředí, lexikální a dynamický rozsah platnosti proměnných. Správa paměti, garbage collector. Předávání argumentů procedurám, procedury vyšších řádů. Rekurzivní datové struktury, rekurzivní procedury.Funkcionální programování, symbolické výrazy, vyhodnocovací proces. Páry a seznamy. Makra, líné vyhodnocování, proudy. Kontext, únikové funkce, aktuální pokračování. Stav, vedlejší efekt, příkaz přiřazení.Objektové programování, třídy a objekty, zprávy a metody. Zapouzdření, polymorfismus, dědičnost. Metody a jejich typy, způsoby ochrany. Vícenásobná dědičnost. Příklady objektově orientovaných jazyků a jejich rysy.Paralelní program, historie, atomické akce, synchronizace. Problémy producent-konzument a čtenáři-písaři, základní řešení. Kritická sekce a její použití. Bariéra a její použití v datově paralelních algoritmech. Semafor a jeho použití pro řešení synch. problémů. Podpora paralelizace v hlavních operačních systémech.Relační databázové systémy: relační model dat a jeho vlastnosti. Jazyk SQL: vytváření tabulek, dotazy, spojení tabulek, referenční integrita, pohledy, indexy, spolupráce SQL s jinými jazyky, základy administrace relačního databázového systému. Analýza a návrh relační databáze: ER a UML model dat a jeho transformace do relačního modelu. Systém řízení báze dat: služby, architektura, abstraktní modely dat, transakční zpracování dat, uzamykací protokoly. Formalizace datové tabulky: relační operace, relační algebra, relační logika/kalkuly a jejich úplnost. Funkční závislosti: definice, vlastnosti a jejich význam, Armstrongovy axiomy. Normální formy: definice a příklad, normalizace relačních schémat.

Požadavky

Schopnost odborně popsat a shrnout problematiku (motivaci, prostředky,výsledky).

Garant

doc. RNDr. Vilém Vychodil, Ph.D.