|
Title: NP - πληρότητα Post by: Fiodor on March 16, 2007, 16:36:27 pm Γνωρίζει κανείς για την NP - πληρότητα;
Αν ναι, ας εξηγήσει σύντομα ή ας βάλει κάποιο link σε κάποιο βιβλιο ή tutorial Thanks in advance, Fiodor Title: deleted Post by: BOBoMASTORAS on March 16, 2007, 16:38:44 pm deleted
Title: Re: NP - πληρότητα Post by: Fiodor on March 16, 2007, 16:44:56 pm Thanks a lot!
Μήπως έχει κανείς κάποιο από τα παρακάτω: # Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp.979–983. # Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp.241–271. # David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004. ή αν γνωρίζει με απλά λόγια πως μπορώ να αποδείξω αν ένα πρόβλημα είναι NP - πλήρες θα μου ήταν πολύ βοηθητικό... Title: Re: NP - πληρότητα Post by: Καμένος on March 16, 2007, 16:51:50 pm Έψαξες στην Αλεξάνδρεια μήπως υπάρχουν?
Title: Re: NP - πληρότητα Post by: Fiodor on March 16, 2007, 16:58:07 pm Δεν έχω λογαριασμό και δεν μπορώ να μπω σαν guest.
Αν δεν σου είναι κόπος ψάξε και ανεβασέ του στο φόρουμ. Thanks in advance... fiodor Title: deleted Post by: BOBoMASTORAS on March 16, 2007, 16:59:46 pm deleted
Title: deleted Post by: BOBoMASTORAS on March 16, 2007, 17:02:04 pm deleted
Title: Re: NP - πληρότητα Post by: elmaya on March 16, 2007, 17:02:21 pm Γνωρίζει κανείς για την NP - πληρότητα; Αν ναι, ας εξηγήσει σύντομα ή ας βάλει κάποιο link σε κάποιο βιβλιο ή tutorial Thanks in advance, Fiodor NP-complete (η και intractable προβλήματα) λέγεται εκείνη η κλάση προβλημάτων που ενώ γνωρίζουμε ότι είναι μαθηματικά επιλύσιμα (decidable), δηλαδή υπολογίζονται από κάποιο αλγόριθμο ή ισοδύναμα υλοποιούνται με ένα Turing Machine (που είναι το πιο απλό μοντέλο των υπολογιστών που χρησιμοποιούμε σήμερα), ο χρόνος επίλυσης τους είναι πολύ μεγάλος. Τόσο μεγάλος που μερικές φορές η ενέργεια που χρειαζόμαστε για την επίλυση τους ξεπερνάει την ενέργεια του σύμπαντος. Για αρχή ο Sipser είναι καλός, αλλα το παραμύθι που αφηγείται ο Παπαδημητριου με τον Lewis είναι άλλο πράμα (δύσκολο, αλλα φανταστικό) edit: Στην Αλεξάνδρεια υπάρχουν και τα δυο που αναφέρονται στη wikipedia Title: Re: NP - πληρότητα Post by: Fiodor on March 16, 2007, 17:03:53 pm Thanks guys...
|