Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
mgr-szz:in-pds [2014/10/27 09:07] 127.0.0.1 upraveno mimo DokuWiki |
mgr-szz:in-pds [2020/04/12 16:56] (aktuální) |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
====== Státní magisterská zkouška v programu Informatika, obor Paralelní a distribuované systémy N-IN PDS ====== | ====== Státní magisterská zkouška v programu Informatika, obor Paralelní a distribuované systémy N-IN PDS ====== | ||
- | - [[mgr-szz:in-pds:1-pds|Hardwarové platformy pro paralelní výpočty a související typy paralelních algoritmů. Návrh paralelních algoritmů: míra a úroveň paralelizace, typy komunikace a jejich vlastnosti, synchronizace a serializace. Analýza paralelních algoritmů: zrychlení (speedup), škálovatelnost, komunikační složitost versus lokalita a jejich vliv na výkon paralelní implementace.]] | + | [[https://www.fi.muni.cz/studies/szz_mgr/pds2015.xhtml|Oficiální znění otázek]] |
- | - [[mgr-szz:in-pds:2-pds|Modely distribuovaných systémů - základní pojmy a pricipy, synchronní a asynchronní komunikace, složitostnímíry. Synchronizace. Detekce ukončení. Detekce chyb. Problém vzájemného vyloučení a problém uváznutí a jejich řešení.]] | + | |
- | - [[mgr-szz:in-pds:3-pds|Problém volby vedoucího prvku - vliv topologie a její znalosti/neznalosti na složitost řešení problému (kruh, úplný graf, úplný orientovaný graf, neznámá topologie); volba v anonymních sítích.]] | + | - [[mgr-szz:in-pds:1-pds|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.]] |
- | - [[mgr-szz:in-pds:4-pds|Sémantické ekvivalence procesů. Silná a slabá bisimulace, bisimulační ekvivalence, ekvivalence stop. Metody ověřování sémantických ekvivalencí procesů, axiomatizace konečných a konečně-stavových procesů v kalkulu CCS; aplikace (např. na komunikační protokoly).]] | + | - [[mgr-szz:in-pds:2-pds|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.]] |
- | - [[mgr-szz:in-pds:5-pds|Temporální logiky, logiky lineárního a větvícího se času a jejich fragmenty, porovnání vyjadřovací síly temporálních logik, axiomatizace a rozhodnutelnost.]] | + | - [[mgr-szz:in-pds:3-pds|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.]] |
- | - [[mgr-szz:in-pds:6-pds|Modální mu-kalkul, syntaxe a sémantika; operátory pevného bodu, alternace operátorů pevného bodu, výpočet pevných bodů pomocí aproximací.]] | + | - [[mgr-szz:in-pds:4-pds|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ů.]] |
- | - [[mgr-szz:in-pds:7-pds|Konečné automaty nad nekonečnými slovy a jimi rozpoznávané jazyky a jejich vlastnosti. Princip překladu formulí LTL na automaty nad nekonečnými slovy.]] | + | - [[mgr-szz:in-pds:5-pds|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.]] |
- | - [[mgr-szz:in-pds:8-pds|Formalismy pro popis nekonečně stavových přechodových systémů (algebry procesů, Petriho sítě, přepisovací systémy, automaty, procesové kalkuly), porovnání jejich vyjadřovací síly.]] | + | - [[mgr-szz:in-pds:6-pds|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ů.]] |
- | - [[mgr-szz:in-pds:9-pds|Rozhodnutelnost sémantických ekvivalencí pro různé třídy nekonečně stavových systémů. Složitost rozhodovacích algoritmů. Analýza dosažitelnosti, rozhodnutelnost, složitost algoritmů pro analýzu dosažitelnosti.]] | + | - [[mgr-szz:in-pds:7-pds|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í).]] |
- | - [[mgr-szz:in-pds:10-pds|Metoda ověřování modelu pro konečně stavové systémy a lineární temporální logiku: základní symbolické a explicitní algoritmy a jejich teoretická složitost.]] | + | - [[mgr-szz:in-pds:8-pds|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.]] |
- | - [[mgr-szz:in-pds:11-pds|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í).]] | + | - [[mgr-szz:in-pds:9-pds|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.]] |
- | - [[mgr-szz:in-pds:12-pds|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.]] | + | - [[mgr-szz:in-pds:10-pds|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:13-pds|Modelování a verifikace systémů reálného času. Teorie časových automatů. Temporální logiky s reálným časem. Programová podpora pro automatickou verifikaci. Komunikační protokoly s reálným časem a jejich verifikace.]] | + | |
- | - [[mgr-szz:in-pds:14-pds|Programování pro souběžné systémy a systémy reálného času. Základní principy: procesy, synchronizace, komunikace, čas. Podpora u existujících programovacích jazyků. Operační systémy reálného času.]] | + | |
- | - [[mgr-szz:in-pds:15-pds|Kryptografie. Použití základních symetrických algoritmů (AES), módy činnosti blokových šifer. Použití základních asymetrických algoritmů (RSA, DSA). Základní kryptografické protokoly. Správa veřejných klíčů, certifikační autority a infrastruktury veřejných klíčů.]] | + |