Fakulta elektrotechnická

České vysoké učení technické v Praze

ČVUT v Praze

Tematické okruhy státních zkoušek magisterského studijního programu Otevřená informatika

  1. Amortizovaná složitost. Prioritní fronty, haldy (binární, d-regulární, binomiální, Fibonacciho), operace nad nimi a jejich složitost. (A4M33PAL)
  2. Efektivní algoritmy pro standardní grafové úlohy: Tarjanův a Kosajaru-Sharirův algoritmus detekce silně souvislých komponent v orientovaném grafu. Konstrukce topologického uspořádání acyklického grafu. Algoritmy hledání minimální kostry grafu (Borůvkův, Primův, Kruskalův). Union-Find problém. (A4M33PAL)
  3. Vyhledávací stromy: B, B+, R-B, 2-3-4, splay a jejich praktické využití. Problematika vyhledávání ve více dimenzích, K-D stromy. (A4M33PAL)
  4. Přesné a přibližné hledání množin vzorků v textu, Hammingova a Levenshteinova vzdálenost. Efektivní algoritmy hledání založené na využití konečných automatů. Klasické hledání v textu (naivní, Boyer-Moore). Slovníkové automaty. (A4M33PAL)
  5. Algoritmus, správnost algoritmu, složitost algoritmu, složitost úlohy, třída P, třída NP. (A4M01TAL)
  6. NP-úplné a NP-těžké úlohy, Cookeova věta, heuristiky na řešení NP-těžkých úloh, pravděpodobnostní algoritmy. (A4M01TAL)
  7. Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky, algoritmicky neřešitelné úlohy. (A4M01TAL)
  8. Metoda větví a mezí. Algoritmy pro celočíselné lineární programování. Formulace optimalizačních a rozhodovacích problémů pomocí celočíselného lineárního programování. Toky a řezy. Multi-komoditní toky. (A4M35KO)
  9. Nejkratší cesty. Úloha obchodního cestujícího. Heuristiky a aproximační algoritmy. Metoda dynamického programování. Problém batohu. Pseudo-polynomiální algoritmy. (A4M35KO)
  10. Rozvrhování na jednom procesoru a na paralelních procesorech. Rozvrhování projektu s časovými omezeními. Programování s omezujícími podmínkami.(A4M35KO)

Obor Umělá inteligence

  1. Ontologie - význam, typy prvků, vztah k jiným způsobům reprezentace (rámce). Ontologické jazyky - cíl, příklady jazyků a jejich použití. (A4M33RZN)
  2. Podmíněná nezávislost a její vyjádření grafem. Bayesovské sítě jako nástroj reprezentace neurčité informace, inference v nich a jejich učení z dat. (A4M33RZN)
  3. Reprezentace vágních údajů pomocí fuzzy množin. Základní operace ve fuzzy logice. (A4M33RZN)
  4. Definice, reprezentace a složitost plánovacích problémů. Rozdíly mezi problémy doménově nezávislého a doménově specifického plánování. Plánovací algoritmy, prohledávání prostoru stavů a plánů. (A4M36PAH)
  5. Definice a použití plánovacích grafů, vč. mutexů. Heuristické plánování, relaxace, abstrakce. (A4M36PAH)
  6. Plánování pohybu, konfigurační prostor a mapy cest, randomizované vzorkovací metody. Hierarchické plánování - reprezentace problému, metody a plánovací proces. (A4M36PAH)
  7. Základní model evolučního algoritmu, jeho hlavní komponenty. Výhody a nevýhody evolučních algoritmů oproti gradientním optimalizačním metodám. Genetický algoritmus a genetické programování: reprezentace, operátory a aplikační domény. (A4M33BIA)
  8. Vícekriteriální evoluční algoritmy, Paretův princip dominance. Algoritmy NSGA a SPEA a jejich rozdíly. (A4M33BIA)
  9. Učení neuronových sítí s učitelem a bez učitele, neurony perceptronoveho typu a RBF neurony. Principy a použití různých paradigmat neuronových sítí. (A4M33BIA)
  10. Formalizace konceptu autonomních agentů a multiagentních systémů. Řídicí architektury agentů, architektura BDI. Distribuované řešení úloh, problémy distribuovaného splňování a optimalizace omezujících podmínek a algoritmy pro jejich řešení. (A4M36MAS)
  11. Nekooperativní teorie her. Hry v normalní a extenzivní formě. Koncepty řešení nekooperativních her (zejména Nashova rovnováha), jejich vlastnosti a algoritmy pro jejich nalezení. Systematické algoritmy (zejména minimax, alfa-beta prořezávání) a vzorkovací algoritmy prohledávání herních stromů. (A4M36MAS)
  12. Formalizace koaličních her a koncepty jejich řešení, zejména jádro a Shapleyho hodnota. Aukční mechanismy a jejich vlastnosti. Teorie veřejné volby, hlasovací protokoly. (A4M36MAS)
  13. Shluková analýza: algoritmus k středů, hierarchické shlukování, spektrální shlukování, shlukování s částečně anotovanými daty. (A4M33SAD)
  14. Časté množiny položek, podsekvence a podgrafy. Asociační pravidla: algoritmus Apriori. Epizodální pravidla. (A4M33SAD)
  15. Výpočetní teorie učení: rozměr hypotézového prostoru, PAC-naučitelnost. PAC-Naučitelnost výrokových konjunkcí, disjunkcí, CNF, DNF, rozhodovacích stromů a seznamů. (A4M33SAD)
  16. Principy metod strojového dokazování v booleovských doménách a v predikátové logice (např. procedura DPLL, unifikace, subsumpce, skolemizace, resoluce, metoda tableaux). (A4M33AU)
  17. Hledání modelů v obecných doménách. ANL Smyčka. Metody dokazování v teoriích s rovností. (A4M33AU)
  18. Korektnost, úplnost a teoretické a praktické limity současných dokazovacích systémů. (A4M33AU)
  19. Model checking (např. SAT, konečné automaty, časové automaty). Praktické využití metod automatického uvažování, např. verifikace programů pomocí formálních metod. Jazyk TPTP. (A4M33AU)

