KIV/BZINF - Státnice pro informatiky

Okruhy pro státní závěrečnou zkoušku. Zpravidla ale neplatí, že jeden okruh je jedna otázka. Někdy třeba spojí více okruhů do jednoho, jindy se zase zeptají jen na jednu jeho část.

Důležitá poznámka: používejte mozek! Wiki je plná kravin, přemýšlejte nad tím, co čtete, protože říct u státnic naprostou volovinu je to nejhorší, co se vám může stát. I odpověď "nevím" je lepší...

PPA2

1. Problém, algoritmus, program
2. Vykonání programu
3. Objekt, třída
4. Spojové datové struktury
5. Správnost programů
6. Analýza programů
7. Asymptotická složitost
8. Rekurze
9. Abstraktní datové typy
10. Zásobník, fronta, seznam
11. Strom, průchody stromem, binární vyhledávací stromy
12. Grafy a jejich implementace
13. Prohledávání grafů
14. Topologické řazení
15. Tabulka s přímým adresováním
16. Rozptylové tabulky s vnějším řetězením
17. Prioritní fronta
18. Halda
19. Algoritmy řazení O(N logN)
20. Dolní omezení pro porovnávací řazení
21. Generičnost
22. Dědičnost
23. Rozhraní
24. Algoritmická řešitelnost problémů
25. Klasifikace problémů

PT

1. Úvod do technologie programování a programovacích stylů, objektově orientovaný návrh, základní UML diagramy, psaní programů v Javě
2. Abstraktní datové typy zásobník fronta, seznamy, řady, vektory a jejich implementace
3. Stromové struktury (Avl, BVS, B, Red-Black) a jejich implementace
4. Skip-list - použití a implementace
5. Tabulky s rozptýlenými položkami, vyhledávání v tabulkách
6. Algoritmy zpracování textů – operace s řetězci, porovnání se vzorem (KMP, Boyer-Moore algoritmus), nejdelší společný podřetězec (LCS algoritmus), vzdálenost mezi řetězci, datová struktura Trie a použití
7. Komprese dat, rozdělení kompresních metod, princip kompresních metod (Huffmann, aritmetické kódování, LZW, JPG, fraktálová komprese)
8. Grafové algoritmy (cesta – Dijkstra, Floyd-Warshal, kostra – Prim-Jarnik), reprezentace grafu (matice, seznam sousednosti), základy kryptografie (symetrické, asymetrické šifrování)

ZOS

1. Rozdělení OS, architektura a komponenty OS
2. Základní funkce OS
3. Vyvolání služeb OS, zpracování přerušení
4. Proces, implementace procesu, konstrukce pro vytváření procesů
5. Paralelní procesy, prostředky pro popis paralelních procesů, vlákna
6. Problém kritické sekce
7. Prostředky pro synchronizaci procesů
8. Semafory, jejich použití a implementace
9. Monitory
10. Problém uvíznutí procesů, graf alokace zdrojů
11. Klasické problémy meziprocesové komunikace – producent-konzument aj.
12. Plánování úloh a procesů v dávkových systémech
13. Plánování procesů v interaktivních systémech
14. Správa hlavní paměti, metody přidělování paměti, virtuální paměť
15. Algoritmy nahrazování stránek paměti
16. Ovládání periferních zařízení, RAID
17. Systémy souborů
18. Kontrola konzistence souborového systému, mechanismy ochrany před neoprávněným přístupem