[Skuska] 10.2.2009
Napsal: 10. 2. 2009 18:09
Pisomka:
(v zatvorke je cislo zo zoznamu skuskovych prikladov, podrobnejsie na http://forum.matfyz.info/viewtopic.php?f=203&t=5021)
(6) 1. Dokazte nebo vyvratte: Mejme orientovany graf, ve kterem $ orientovana cesta mezi vrcholy U→V, pricemz pri prochazeni grafem narazilo DFS jako prvni na U. Pak V je v nejakem DFS stromu potomkem (ne nutne primym) U.
(7) 2. Mejme formuli F v CNF, kde se kazda promenna (ne literal!) vyskytuje nejvyse dvakrat. Otazka: Je formule F splnitelna? Vyreste 2R-SAT v polynomialnim case, uvedte asymptotickou slozitost.
(8) 3. Sablony
Ustna (co som pocul):
- planarny separator, #P, UPAS, algoritmus na 2-suvislost, prevod VP na HK, pseudopolynomialne algoritmy
(v zatvorke je cislo zo zoznamu skuskovych prikladov, podrobnejsie na http://forum.matfyz.info/viewtopic.php?f=203&t=5021)
(6) 1. Dokazte nebo vyvratte: Mejme orientovany graf, ve kterem $ orientovana cesta mezi vrcholy U→V, pricemz pri prochazeni grafem narazilo DFS jako prvni na U. Pak V je v nejakem DFS stromu potomkem (ne nutne primym) U.
(7) 2. Mejme formuli F v CNF, kde se kazda promenna (ne literal!) vyskytuje nejvyse dvakrat. Otazka: Je formule F splnitelna? Vyreste 2R-SAT v polynomialnim case, uvedte asymptotickou slozitost.
(8) 3. Sablony
Ustna (co som pocul):
- planarny separator, #P, UPAS, algoritmus na 2-suvislost, prevod VP na HK, pseudopolynomialne algoritmy