home
mgr-szz
ap-ap
ap-bio
ap-obr
ap-ssme
in-bit
in-emba
in-gra
in-ins
in-pds
1-pds
2-pds
5-pds
6-pds
7-pds
9-pds
in-pos
in-psk
in-tei
in-umi-ai
in-uni-nlp
ap-ap
ap-bio
ap-obr
ap-ssme
in-bit
in-emba
in-gra
in-ins
in-pds
in-pos
in-psk
in-tei
in-umi-ai
in-umi-nlp
playground
wiki
home
mgr-szz
hledat
Hledat
Mapa stránek
Správa médií
Poslední úpravy
Zpětné odkazy
Přihlásit se
Státnice na FI MUNI
Zdrojový kód stránky
Starší verze
Historie:
•
in-pds
Umístění:
home
»
mgr-szz
»
in-pds
Státní magisterská zkouška v programu Informatika, obor Paralelní a distribuované systémy N-IN PDS
Oficiální znění otázek
Grafy a grafové algoritmy. Formalizace základních grafových pojmů, reprezentace grafů. Souvislost grafu, barevnost, rovinné grafy. Algoritmy (včetně složitosti a základní myšlenky důkazů korektnosti): prohledávání grafu do šířky a do hloubky, nejkratší vzdálenosti, kostry, toky v sítích.
Matematická logika. Výroková a predikátová logika, syntaxe, sémantika. Odvozovací systémy, formální důkazy. Korektnost a úplnost odvozovacích systémů. Gödelovy věty o neúplnosti.
Konečné automaty (FA) a logiky nad slovy. Logika 1.řádu (FOL) a monadická logika 2.řádu (MSOL): syntax a sémantika FOL a MSOL, principy převoditelnosti mezi FA a formulemi MSOL. Automaty nad nekonečnými slovy a omega-regulární jazyky.
Operační, denotační, a axiomatická sémantika programovacích jazyků. CPO, věta o pevném bodě a její použití. Hoareova logika, její korektnost a úplnost. Temporální logiky lineárního a větvícího se času a jejich fragmenty, sémantika neukončených a paralelních programů.
Metoda ověřování modelu (MC) pro konečně stavové systémy a lineární temporální logiku. Princip překladu formulí LTL na automaty nad nekonečnými slovy. Základní symbolické a explicitní algoritmy pro MC a jejich teoretická složitost.
Formalismy pro modelování nekonečně stavových systémů (Petriho sítě, procesové přepisovací systémy, automaty, procesové kalkuly) a algebry procesů, porovnání jejich vyjadřovací síly vzhledem k bisimulaci. Vybrané rozhodnutelné problémy z oblasti verifikace těchto systémů.
Specifické techniky pro verifikaci softwarových systémů, abstraktní interpretace, metody abstrakce a aproximace, redukce částečným uspořádáním, metody zjemňování abstrakcí (např. CEGAR – protipříkladem řízené zjemňování abstrakcí).
Systémy reálného času. Měkké a tvrdé systémy. Plánování v systémech reálného času: plánování s periodickými úkoly, plánování založené na prioritách, přístup ke sdíleným zdrojům.
Modely distribuovaných systémů - základní pojmy a pricipy, synchronní a asynchronní komunikace. Synchronizace. Detekce ukončení. Problém vzájemného vyloučení a problém uváznutí a jejich řešení. Problém volby vedoucího prvku - vliv topologie a její znalosti/neznalosti na složitost řešení problému.
Počítačové sítě - základní pojmy, principy, architektury. Spojované a nespojované sítě, OSI model, protokoly v prostředí Internetu. Směrování, základní služby počítačových sítí, správa a bezpečnost sítí.
mgr-szz/in-pds.txt
· Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
hledat
hledat