Obor Počítačové inženýrství

  1. Architektura distribuovaných síťových aplikací. Struktura sítě, vrstvy a hlavní části sítě. Nejběžnější databázové servery v průmyslových aplikacích a jejich management. Webové aplikace v distribuovaných řídicích systémech. (A0M35PII)
  2. Klasické PLC, tagově orientované PLC, systémy SCADA (Supervisory Control And Data Acquisition) a MES (Manufacturing Execution Systems) - principy, organizace, činnost a sběr dat. Průmyslové sítě. OPC (OLE for Process Control). (A0M35PII)
  3. Spolehlivost sítí a řešení vhodná pro kritické aplikace (A0M35PII)
  4. Metodiky návrhu analogových, digitálních a smíšených integrovaných systémů. Aplikačně specifické integrované systémy - plně zákaznický návrh, hradlová pole, standardní buňky, programovatelné obvody FPGA. (A4M34ISC)
  5. Jazyky HDL, HDL-A, logická a fyzická syntéza systému. Frond End a Back End návrh. Problematika rozmístění (floorplaning), časové analýzy, návrh testů a verifikace návrhu. (A4M34ISC)
  6. CAD prostředky a standardy pro návrh analogových a smíšených integrovaných obvodů, mobilní IO s nízkou spotřebou, verifikace návrhu. Technologická realizace, verifikace integrovaných systémů, problematika převodu návrhu systému mezi jednotlivými technologiemi. (A4M34ISC)
  7. Techniky správy a organizace rozsáhlých softwarových projektů. Nástroje pro správu verzí zdrojových kódů, sledování chyb, pro automatické generování dokumentace a podporu orientace v rozsáhlých projektech. Způsoby komunikace mezi vývojáři navzájem a i s uživateli. Systémy pro sledování a řešení chyb a uživatelskou podporu. Open-source licence a z nich vyplývající práva a licence. Postup začlenění úpravy (patche) do velkého open-source projektu (např. Linuxové jádro). (A4M35OSP)
  8. Požadavky a pravidla pro tvorbu přenositelného kódu. Organizace projektů a struktura operačních systémů pro zajištění přenositelnosti mezi různými platformami (OS, CPU). Vnitřní a vnější reprezentace dat, převody mezi nimi, vztah k síťovým protokolům (endianing, serializace atd.). (A4M35OSP)
  9. I/O rozhraní počítačů (PCI, PCIe a USB), funkce, implementace a ovladače zařízení. (A4M38KRP)
  10. Síťová rozhraní (Ethernet, Auto-negotiation, PoE), implementace IP zásobníku. (A4M38KRP)
  11. Bezdrátové sítě (IEEE802) a jejich implementace. (A4M38KRP)
  12. Pokročilé architektury procesorů. Paralelismus na úrovni instrukcí (ILP). Superskalární procesory se statickým a dynamickým plánováním provádění instrukcí. Spekulativní provádění instrukcí a podpora přesného přerušení. Procesory VLIW a EPIC. Využití datového paralelismu, SIMD a vektorové instrukce v ISA. (A4M36PAP)
  13. Architektura paměťového a periferního subsystému. Návrh a optimalizace paměťového subsystému, cache a virtuální paměť. Způsoby propojení procesoru, paměti a periférií uvnitř systémů na čipu (SoC). Vyrovnávací paměti v periferním subsystému, způsoby implementace sdíleného přístupu k vyrovnávací paměti. (A4M36PAP)
  14. Architektury multiprocesorových počítačů. Architektury symetrických multiprocesorových počítačů (SMP). Způsoby zajištění koherence v SMP. Pravidla pro provádění paměťových operací, zajištění sekvenční konzistence, slabší modely paměťové konzistence. Architektury s distribuovanou sdílenou pamětí, zajištění koherence a konzistence. Vícevláknové procesory. (A4M36PAP)
  15. Uspořádání, vlastnosti, funkční bloky a oblasti použití mikrořadičů, jejich typické periferie a rozhraní, způsoby ovládání výstupních členů (akustických, opoelektronických, mechanických a silových,..). (A4M38AVS)
  16. Mikrořadiče s jádrem ARM a číslicové signálové procesory (DSP), architektura, základní funkční bloky, vlastnosti z hlediska aplikace ve vestavném systému. (A4M38AVS)
  17. Způsoby vstupu analogového signálu (ze snímačů zvuku, obrazu, pohybu, polohy a dalších snímačů) do vestavných systémů, základní metody zpracování signálu a jejich implementace ve vestavných systémech. (A4M38AVS)

