NP - πληρότητα

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Fiodor]

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

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

Thanks in advance,

Fiodor

[BOBoMASTORAS]

deleted

[Fiodor]

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

[Καμένος]

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

[Fiodor]

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

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

Thanks in advance...

fiodor

[BOBoMASTORAS]

deleted

[BOBoMASTORAS]

deleted

[elmaya]

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

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

Thanks in advance,

Fiodor

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

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

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

[Fiodor]

Thanks guys...