Οδηγός Καθοδήγησης Μελέτης: Χρονική Πολυπλοκότητα – ΝΡ-πλήρη προβλήματα

 
This item is provided by the institution :

Repository :
Institutional Repository of the Hellenic Open University
see the original item page
in the repository's web site and access all digital files if the item*
share



Semantic enrichment by EKT
2008 (EN)
Οδηγός Καθοδήγησης Μελέτης: Χρονική Πολυπλοκότητα – ΝΡ-πλήρη προβλήματα
ΣΤΑΥΡΟΠΟΥΛΟΣ, ΗΛΙΑΣ (ΔΙΔΑΚΤΩΡ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟΥ ΑΝΟΙΚΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ)
ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
ΠΑΠΑΡΡΙΖΟΣ, ΚΩΝΣΤΑΝΤΙΝΟΣ (ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΜΑΚΕΔΟΝΙΑΣ)
Το παρόν υλικό αποτελεί έναν οδηγό καθοδήγησης μελέτης του υπάρχοντος έντυπου εκπαιδευτικού υλικού. Μελετώντας το ο φοιτητής θα μπορέσει να εντοπίσει και να κατανοήσει τις βασικότερες έννοιες που αφορούν την Χρονική Πολυπλοκότητα και την ΝΡ-πληρότητα (Κεφάλαια 7, 8 του Τόμου Α΄ και Κεφάλαιο 3 του Τόμου Β΄). Το υλικό βελτιώνει και συμπληρώνει το υπάρχον έντυπο εκπαιδευτικό υλικό αναφορικά με αποδείξεις προτάσεων και παραδείγματα ΝΠ-πλήρων προβλημάτων. Γίνονται εκτεταμένες αναφορές σε εδάφια του υπάρχοντος εκπαιδευτικού υλικού και γίνονται επιπρόσθετες αναλύσεις αυτών. Η μελέτη του υλικού αυτού θα καθοδηγήσει τον φοιτητή στον τρόπο μελέτης του υπάρχοντος εκπαιδευτικού υλικού.
Το παρόν αποτελεί έναν οδηγό καθοδήγησης μελέτης αναφορικά με τις Κλάσεις Χρονικής Πολυπλοκότητας και την ΝΡ-πληρότητα. Αφορά βασικές έννοιες των παραπάνω θεματικών περιοχών και παραλλαγές του υπολογιστικά δύσκολου προβλήματος της ικανοποιησιμότητας Λογικών εκφράσεων.
Hypertext
μηχανές turing, ντετερμινιστικός υπολογισμός, μη ντετερμινιστικός υπολογισμός, χρονική πολυπλοκότητα, κλάσεις χρονικής πολυπλοκότητας, κλειστότητα κλάσεων πολυπλοκότητας, ΝΡ-πληρότητα, ικανοποιησιμότητα λογικών εκφράσεων, turing machines, deterministic computation, non deterministic computation, time complexity, time complexity classes, closeness, NP-completeness satisfiability of boolean expressions (SAT)
Hellenic Open University
Institutional Repository of the Hellenic Open University
Greek
2008
2013-12-13T14:48:24Z
2009-03-09T09:15:17Z
http://apothesis.eap.gr/handle/eap/650
Οι εκτιμώμενοι χρόνοι μελέτης αφορούν στην περίπτωση όπου ο φοιτητής έχει ήδη μελετήσει το έντυπο εκπαιδευτικό υλικό (Κεφάλαια 7, 8 του Τόμου Α΄ και Κεφάλαιο 3 του Τόμου Β΄) σύμφωνα με το Χρονοδιάγραμμα Μελέτης και Γραπτών εργασιών της Θεματικής Ενότητας. Ο εκτιμώμενος χρόνος μελέτης είναι συνολικά 20 ώρες. Συγκεκριμένα, για την ενότητα της Χρονικής Πολυπλοκότητας, 2 ώρες για κάθε ένα ερώτημα και για την ενότητα των ΝΡ-πλήρων προβλημάτων, 1 ώρα για κάθε ένα από τα 4 πρώτα προβλήματα και 1.5 ώρες για κάθε ένα από 4 τελευταία ερωτήματα. (66 Σελίδες + 43 Εικόνες)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)