Obor Počítačová grafika a interakce

  1. Rastrová grafika, kresba grafických primitiv, vyplňování, ořezávání. (A4M39APG)
  2. Reprezentace 3D objektů a 3D scény, kamera a projekční transformace. (A4M39APG)
  3. Barevné modely obrazu a obrazová komprese. (A4M39APG)
  4. Metody pro výpočet viditelnosti, lokální a globální osvětlení scény, vržené stíny. (A4M39APG)
  5. Světlo, stínování, texturování. (A4M39APG)
  6. Regulární a hierarchické datové struktury pro vyhledávání v blízkosti, obecné vlastnosti prostorových datových struktur (aplikace vyhledávání K nejbližších sousedů a v rozsahu). (A4M39DPG)
  7. Datové struktury pro reprezentaci bodových a prostorových dat (volumetrické a hraniční reprezentace a jejich vlastnosti). (A4M39DPG)
  8. Datové struktury pro pokročilé algoritmy, vrhání paprsku a výpočtu detekce kolizí (kd-stromy, hierarchie obálek, jejich vlastnosti). (A4M39DPG)
  9. Afinní a projektivní rovina a prostor. Reprezentace bodů, přímek, rovin, úhlů a vzdáleností a operace s nimi. (A4M33GVG)
  10. Matematický model, kalibrace a poloha perspektivní kamery a jejich výpočet. (A4M33GVG)
  11. Rekonstrukce 3D scény z obrazů. Homografie. Epipolární geometrie. Výpočet pohybu kamery z korespondencí v obrazech. (A4M33GVG)
  12. Inverzní kinematika (IK problém a metody jeho řešení v počítačové animaci), dynamika, animace lidské postavy, animace davu. (A4M39MMA)
  13. Částicové systémy (reprezentace, druhy sil, zobrazování, aplikace), fluidní dynamika (Navier-Stokesovy rovnice, metody simulace pohybu fluidního pole v počítačové animaci). (A4M39MMA)
  14. Modelování a animace šatů a lidské tváře - metody reprezentace, vlastnosti, principy simulace. (A4M39MMA)
  15. Syntéza a zpracování zvuku (pojem zvukový signál, jeho vlastnosti, metody syntézy a zpracování v rámci multimediální tvorby). (A4M39MMA)
  16. Produkční proces (kompozice videa, klíčování), snímání pohybu (MOCAP systémy, jejich principy a metody zpracování nasnímaných dat), stereoskopické zobrazování (binokulární vnímání, parametry projekce a jejich vliv na celkový vjem hloubky scény). (A4M39MMA)
  17. Konvexní množina, konvexní obálka množiny (definice). Reprezentace konvexní obálky ve 2D. Její výpočet pro množinu bodů: Grahamův algoritmus, Jarvisův algoritmus balení dárku, metoda rozděl a panuj. Výpočet konvexní obálky pro jednoduchý polygon. Výpočet a reprezentace konvexní obálky ve 3D. (A4M39VG)
  18. Test příslušnosti bodu k polygonu a příslušnosti bodu k oblasti v planárním dělení (metoda pásů, strom monotónních řetězů). Reprezentace planárního dělení (DCEL), výpočet překrytí planárních dělení (průsečík, sjednocení, rozdíl) modifikovaným Plane-sweep algoritmem pro průsečíky množiny úseček. (A4M39VG)
  19. Voronoiův diagram. Vlastnosti, metody konstrukce. Příklady využití. (A4M39VG)
  20. Ortogonální vyhledávání, kD strom, intervalový strom (range tree), segmentový strom. (A4M39VG)
  21. Kategorizace vizualizačních technik, vizualizace skalárních, vektorových a objemových dat. (A4M39VIZ)
  22. Vizualizace dynamických dat, vizualizace informace, vizualizace a percepce. (A4M39VIZ)
  23. Aplikace vizualizačních technik (vizualizace medicinských dat, vizualizace grafů, visual data mining,...). (A4M39VIZ)

