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

 
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



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

ΣΤΑΥΡΟΠΟΥΛΟΣ, ΗΛΙΑΣ (ΔΙΔΑΚΤΩΡ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟΥ ΑΝΟΙΚΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ)

ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
ΠΑΠΑΡΡΙΖΟΣ, ΚΩΝΣΤΑΝΤΙΝΟΣ (ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΜΑΚΕΔΟΝΙΑΣ)

Το παρόν υλικό αποτελεί έναν οδηγό καθοδήγησης μελέτης του υπάρχοντος έντυπου εκπαιδευτικού υλικού. Μελετώντας το ο φοιτητής θα μπορέσει να εντοπίσει και να κατανοήσει τις βασικότερες έννοιες που αφορούν την Χρονική Πολυπλοκότητα και την ΝΡ-πληρότητα (Κεφάλαια 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)

Ελληνικό Ανοικτό Πανεπιστήμιο (EL)
Hellenic Open University (EN)

2008
2013-12-13T14:48:24Z
2009-03-09T09:15:17Z


Οι εκτιμώμενοι χρόνοι μελέτης αφορούν στην περίπτωση όπου ο φοιτητής έχει ήδη μελετήσει το έντυπο εκπαιδευτικό υλικό (Κεφάλαια 7, 8 του Τόμου Α΄ και Κεφάλαιο 3 του Τόμου Β΄) σύμφωνα με το Χρονοδιάγραμμα Μελέτης και Γραπτών εργασιών της Θεματικής Ενότητας. Ο εκτιμώμενος χρόνος μελέτης είναι συνολικά 20 ώρες. Συγκεκριμένα, για την ενότητα της Χρονικής Πολυπλοκότητας, 2 ώρες για κάθε ένα ερώτημα και για την ενότητα των ΝΡ-πλήρων προβλημάτων, 1 ώρα για κάθε ένα από τα 4 πρώτα προβλήματα και 1.5 ώρες για κάθε ένα από 4 τελευταία ερωτήματα. (66 Σελίδες + 43 Εικόνες)



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.