Předmět Základní metody informatiky (KMI / SZZZM)

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 / SZZZM - Základní metody informatiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

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

Obsah

verze 1, nový studijní plán: pro studenty, kteří začali studovat navazující magisterské studium od roku 2010 a pozdějiAbeceda, formální jazyk, gramatika. Chomského klasifikace gramatik a jazyků. Konečné automaty a regulární jazyky. Zásobníkové automaty a bezkontextové jazyky.Částečně rekurzivní a rekurzivní jazyky, jazyky a rozhodovací problémy. Složitost algoritmu (časová a paměťová). Třída P, třída NP, důvody jejich zavedení, jejich vzájemný vztah. NP-úplné problémy. Vybrané NP-úplné problémy, dokazovaní NP-úplnosti.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 a B-stromy, složitost operací. Hešování, jednoduché a dvojité, hešovací funkce. Grafy, reprezentace, průchod grafem do hloubky a do šířky.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.Logické programy, jejich syntaxe a sémantika, proměnné, termy a formule. Unifikace, rezoluce, výpočet programu. Základní rysy jazyka PROLOG: programy, dotazy (cíle), výpočet, řízení výpočtu.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, základní pojmy (atributy, domény, ntice, relační schémata, relace). Operace relační algebry: množinové operace, projekce, selekce, dělení, spojení a jeho typy. Vzájemné vztahy relačních operací. Realizace relačních operací v jazyce SQL.Výroková logika: syntax a sémantika, normální formy, korektnost a úplnost. Predikátová logika: syntax a sémantika, korektnost a úplnost.==================================================verze 2, starý studijní plán: pro studenty, kteří začali studovat navazující magisterské studium od roku 2009 a dřívevizhttp://www.inf.upol.cz/statni-zaverecna-zkouska

Garant

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