NP-uplnost

Uživatelský avatar
Lada
Donátor
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

Příspěvek 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 :cry:
nebo nemohli byste sem nekdo ofotit poznamky z prednasky??

Moc dekuju Ladis
Hail to you, champion:o)
Dast
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 30. 1. 2005 14:37
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Příspěvek 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.
-- Dalibor Straka
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek 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 :lol: ) těchto knížek? Docela by se mi to hodilo.
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Příspěvek od Lada »

hmm, tak se zda ze si odpovim asi sam - nasel jsem celkem hezky studijni text (psany reci skoro normalnich lidi :wink: ) 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]
Hail to you, champion:o)
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re:

Příspěvek 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
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Odpovědět

Zpět na „2005“