Treba da pripremim 20 NP problema sa dokazima tako ako ko ima sta korisno za preporuciti bio bi mu veoma zahvalan!
NP problems
-
problemboy
- Posts: 13
- Joined: 16/10/2009 15:13
#1 NP problems
Mozeli mi ko preporuciti dobru knjigu na netu koja se bavi prvenstveno NP problemima?
Treba da pripremim 20 NP problema sa dokazima tako ako ko ima sta korisno za preporuciti bio bi mu veoma zahvalan!
Treba da pripremim 20 NP problema sa dokazima tako ako ko ima sta korisno za preporuciti bio bi mu veoma zahvalan!
-
nellington
- Posts: 10761
- Joined: 11/03/2008 13:32
- Location: navedeno lice se udaljilo u nepoznatom pravcu.
#2 Re: NP problems
NP ili NP-kompletnih?
-
nellington
- Posts: 10761
- Joined: 11/03/2008 13:32
- Location: navedeno lice se udaljilo u nepoznatom pravcu.
#4 Re: NP problems
Baš me zadevera - nigdje kod sebe u literaturi ne nađoh na sličnu referencu. Ali na wikipediji recimo imaš čitavu kategoriju sa NP-kompletnim (potpunim) problemima - kako je NP-potpun ipak NP problem, ne vidim razlog da ne uzmeš materijal otamo 
-
problemboy
- Posts: 13
- Joined: 16/10/2009 15:13
#5 Re: NP problems
Pa eto izgleda da mi je ta opcija jedina preostala. wikipedia mi je nekako previse opcenita a nikako konkretna. Postoji li na netu, ili ako imas kakav link, nekakva knjiga koja se bavi samo tim problemima.. Pa neka su u pitanju i np kompletni problemi. Nekako u svim knjigama se samo za neke probleme onako usput kaze ovo je np kompletan problem i dovidjenja. Treba mi neka knjiga gdje je neko tu temu detaljno razradio... 
-
nellington
- Posts: 10761
- Joined: 11/03/2008 13:32
- Location: navedeno lice se udaljilo u nepoznatom pravcu.
#6 Re: NP problems
Ima knjiga, samo ne znam koliko je dostupna (ja sam samo čuo za nju - izračunljivost i algoritmi nisu baš moj fah)
Computers and Intractability: A Guide to the Theory of NP-Completeness
Computers and Intractability: A Guide to the Theory of NP-Completeness
-
saga
- Posts: 1180
- Joined: 14/05/2007 22:23
#7 Re: NP problems
pored ovog Garey-a (valjda je to to) sto je nellington naveo pogledaj i
Papadimitriou C.H, Steiglitz K. Combinatorial Optimization. Algorithms and Complexity
Papadimitriou C.H, Steiglitz K. Combinatorial Optimization. Algorithms and Complexity
-
nellington
- Posts: 10761
- Joined: 11/03/2008 13:32
- Location: navedeno lice se udaljilo u nepoznatom pravcu.
#8 Re: NP problems
Jeste, ovo je Gareyeva knjiga. Pogledao sam sinoć njen sadržaj: ima sjajan dodatak od 100 strana sa par stotina NP-potpunih problema.
A ova tvoja je dostupna i na googlebooks za kakav-takav pregled, pa postavljač teme može pogledati šta mu treba.
A ova tvoja je dostupna i na googlebooks za kakav-takav pregled, pa postavljač teme može pogledati šta mu treba.
-
saga
- Posts: 1180
- Joined: 14/05/2007 22:23
#9 Re: NP problems
ima u Papadimitriou pravo finih dokaza NP-complete problema
a inace se obje knjige imaju skinut na www.gigapedia.org
a inace se obje knjige imaju skinut na www.gigapedia.org
-
Ajatolah_
- Posts: 8611
- Joined: 11/02/2009 15:21
#10 Re: NP problems
Computers and Intractability: A Guide to the Theory of NP-completeness (A Series of books in the mathematical sciences)
This book's introduction features a humorous story of a man with a line of people behind him, who explains to his boss, "I can't find an efficient algorithm, but neither can all these famous people." This man illustrates an important quality of a class of problems, namely, the NP-complete problems: if you can prove that a problem is in this class, then it has no known polynomial-time solution that is guaranteed to work in general. This quality implies that the problem is difficult to deal with in practice. The focus of this book is to teach the reader how to identify, deal with, and understand the essence of NP-complete problems; Computers and Intractability does all of those things effectively. In a readable yet mathematically rigorous manner, the book covers topics such as how to prove that a given problem is NP-complete and how to cope with NP-complete problems. (There is even a chapter on advanced topics, with numerous references.) Computers and Intractability also contains a list of more than 300 problems--most of which (dakle, ne sve
, valjda će se naći nešto što ti odgovara) are known to be NP-complete--with comments and references.
Download Links:
http://hotfile.com/dl/18564187/e903d5f/ ... 7.rar.html
http://www.filezlot.com/m43110yizs64/07 ... 7.rar.html
http://hotfile.com/dl/35261387/1293092/ ... 7.rar.html
This book's introduction features a humorous story of a man with a line of people behind him, who explains to his boss, "I can't find an efficient algorithm, but neither can all these famous people." This man illustrates an important quality of a class of problems, namely, the NP-complete problems: if you can prove that a problem is in this class, then it has no known polynomial-time solution that is guaranteed to work in general. This quality implies that the problem is difficult to deal with in practice. The focus of this book is to teach the reader how to identify, deal with, and understand the essence of NP-complete problems; Computers and Intractability does all of those things effectively. In a readable yet mathematically rigorous manner, the book covers topics such as how to prove that a given problem is NP-complete and how to cope with NP-complete problems. (There is even a chapter on advanced topics, with numerous references.) Computers and Intractability also contains a list of more than 300 problems--most of which (dakle, ne sve
, valjda će se naći nešto što ti odgovara) are known to be NP-complete--with comments and references.Download Links:
http://hotfile.com/dl/18564187/e903d5f/ ... 7.rar.html
http://www.filezlot.com/m43110yizs64/07 ... 7.rar.html
http://hotfile.com/dl/35261387/1293092/ ... 7.rar.html