Státní závěrečná zkouška

http://www.fit.vutbr.cz/info/rd/2012/rd19-120411.pdf

Jazyk a sémantika predikátové logiky (termy, formule, realizace jazyka, pravdivost formulí).

Formální systém predikátové logiky (axiomy a odvozovací pravidla, dokazatelnost, model a důsledek teorie, věty o úplnosti a kompaktnosti, prenexní tvar formulí).

Algebraické struktury (grupy, okruhy, obory integrity a tělesa, svazy a Booleovy algebry, univerzální algebry).

Základní algebraické metody (podalgebry, homomorfismy, přímé součiny, kongruence a faktorové algebry, normální podgrupy a ideály okruhů).

Obory integrity a dělitelnost (okruhy polynomů, pravidla dělitelnosti, Gaussovy a Eukleidovy okruhy).

Teorie polí (minimální pole, rozšíření pole, konečná pole a jejich konstrukce).

Metrické prostory (příklady, konvergence posloupností, spojitá a izometrická zobrazení, úplnost, Banachova věta o pevném bodu).

Normované a unitární prostory (základní vlastnosti a příklady, normované prostory konečné dimenze, uzavřené ortonormální systémy a Fourierovy řady).

Obyčejné grafy (stupně uzlů, cesty a kružnice, souvislost grafu, stromy, kostry, Kruskalův a Primův algoritmus pro hledání minimální kostry ohodnoceného grafu).

Orientované grafy (orientované cesty a kružnice, souvislost a silná souvislost, turnaj, eulerovský graf, Dijkstrův a Floyd-Warshallův algoritmus pro hledání cesty minimální délky).

Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.

Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost).

Konečné automaty (jazyky přijímané jazyky KA, varianty KA, minimalizace KA).

Regulární množiny, regulární výrazy a rovnice nad regulárními výrazy.

Transformace a normální formy bezkontextových gramatik.

Zásobníkové automaty (jazyky přijímané ZA, varianty ZA).

Turingovy stroje (jazyky přijímané TS, varianty TS, lineárně omezené automaty, univerzální TS).

Nerozhodnutelnost (problém zastavení TS, princip diagonalizace a redukce, Postův korespondenční problém).

Parciální rekurzivní funkce.

Časová a paměťová složitost ( třídy složitosti, úplnost, SAT problém).

Metodika návrhu HW/SW codesign, programovatelné obvody

Výpočetní modely (StateCharts, codesign konečný automat, Kahnova síť procesů, synchronní dataflow).

Odhady vlastností systému (přesnost, věrnost, metriky, metody).

Rozdělování úlohy na SW a HW část (alokace, přidělení, plánování).

Jazyk VHDL (entita, architektura, procesy).

Lambda kalkul (definice všech pojmů, operací, …).

Práce v lambda kalkulu (reprezentace čísel a pravdivostních hodnot a operací nad nimi).

Haskell – lazy evaluation (typy v jazyce, demonstrace lazy evaluation).

Haskell – typové třídy (definice, význam), monads, vstup/výstup, paralelizace.

Prolog – způsob vyhodnocení (základní princip, unifikace, chování vestavěných predikátů, operátor řezu /vhodné a nevhodné užití/, změny DB/programu za běhu).

Kódování, Shannonova věta o kódování, bezpečnostní kódy (lineární, Hammingovy, cyklické a konvoluční).

Architektura směrovačů - typy směrovačů, funkční části směrovače, zpracování paketů, základní typy architektur.

Přepínání paketů, trie, 3 generace IP přepínačů, Banyan, řešení kolizí.

Multicastové adresování a směrování, IGMP, distribuční stromy, DVMRP, PIM.

Správa chyb na úrovni paketů, TCP: trojcestné potvrzování, Go back N / selektivní opakování.

Protokolové inženýrství a formální specifikace protokolů (konečné automaty, gramatiky, stopy, relace, temporální logika).

Grafická knihovna OpenGL: vykreslovací řetězec (funkční bloky, možnosti nastavení), frame buffer, stencil buffer.

Afinní 3D transformace, kamera, projekce, skládání transformací.