Obor Softwarové inženýrství

  1. Sémantika: operační sémantika, denotační sémantika, pevný bod funkce, vázání jmen, stav programu a data. (A4M36TPJ)
  2. Statická sémantika: typy, polymorfní typy, typy vyššího řádu, rekonstrukce (inference) typů, abstraktní typy. (A4M36TPJ)
  3. Teorie HCI, kognitivní aspekty, způsoby interakce, speciální uživatelská rozhraní, (A4M39NUR)
  4. Metody návrhu, uživatelské a konceptuální modely (A4M39NUR)
  5. Formální popis uživatelských rozhraní (A4M39NUR)
  6. Prototypování uživatelských rozhraní. (A4M39NUR)
  7. Techniky správy a organizace rozsáhlých softwarových projektů. Nástroje pro správu verzí zdrojových kódů, sledování chyb, pro automatické generování dokumentace a podporu orientace v rozsáhlých projektech. Způsoby komunikace mezi vývojáři navzájem a i s uživateli. Systémy pro sledování a řešení chyb a uživatelskou podporu. Open-source licence a z nich vyplývající práva a licence. Postup začlenění úpravy (patche) do velkého open-source projektu (např. Linuxové jádro). (A4M35OSP)
  8. Požadavky a pravidla pro tvorbu přenositelného kódu. Organizace projektů a struktura operačních systémů pro zajištění přenositelnosti mezi různými platformami (OS, CPU). Vnitřní a vnější reprezentace dat, převody mezi nimi, vztah k síťovým protokolům (endianing, serializace atd.). (A4M35OSP)
  9. Co je to architektura zaměřená na služby (SOA)? Základní pojmy, vztah k objektově orientované architektuře. Konceptuální model a formalismy pro modelování SOA. (A4M33AOS)
  10. Webové služby. K čemu slouží? Popis a vyhledávání služeb. Technologie pro implementaci a nasazení služeb a klientů. Protokoly, kódování obsahu. Top-down a bottom-up design. (A4M33AOS)
  11. Webové služby, automatická kompozice služeb. Orchestrace a choreografie, web mash-up. Modelování služeb a procesů (BPMN, BPEL). (A4M33AOS)
  12. Architektura zaměřená na služby (SOA). Kvalita, výkonost a škálování služeb. Zabezpeční, integrita, bezpečnost, a autentifikace služeb. Point-to-point a end-to-end šifrování. (A4M33AOS)
  13. Kategorizace SW chyb, optimalizace návrhu testů. Testování automatů. (A4M33TVS)
  14. Testovaní metodami bílé a černé skřínky. Strukturální, statická a dynamická analýza. Analýza datových toků. Testování objektově orientovaného softwaru. (A4M33TVS)
  15. Formální specifikace programu. Verifikace pomocí metod automatického dokazování a metody model-checking. (A4M33TVS)
  16. Architektura Java EE, funkce jednotlivých vrstev, životní cyklus standardizovaných komponent Java EE, návrhové vzory využitelné v architektuře webové aplikace. (A4M39WA2)
  17. Vhodnost nasazení jednotlivých webových architektur, sdílení dat, perzistence, webové služby a REST, asynchronnost, messaging. (A4M39WA2)
  18. Není - okruh zrušen(A4M39WA2)
  19. Cloud architektury, virtualizace, různá pojetí cloudových řešení, omezení cloudových aplikací, náklady na provoz, vlastnosti aplikací vhodných pro nasazení v cloud architektuře. (A4M39WA2)

