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
NP-uplnost
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
NP-uplnost
Hail to you, champion:o)
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
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]
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]
Hail to you, champion:o)
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Re:
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
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
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat