Fórum studentů MFF UK

Ustni co jsem zase dostal ja - prevod 3 SAT - 3 BAREVNOST, silna NPU, slaba NPU.
Prevod v pohode, v ty silny jsme mu rikal vsechno kolem pseudopolynomialnich alg a ciselnych problemu, ale chtel slyset slovicka UPAS (proste jen to, dost mne to dostalo po delsi debate). Jednoho cloveka vyhodil na Cook-Levin vete (rekl jen tohle, clovek rekl ze nevi co to je a tak sel, mozna stacilo rict ze jde o kachlikovani). Pak jsem jeste slysel konsolidaci na Fib. halde.

Vsechno Kucera, co jsme pak debatovali, tak mi prijde Cepek na zkouseni lepsi.

Pisomka:
(v zatvorke je cislo zo zoznamu skuskovych prikladov, podrobnejsie na [url]http://forum.matfyz.info/viewtopic.php?f=203&t=5021[/url])

(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