Obor Počítačové vidění a digitální obraz

  1. Fyzikální aspekty vzniku obrazu, geometrická optika, radiometrie. Barevné prostory a multispektrální obrazy. (A4M33DZO)
  2. Konvoluce, korelace, Fourierova transformace pro obrazy. Vzorkovací věta, rekonstrukce obrazu, interpolace obrazu, např. při geometrických transformacích. (A4M33DZO)
  3. Detekce hran, Cannyho a Sobelův detektor, prostor měřítek. Matematická morfologie, pojem sousedství a souvislosti v diskrétním obraze, diskrétní metriky. (A4M33DZO)
  4. Segmentace obrazu. Taxonomie přístupů. Segmentace prahováním, na základě prostorové podobnosti, pomocí matematické morfologie, shlukováním metodou k-průměrů, řešením optimalizačních úloh, např. hledáním minimálního řezu grafem. (A4M33DZO)
  5. Komprese obrazu a videa, metody LZW, JPEG, MPEG. (A4M33DZO)
  6. Detektory "bodů" a oblastí zájmu. Algoritmy detekce a jejich citlivosti na geometrické a fotometrické změny v obraze. Popis oblasti zájmů: metoda lokálních rámců pro zajištění geometrické invariance popisu, deskriptor SIFT (scale invariant feature transform) (A4M33MPV)
  7. Hledání korespondencí mezi obrazy. Houghova transformace (HT). Použití HT a metody RANSAC (Random Sample and Consensus) pro robustní nalezení transformace mezi obrazy. Porovnání rychlosti a paměťové naročnosti HT a metody RANSAC. (A4M33MPV)
  8. Sledování objektu (tracking). Formulace úlohy, standardní algoritmy (např. Kanade-Lucas tracker a mean-shift tracker) (A4M33MPV)
  9. Afinní a projektivní rovina a prostor. Reprezentace bodů, přímek, rovin, úhlů a vzdáleností a operace s nimi. (A4M33GVG)
  10. Matematický model, kalibrace a poloha perspektivní kamery a jejich výpočet. (A4M33GVG)
  11. Rekonstrukce 3D scény z obrazů. Homografie. Epipolární geometrie. Výpočet pohybu kamery z korespondencí v obrazech. (A4M33GVG)
  12. Shluková analýza: algoritmus k středů, hierarchické shlukování, spektrální shlukování, shlukování s částečně anotovanými daty. (A4M33SAD)
  13. Časté množiny položek, podsekvence a podgrafy. Asociační pravidla: algoritmus Apriori. Epizodální pravidla. (A4M33SAD)
  14. Výpočetní teorie učení: rozměr hypotézového prostoru, PAC-naučitelnost. PAC-Naučitelnost výrokových konjunkcí, disjunkcí, CNF, DNF, rozhodovacích stromů a seznamů. (A4M33SAD)
  15. Základní geometrické úlohy: Resekce kamery (šestibodový algoritmus), absolutní orientace kamery (tříbodový algoritmus), relativní orientace dvojice kamer (pětibodový algoritmus), odhad fundamentální matice (sedmibodový algoritmus), triangulace 3D bodů z korespondencí. Výpočet relativní orientace a polohy v systému více kamer. Metoda vyrovnání svazku. Minimální reprezentace projekční matice. Modely radiálního zkreslení. (A4M33TDV, A4M33GVG)
  16. Úloha řídkého párování. Algebraická a geometrická chyba a jejich vlastnosti. Sampsonova aproximace. Pojem robustní chybové funkce a její optimalizace náhodným vzorkováním. (A4M33TDV)
  17. Stereoskopické párování, epipolární narovnání obrazů, disparitní mapa a podmínky jednoznačnosti a uspořádání. Formulace párovací úlohy a základní algoritmy. (A4M33TDV)
  18. Fotometrické stereo. Výpočet mapy odrazivosti a mapy normál pro Lambertovský povrch ze třech osvětlení. (A4M33TDV)
  19. Konvexní množina, konvexní obálka množiny (definice). Reprezentace konvexní obálky ve 2D. Její výpočet pro množinu bodů: Grahamův algoritmus, Jarvisův algoritmus balení dárku, metoda rozděl a panuj. Výpočet konvexní obálky pro jednoduchý polygon. Výpočet a reprezentace konvexní obálky ve 3D. (A4M39VG)
  20. Test příslušnosti bodu k polygonu a příslušnosti bodu k oblasti v planárním dělení (metoda pásů, strom monotónních řetězů). Reprezentace planárního dělení (DCEL), výpočet překrytí planárních dělení (průsečík, sjednocení, rozdíl) modifikovaným Plane-sweep algoritmem pro průsečíky množiny úseček. (A4M39VG)
  21. Voronoiův diagram. Vlastnosti, metody konstrukce. Příklady využití. (A4M39VG)
  22. Ortogonální vyhledávání, kD strom, intervalový strom (range tree), segmentový strom. (A4M39VG)
Za obsah odpovídá: doc. Ing. Jiří Jakovenko, Ph.D.