Θεωρία Πολυπλοκότητας (ΠΛ1)
Από Wiki Τμήματος Μαθηματικών
Αναθεώρηση ως προς 17:08, 25 Νοεμβρίου 2022 από τον Mathwikiadmin (συζήτηση | συνεισφορές)
Γενικά
Σχολή | Σχολή Θετικών Επιστημών |
---|---|
Τμήμα | Τμήμα Μαθηματικών |
Επίπεδο Σπουδών | Μεταπτυχιακό |
Κωδικός Μαθήματος | ΠΛ1 |
Εξάμηνο | 1 |
Τίτλος Μαθήματος | ΘΕΩΡΙΑ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ |
Αυτοτελείς Διδακτικές Δραστηριότητες | Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 7.5) |
Τύπος Μαθήματος | Επιλογής |
Προαπαιτούμενα Μαθήματα | Απαραίτητες γνώσεις από 641-Σχεδίαση και Ανάλυση Αλγορίθμων |
Γλώσσα Διδασκαλίας και Εξετάσεων | Ελληνική |
Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus | Ναι (στην Αγγλική γλώσσα) |
Ηλεκτρονική Σελίδα Μαθήματος (URL) | Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων. |
Μαθησιακά Αποτελέσματα
Μαθησιακά Αποτελέσματα | Ο κύριος σκοπός του μαθήματος είναι η εισαγωγή στην έννοια της πολυπλοκότητας χρόνου και χώρου για την επίλυση δύσκολων προβλημάτων.
Μέθοδοι απόδειξης NP-πληρότητας προβλημάτων.
Στο μάθημα περιλαμβάνονται ατομικές ασκήσεις, περιληπτική συγγραφή και παρουσίαση σχετικών ερευνητικών εργασιών. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:
|
---|---|
Γενικές Ικανότητες |
|
Περιεχόμενο Μαθήματος
- ΝΡ και υπολογιστική δυσεπιλυσιμότητα
- Η κλάση PSPACE
- Επέκταση των ορίων επιλυσιμότητας
- Προσεγγιστικοί Αλγόριθμοι
- Τοπική Αναζήτηση
- Τυχαιοποιημένοι Αλγόριθμοι
Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση
Τρόπος Παράδοσης | Στην τάξη | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών | Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-class | ||||||||||
Οργάνωση Διδασκαλίας |
| ||||||||||
Αξιολόγηση Φοιτητών |
|
Συνιστώμενη Βιβλιογραφία
- Computational Complexity, Christos Papadimitriou.
- Computers and Intractability, M. R. Garey and D. S. Johnson.
- J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.