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

 
Το τεκμήριο παρέχεται από τον φορέα :

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



Σημασιολογικός εμπλουτισμός από το EKT
2008 (EL)
Οδηγός Καθοδήγησης Μελέτης: Χρονική Πολυπλοκότητα – ΝΡ-πλήρη προβλήματα
ΣΤΑΥΡΟΠΟΥΛΟΣ, ΗΛΙΑΣ (ΔΙΔΑΚΤΩΡ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟΥ ΑΝΟΙΚΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ)
ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
ΠΑΠΑΡΡΙΖΟΣ, ΚΩΝΣΤΑΝΤΙΝΟΣ (ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΜΑΚΕΔΟΝΙΑΣ)
Το παρόν υλικό αποτελεί έναν οδηγό καθοδήγησης μελέτης του υπάρχοντος έντυπου εκπαιδευτικού υλικού. Μελετώντας το ο φοιτητής θα μπορέσει να εντοπίσει και να κατανοήσει τις βασικότερες έννοιες που αφορούν την Χρονική Πολυπλοκότητα και την ΝΡ-πληρότητα (Κεφάλαια 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)
Ελληνικό Ανοικτό Πανεπιστήμιο
Ιδρυματικό Αποθετήριο Ελληνικου Ανοικτού Πανεπιστημίου
Ελληνική γλώσσα
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 Εικόνες)



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