[Zk] Paralelní algoritmy 13. 6. 2014

tobik
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 5. 2011 18:10
Typ studia: Informatika Bc.

[Zk] Paralelní algoritmy 13. 6. 2014

Příspěvek od tobik »

Na začátku dal pan Mráz každému vylosovat dva lístečky, jeden s teoretickou otázkou a jeden praktický příklad k vyřešení. Otázek je tedy konečná množina a co se mi zdálo, tak se opakují i v rámci malé skupiny studentů. Co se týče mě, tak jsem dostal otázky:

Praktická: Vymyslet algoritmus, který vrátí počet komponent souvislosti v grafu.
Teoretická: Dokázat, že úloha, zda na vstupu daná bezkontextová gramatika dokáže vygenerovat prázdné slovo, je P-úplná, ale zároveň pro zafixovanou gramatiku (tedy není součástí vstupu), je problém v NC.

Řekl bych, že jsem měl jedno z těch lehčích zadání (zdálo se mi, že ostatní se s tím trápili mnohem více). Praktický příklad se dá vyřešit modifikací standardního algoritmu pro určení komponent (ten algoritmus vrátí pole vrcholů, kde u každého vrcholu je určeno číslo komponenty, tj. v podstatě hledám počet unikátních hodnot v poli. Řešil jsem to seřazením a na seřazené pole jsem aplikoval binární strom, tj. vezmu počet unikátních hodnot z levého a pravého podstromu a sečtu je, případně odečtu jedničku, pokud na hranici podstromů jsou stejné hodnoty). V té teoretické otázce jsou zakuklené dva podbody, jednak převod problému GEN na ty gramatiky, a jednak NC algoritmus rozpoznávání bezkontextového jazyka.

Mráz vyžaduje v podstatě jen znalost principu algoritmu (a asi je dobré si i pamatovat složitost), nicméně nevšiml jsem si, že by po někom chtěl něco dokazovat. Nevyžaduje ani přesnou znalost těch několika vět o zrychlení z úvodních přednášek. A obecně hodnotí mírně je schopný leccos odpustit.
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“