NP - πληρότητα

THMMY.gr > Forum > Ηλεκτρονικοί Υπολογιστές και Τεχνικά Θέματα > Περί Υπολογιστών... > Γενική συζήτηση, Απορίες, Τεχνολογικά Νεα, Εκθέσεις ... (Moderators: chatzikys, PolarBear) > NP - πληρότητα

0 Members and 1 Guest are viewing this topic.

Pages: [1]

Author

Topic: NP - πληρότητα (Read 1981 times)

Fiodor

Νεούλης/Νεούλα

Gender:

Posts: 46

NP - πληρότητα

« on: March 16, 2007, 16:36:27 pm »

Γνωρίζει κανείς για την NP - πληρότητα;

Αν ναι, ας εξηγήσει σύντομα ή ας βάλει κάποιο link σε κάποιο βιβλιο ή tutorial

Thanks in advance,

Fiodor


	Logged

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

deleted

« Reply #1 on: March 16, 2007, 16:38:44 pm »

deleted


« Last Edit: June 14, 2015, 21:27:41 pm by BOBoMASTORAS »	Logged

Της γενιάς μου βασιλιά,
μην κατέβεις τα σκαλιά.
Πιες αθάνατο νερό
να νικήσεις τον καιρό.

http://tools.ietf.org/html/rfc1149
The only reason we invent robots

Fiodor

Νεούλης/Νεούλα

Gender:

Posts: 46

Re: NP - πληρότητα

« Reply #2 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 - πλήρες θα μου ήταν πολύ βοηθητικό...


	Logged

Καμένος

Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 2322

Re: NP - πληρότητα

« Reply #3 on: March 16, 2007, 16:51:50 pm »

Έψαξες στην Αλεξάνδρεια μήπως υπάρχουν?


	Logged

Fiodor

Νεούλης/Νεούλα

Gender:

Posts: 46

Re: NP - πληρότητα

« Reply #4 on: March 16, 2007, 16:58:07 pm »

Δεν έχω λογαριασμό και δεν μπορώ να μπω σαν guest.

Αν δεν σου είναι κόπος ψάξε και ανεβασέ του στο φόρουμ.

Thanks in advance...

fiodor


	Logged

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

deleted

« Reply #5 on: March 16, 2007, 16:59:46 pm »

deleted


« Last Edit: June 14, 2015, 21:27:36 pm by BOBoMASTORAS »	Logged

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

deleted

« Reply #6 on: March 16, 2007, 17:02:04 pm »

deleted


« Last Edit: June 14, 2015, 21:27:34 pm by BOBoMASTORAS »	Logged

elmaya

Guest

Re: NP - πληρότητα

« Reply #7 on: March 16, 2007, 17:02:21 pm »

Quote from: Fiodor on March 16, 2007, 16:36:27 pm

NP-complete (η και intractable προβλήματα) λέγεται εκείνη η κλάση προβλημάτων που ενώ γνωρίζουμε ότι είναι μαθηματικά επιλύσιμα (decidable), δηλαδή υπολογίζονται από κάποιο αλγόριθμο ή ισοδύναμα υλοποιούνται με ένα Turing Machine (που είναι το πιο απλό μοντέλο των υπολογιστών που χρησιμοποιούμε σήμερα), ο χρόνος επίλυσης τους είναι πολύ μεγάλος. Τόσο μεγάλος που μερικές φορές η ενέργεια που χρειαζόμαστε για την επίλυση τους ξεπερνάει την ενέργεια του σύμπαντος.

Για αρχή ο Sipser είναι καλός, αλλα το παραμύθι που αφηγείται ο Παπαδημητριου με τον Lewis είναι άλλο πράμα (δύσκολο, αλλα φανταστικό)

edit: Στην Αλεξάνδρεια υπάρχουν και τα δυο που αναφέρονται στη wikipedia


« Last Edit: March 17, 2007, 18:18:20 pm by elmaya »	Logged

Fiodor

Νεούλης/Νεούλα

Gender:

Posts: 46

Re: NP - πληρότητα

« Reply #8 on: March 16, 2007, 17:03:53 pm »

Thanks guys...


	Logged

Pages: [1]

Jump to: