Tematické okruhy ke SZZ 2015/2016

[johnymachine]

Tematické okruhy ke státní závěrečné zkoušce 2015/2016

Určeno pro studenty NMS oboru Informační technologie FM TUL

Postup pro vypracovávání je uveden v příslušné issue #5.

• 1. ⌛ Základy teorie grafů – souvislost, kostra grafu, eulerovské, hamiltonovské a rovinné grafy. Vybrané grafové algoritmy – prohledávání grafu, minimální kostra, nejkratší cesta. Okruh 1 - Základy teorie grafů #31
• 2. 👀 Základy teorie dělitelnosti – základní pojmy (NSD, NSN, Eukleidův algoritmus), řetězové zlomky, kongruence modulo m, úplná a redukovaná soustava zbytků, počítání v (Zm, +, .), řešení kongruencí 1. stupně a jejich soustav. Okruh 2 - Základy teorie dělitelnosti #15
• 3. ⌛ Rekurentní vztahy – základní pojmy, řešení, (ne)homogenní, (ne)lineární rekurentní vztahy, řešení lineárních rekurentních vztahů s konstantními koeficienty a jejich soustav (otázka existence a jednoznačnosti řešení), využití vytvořujících funkcí. Okruh 3 - Rekurentní vztahy #35
• 4. 👀 Základy klasické kombinatoriky – princip inkluze a exkluze, Dirichletův princip, zobecněný binomický koeficient, subfaktoriály, Fibonacciho, Catalanova a Stirlingova čísla, problematika rozkladů – varianty, (ne)rozlišitelné objekty, (ne)rozlišitelné skupiny, využití diofantických rovnic a vytvořujících funkcí v oblasti rozkladů. Okruh 4 - Základy klasické kombinatoriky #18
• 5. ⌛ Vytvořující funkce (obyčejná, exponenciální), otevřený a uzavřený tvar, základní operace s vytvořujícími funkcemi, vytvořující funkce (uzavřený tvar) základních posloupností, věžové polynomy. Okruh 5 - Vytvořující funkce #36
• 6. 👀 Problematika řazení – základní algoritmy a jejich složitost. Okruh 6 - Problematika řazení #10
• 7. 👀 Časová náročnost algoritmů. Průměrné a nejhorší chování. Úlohy P, NP a NP-úplné. Okruh 7 - Časová náročnost algoritmů #37
• 8. 👀 Definice konečného automatu, jazyky rozpoznávané konečnými automaty. Okruh 8 - Konečné automaty #11
• 9. 👀 Gramatiky, Chomského hierarchie, vztah gramatik ke konečným strojům. Okruh 9 - Gramatiky #8
• 10. 👀 Turingův stroj, problém zastavení, totální a parciální rozhodnutelnost tříd problémů, rekurzivní a rekurzivně spočetné množiny, jejich vztah. Okruh 10 - Turingův stroj #38
• 11. ⌛ Pojmy šifrování, kódování, symetrické šifry (afinní, Vigener, Hill, jednoduchá transpozice), asymetrické šifry (RSA), Feistelovy šifry, princip, příklady (DES, AES, NDS). Okruh 11 - Pojmy šifrování #33
• 12. ⌛ : Minimální kódy, princip, použití, konstrukce Huffmanova kódu, aritmetické kódy. Okruh 12 - Minimální kódy #29
• 13. ⌛ Operační systém a jeho základní úlohy – správa paměti, správa procesů, životní cyklus procesu, přidělování procesoru, správa periferií, problém uváznutí a metody jeho předcházení. Okruh 13 - Operační systém #28
• 14. 👀 Databázové systémy – relační a objektový model dat, NoSQL databáze (typy škálování, teorém CAP). Okruh 14 - Databázové systémy #16
• 15. 👀 Normalizace v relačním modelu, bezztrátová dekompozice, datové modelování (ER/ERA diagramy), funkční analýza (DFD diagramy), optimalizace databázových struktur (typy indexů a případy jejich využití). Okruh 15 - Normalizace, modelování a optimalizace v databázi #19
• 16. ⌛ Jazyk SQL (DDL, DML, množinové operace), uložené procedury a spouště v SQL, transakce (ACID, typy konfliktů, stupně izolace). Okruh 16 - Jazyk SQL #20
• 17. 👀 Programování síťových operací, koncepce socketů a jejich využití, blokující a neblokující komunikační operace. Okruh 17 - Programování síťových operací #30
• 18. 👀 WWW aplikace, programování na straně klienta a serveru, jejich možnosti a omezení, nejběžnější používané prostředky a jazyky, uchovávání stavové informace, cookie. Okruh 18 - WWW aplikace #9
• 19. ⌛ Alternativní přístupy k programování – funkcionální programování a Lambda kalkulus, náhrada cyklu rekurzí, logické programování, rezoluční mechanismus a jazyk Prolog. Okruh 19 - Alternativní přístupy k programování #17
• 20. ⌛ Deterministické číslicové signály – popis v časové oblasti, periodicita, DTFT/DFT spektrum, krátkodobá spektrální analýza (STFT) + využití okénkových funkcí, vzorkovací teorém, kvantizace. Okruh 20 : Deterministické časové signály #21
• 21. ⌛ LTI číslicové systémy – vlastnosti (linearita, kauzalita, stabilita), impulsní odezva (FIR/IIR), frekvenční charakteristika, přenosová funkce, skupinové zpoždění, lineární diferenční rovnice konstantními koeficienty, systém s lineární a minimální fází. Okruh 21. - LTI číslicové systémy #22
• 22. ⌛ Návrh číslicových filtrů – toleranční schéma, základní druhy filtrů (DP, HP, PP, PZ, Allpass), návrh FIR filtrů (metoda oken, metoda vzorkování frekvenční charakteristiky), typy IIR filtrů, porovnání vlastností FIR/IIR filtrů. Okruh 22 - Návrh číslicových filtrů #27
• 23. ⌛ DFT/FFT (radix-2) – vlastnosti a výpočetní složitost, linearní a kruhová konvoluce, rychlý výpočet lineární konvoluce pomocí FFT (metoda overlap-add, overlap-save). Okruh 23 - DFT/FFT  #26
• 24. ⌛ Rozdělení a architektury programovatelných zákaznických obvodů, jazyky pro popis technických prostředků, charakteristické rysy jazyka VHDL. Okruh 24 - Programovatelné zákaznické obvody #32
• 25. ⌛ Zásady návrhu elektronických systémů (základní struktura systému, pravidla synchronního návrhu, přenos signálů mezi časovými doménami). Okruh 25 - Zásady návrhu elektronických systémů #34
• 26. ⌛ Základní architektury počítačů, architektury mikroprocesorů, architektury signálových a grafických procesorů, architektury mikrořadičů, hodnocení výkonnosti počítačů, Amdahlův zákon, výkonnostní rovnice procesoru, srovnání systémů CISC a RISC. Okruh 26 - Základní architektury počítačů #23
• 27. ⌛ Paralelní systémy, kategorie, paralelizace zpracování, víceprocesorové systémy, programování v paralelních a distribuovaných systémech – přístupy, prostředky, metody vzájemné synchronizace. Okruh 27 - Paralelní systémy #14
• 28. ⌛ Významné průmyslové komunikační systémy a sběrnice v počítačových systémech (CAN, Ethernet, Modbus, SPI, I2C, RS-232, USB, PCI-e, SATA), topologie, charakteristické vlastnosti. Okruh 28 - Průmyslové komunikační systémy #24
• 29. 👀 Abstraktní datové typy, seznam, fronta, zásobník, halda, strom, asociativní pole. Okruh 29 - Abstraktní datové typy #12
• 30. ⌛ Vyhledávání lineární a binární, datové struktury optimalizované pro vyhledávání a práce s nimi, binární vyhledávací strom, 2-3 strom, B strom, hashování. Okruh 30 - Vyhledávání #13

Původní pdf je dostupné zde: http://www.fm.tul.cz/pro-studenty/dpszz

[johnymachine]

Důležité věci mimo okruh:

• AD a DA převodníky
• zabezpečovací kódy Hamming, CRC
• Protokol TCP/IP
• Mealyho a Moorův automat

Na zvážení sekce extras