Stránka 1 z 1
NP-uplnost
Napsal: 3. 2. 2006 00:02
od Lada
Zdarek lidi, nevite o nejakem hezkem studijnim textu kde by byla vysvetlena NP - uplnost, prevadeni problemu a tak (proste o co tam vubec jde) na prednasku jsem chybel a ze slajdu fakt moc moudrej nejsem
nebo nemohli byste sem nekdo ofotit poznamky z prednasky??
Moc dekuju Ladis
Napsal: 3. 2. 2006 01:50
od Dast
NP uplnost je hezky vysvetlena v knize "Introduction to Algorithms" a take v ceske knize Alena Koubkova, Jan Pavelka "Uvod do teoreticke Informatiky". Jinak je toho plny internet.
Napsal: 3. 2. 2006 09:25
od hippies
Dast píše:NP uplnost je hezky vysvetlena v knize "Introduction to Algorithms" a take v ceske knize Alena Koubkova, Jan Pavelka "Uvod do teoreticke Informatiky". Jinak je toho plny internet.
Nevěděl bys o nějaké e-podobě (nemyslím tím erotickou
) těchto knížek? Docela by se mi to hodilo.
Napsal: 3. 2. 2006 21:23
od Lada
hmm, tak se zda ze si odpovim asi sam - nasel jsem celkem hezky studijni text (psany reci skoro normalnich lidi
) na
http://www.cs.vsb.cz/hlineny/vyuka/UTI ... ext05.pdf
NP je tam vysvetlena rekl bych dobre (pochopil jsem to z toho) zbytek jsem nezkoumal, ale myslim ze by to mohlo stat zato;)[/url]
Re:
Napsal: 4. 2. 2006 17:37
od Necroman
Sbírka několika zajímavých převodů, namátkou
3-SAT → IS - splnitelnost booleovských formulí s omezením na 3 literály na problém nezávislé množiny (Independent Set)
3-SAT → 3-CG - splnitelnost booleovských formulí s omezením na 3 literály na problém barvení grafu třemi barvami
HK → TSP - ex. hamiltonovské kružnice na problém obchodního cestujícího
IPKP → PKP - Postův Korespondenční Problém na Iniciální PKP
HP → IPKP - problém zastavení na Iniciální PKP