Zkouška - 18. 12. 2014 - Čepek

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Erim
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 18. 12. 2014 12:28
Typ studia: Informatika Bc.

Zkouška - 18. 12. 2014 - Čepek

Příspěvek od Erim »

Zkouška 18. 12. 2014

1) Aho-Corasick:

Slova: {okolo, lom, luk, omyl}
Nakreslete graf znázorňující stavy a přechodovou funkci. Zpětnou a výstupní fci zapište tabulkou.

2) Minimální pokrytí grafu pomocí orientovaných cest

G = (V, E) acyklický orientovaný graf

Problém: Najděte polynomiální algoritmus, který v G nalezne minimální počet vrcholově disjunktních orientovaných cest, které pokryjí všechny vrcholy G.

3) Hamiltonovská cesta

G = (V, E) neorientovaný graf
s, k \in V

Problém HC: Existuje v G cesta z s do k, která navštíví každý další vrchol G právě jednou?

Otázka: Je tato úloha NP-úplná? Dokažte pomocí nějaké úlohy, kterou jsme brali na přednášce (KLIKA, HK, TSP, ROZ, ....)

Ústní část:
Třídící sítě - hloubka mergesortu
Toky v sítích - preflow-push algoritmy
Naposledy upravil(a) Erim dne 12. 1. 2015 20:54, celkem upraveno 1 x.
Pavel Brožek
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 15. 12. 2014 15:56
Typ studia: Informatika Bc.

Re: Zkouška - 18. 12. 2014 - Čepek

Příspěvek od Pavel Brožek »

2) Nebylo ještě v zadání, že ten graf je acyklický?
Erim
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 18. 12. 2014 12:28
Typ studia: Informatika Bc.

Re: Zkouška - 18. 12. 2014 - Čepek

Příspěvek od Erim »

Pavel Brožek píše:2) Nebylo ještě v zadání, že ten graf je acyklický?
Nevzpomínám si, ale nejspíš to bude pravda. Algoritmus, který jsem použil (hledání maximálního toku v bipartitním grafu), by si s cykly neuměl poradit a nenašel by vždy nejmenší pokrytí, přesto mi byl uznán, takže v testu tento předpoklad nejspíš byl.
Díky za otázku, změním první zprávu.
Pavel Brožek
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 15. 12. 2014 15:56
Typ studia: Informatika Bc.

Re: Zkouška - 18. 12. 2014 - Čepek

Příspěvek od Pavel Brožek »

Shodou okolností jsem u zkoušky dostal přesně tohle zadání a skutečně v zadání bylo, že je graf acyklický :)
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“