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

  1. Ψηφιακό τεκμήριο (Έγγραφο)
  2. ΠΛΗ30 Ψηφιακό Εκπαιδευτικό Υλικό (ΨΕΥ)
  3. Ελληνικά
  4. ΣΤΑΥΡΟΠΟΥΛΟΣ, ΗΛΙΑΣ (ΔΙΔΑΚΤΩΡ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟΥ ΑΝΟΙΚΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ)
  5. ΠΑΠΑΡΡΙΖΟΣ, ΚΩΝΣΤΑΝΤΙΝΟΣ (ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΜΑΚΕΔΟΝΙΑΣ)
  6. ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
  7. ΠΑΠΑΡΡΙΖΟΣ, ΚΩΝΣΤΑΝΤΙΝΟΣ (ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΜΑΚΕΔΟΝΙΑΣ)
  8. Οι εκτιμώμενοι χρόνοι μελέτης αφορούν στην περίπτωση όπου ο φοιτητής έχει ήδη μελετήσει το έντυπο εκπαιδευτικό υλικό (Κεφάλαια 7, 8 του Τόμου Α΄ και Κεφάλαιο 3 του Τόμου Β΄) σύμφωνα με το Χρονοδιάγραμμα Μελέτης και Γραπτών εργασιών της Θεματικής Ενότητας. Ο εκτιμώμενος χρόνος μελέτης είναι συνολικά 20 ώρες. Συγκεκριμένα, για την ενότητα της Χρονικής Πολυπλοκότητας, 2 ώρες για κάθε ένα ερώτημα και για την ενότητα των ΝΡ-πλήρων προβλημάτων, 1 ώρα για κάθε ένα από τα 4 πρώτα προβλήματα και 1.5 ώρες για κάθε ένα από 4 τελευταία ερωτήματα. (66 Σελίδες + 43 Εικόνες)
    • Το παρόν υλικό αποτελεί έναν οδηγό καθοδήγησης μελέτης του υπάρχοντος έντυπου εκπαιδευτικού υλικού. Μελετώντας το ο φοιτητής θα μπορέσει να εντοπίσει και να κατανοήσει τις βασικότερες έννοιες που αφορούν την Χρονική Πολυπλοκότητα και την ΝΡ-πληρότητα (Κεφάλαια 7, 8 του Τόμου Α΄ και Κεφάλαιο 3 του Τόμου Β΄). Το υλικό βελτιώνει και συμπληρώνει το υπάρχον έντυπο εκπαιδευτικό υλικό αναφορικά με αποδείξεις προτάσεων και παραδείγματα ΝΠ-πλήρων προβλημάτων. Γίνονται εκτεταμένες αναφορές σε εδάφια του υπάρχοντος εκπαιδευτικού υλικού και γίνονται επιπρόσθετες αναλύσεις αυτών. Η μελέτη του υλικού αυτού θα καθοδηγήσει τον φοιτητή στον τρόπο μελέτης του υπάρχοντος εκπαιδευτικού υλικού.
  9. Το υλικό αυτό αφορά στα Κεφάλαια 7 και 8 του Τόμου Α΄ καθώς και στο Κεφάλαιο 3 του Τόμου Β΄. Ο φοιτητής μπορεί εναλλακτικά, είτε να μελετήσει αρχικά τα Κεφάλαια αυτά σύμφωνα με το Χρονοδιάγραμμα Μελέτης και Γραπτών Εργασιών της Ενότητας και στη συνέχεια να μελετήσει το υλικό αυτό, είτε να μελετήσει πρώτα το παρόν υλικό και στη συνέχεια να μελετήσει τα αντίστοιχα Κεφάλαια. Στην πρώτη περίπτωση με την μελέτη του παρόντος υλικού ο φοιτητής θα έχει τη δυνατότητα να εντοπίσει κεντρικά σημεία που θα πρέπει να γνωρίζει και να τα κατανοήσει σε βάθος (αφού το παρόν υλικό κάνει συνεχείς αναφορές σε έννοιες που έχει ήδη μελετήσει μέσω του υπάρχοντος έντυπου εκπαιδευτικού υλικού). Στην δεύτερη περίπτωση, ο φοιτητής καλείτε να συναντήσει για πρώτη φορά άγνωστες σε αυτόν έννοιες τις οποίες θα κατανοήσει μέσω του υλικού αλλά και μέσω παραπομπών στο υπάρχον έντυπο εκπαιδευτικό υλικό. Σε κάθε περίπτωση ο φοιτητής έχει τη δυνατότητα να αποκτήσει εξοικείωση και εμπειρία στην απόδειξη ΝΡ-πλήρων προβλημάτων, μέσω παραδειγμάτων που συμπληρώνουν τα αντίστοιχα Κεφάλαια του υπάρχοντος έντυπου εκπαιδευτικού υλικού.
  10. μηχανές turing, ντετερμινιστικός υπολογισμός, μη ντετερμινιστικός υπολογισμός, χρονική πολυπλοκότητα, κλάσεις χρονικής πολυπλοκότητας, κλειστότητα κλάσεων πολυπλοκότητας, ΝΡ-πληρότητα, ικανοποιησιμότητα λογικών εκφράσεων, turing machines, deterministic computation, non deterministic computation, time complexity, time complexity classes, closeness, NP-completeness satisfiability of boolean expressions (SAT)