Phongův model osvětlení, textury: materiály a osvětlení, způsob výpočtu, texturování, MIP mapping

Realistické zobrazování: metoda sledování paprsku, radiozita, distribuované sledování paprsku.

Zobrazování objemových dat: reprezentace dat, zobrazování, převod na polygonální síť.

Zobrazování v geometrické optice (maticová formulace, přenosové matice jednoduchých optických prvků).

Interference světla (skládání dvou a více koherentních vln, intenzita složené vlny, interferenční člen, konstruktivní a destruktivní interference, princip interferometru).

Difrakce světla (rozložení intenzity světla za obdélníkovou a kruhovou štěrbinou, Airyho obrazec, rozlišovací schopnost optických přístrojů, oka).

Polarizace světla (přirozené a lineárně polarizované světlo, polarizační rovina, způsoby polarizace světla, elipticky polarizované světlo, polarizační filtry).

Holografie a laser (holografický kód, jeho dekódování, mimoosový hologram, objemový hologram, vztah holografie a laseru, stimulovaná emise, metastabilní energetická hladina).

Vztah zpracování signálu a multimédií (proč je zpracování zvukového a obrazového signálu pro multimédia důležité, typické operace při zpracování zvukového a obrazového signálu).

Komprese zvuku (základní postupy při kompresi zvuku, jak se liší od obecné komprese dat, vztah k lidskému sluchu, kompresní poměr).

Komprese obrazu (základní postupy při kompresi obrazu, jak se liší od obecné komprese dat, vztah k lidskému zraku a jeho vlastnostem, dosahovaný kompresní poměr).

Komprese videosekvencí (základní postupy při kompresi videa, jak se liší od komprese obrazu, a od obecné komprese dat, vlastnosti a dosahovaný, kompresní poměr).

Programátorská rozhraní pro multimédia (přehled rozhraní, příklady použití rozhraní pro audio a video, základní vlastnosti rozhraní).

Obrazová data, jejich pořizování a možná poškození (obrazová data, možné reprezentace obrazu, druhy snímacích čipů a zařízení, jejich vlastnosti, vady pořízeného obrazu, šumy, optimální filtrace obrazu).

Transformace obrazu (jaké se používají transformace při zpracování obrazu, důvody a typické příklady použití transformací při zpracování obrazu).

Filtrace obrazu (definice lineární filtrace, typické příklady použití filtrů, použití rychlá konvoluce (přes FFT), návrh lineárních filtrů, nelineární filtrace).

Vodoznaky (watermarks) (vymezení pojmu vodoznak, základní principy a vlastnosti vodoznaků, typické příklady vodoznaků a jejich vlastnosti).

Detekce hran, segmentace (vymezení pojmů detekce hran a segmentace, možné aplikace algoritmů a jejich důvody, typické nasazení algoritmů).

Analýza a předzpracování řeči (spektrální analýza, preemfáze, rámce), základní parametry řeči (energie, průchody nulou, korelační koeficienty), cepstrum

Lineární predikce (podstata, výpočet parametrů LP filtru, použití lineární predikce).

Určení základního tónu (podstata, autokorelace, normalizovaná cross-korelace, metody zlepšení přesnosti).

Kódování – waveform, vokodéry, hybridní kodéry, princip CELP.

Rozpoznávání pomocí DTW a HMM (architektura HMM, přechodová pravděpodobnost, modelování funkcí hustoty pravděpodobnosti ve stavech, sekvence stavů, pravděpodobnost promluvy přes sekvenci stavů, Baum-Welch, Viterbi, podstata trénování parametrů).

Standardy pro rychlé vykreslování na GPU (OpenGL, Direct3D, XNA) – základní charakteristiky, srovnání, důležité verze.

Důležité knihovny pro práci s grafem 3D scény.

Standardy ukládání obrazů, 3D objektů a scén – rozdělení podle účelu, důležití zástupci, moderní trendy.

Standardy a knihovny ve zpracování videa – standardy kódování, důležité knihovny a nástroje.

MIDI a rozhraní pro profesionální práci se zvukem v reálném čase.