| Τίτλος | ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY |
| Κωδικός | NGE-07-01 |
| Σχολή | Θετικών Επιστημών |
| Τμήμα | Πληροφορικής |
| Κύκλος / Επίπεδο | 1ος / Προπτυχιακό |
| Περίοδος Διδασκαλίας | Χειμερινή |
| Υπεύθυνος/η | Γεώργιος Χριστοδούλου |
| Κοινό | Όχι |
| Κατάσταση | Ενεργό |
| Course ID | 40002972 |
Πρόγραμμα Σπουδών: ΠΠΣ-Τμήμα Πληροφορικής (2019-σήμερα)
Εγγεγραμμένοι φοιτητές: 23
| Κατεύθυνση | Τύπος Παρακολούθησης | Εξάμηνο | Έτος | ECTS |
|---|---|---|---|---|
| ΓΕΝΙΚΗ ΚΑΤΕΥΘΥΝΣΗ | ΥΠΟΧΡΕΩΤΙΚΟ ΚΑΤΑ ΕΠΙΛΟΓΗ | 7 | 4 | 5 |
| Τίτλος | ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ |
| Ακαδημαϊκό Έτος | 2019 – 2020 |
| Περίοδος Τάξης | Χειμερινή |
| Διδάσκοντες άλλων Κατηγοριών | |
| Ώρες Εβδομαδιαία | 3 |
| Class ID | 600154416
|
Τύπος Μαθήματος 2016-2020
- Υποβάθρου
- Γενικών Γνώσεων
- Επιστημονικής Περιοχής
Τύπος Μαθήματος 2011-2015
Ειδικού Υποβάθρου / Κορμού
Τρόπος Παράδοσης
- Πρόσωπο με πρόσωπο
Ηλεκτρονική Διάθεση Μαθήματος
- e-Οδηγός Σπουδών https://qa.auth.gr/el/class/1/600154416
- eLearning: https://elearning.auth.gr/course/view.php?id=8618
Erasmus
Το μάθημα προσφέρεται και σε φοιτητές
προγραμμάτων ανταλλαγής.
Γλώσσα Διδασκαλίας
- Ελληνικά (Διδασκαλία, Εξέταση)
- Αγγλικά (Εξέταση)
Προαπαιτήσεις
Προαπαιτούμενα Μαθήματα
- NCO-01-04 ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ
- NCO-02-02 ΠΙΘΑΝΟΤΗΤΕΣ & ΣΤΑΤΙΣΤΙΚΗ
- NCO-02-03 ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ
- NCO-04-03 ΑΛΓΟΡΙΘΜΟΙ
Μαθησιακά Αποτελέσματα
Γνωστικά: Κατανόηση της αντιστοίχησης προβλημάτων σε αλγοριθμικές λύσεις (για παράδειγμα ως προβλημάτων γράφων). Κατανόηση των περιορισμών απόδοσης αλγορίθμων για συγκεκριμένες κατηγορίες προβλημάτων. Εξοικείωση με διαφορετικές κλάσεις πολυπλοκότητας (P, NP, NP πλήρης, NP δύσκολη, PSPACE). Εκμάθηση διαφορετικών τεχνικών επίλυσης δύσκολων προβλήματων μέσω της χρήσης αλγορίθμων (εκθετικοί αλγόριθμοι, προσεγγιστικοί αλγόριθμοι, τυχαιοποιημένοι αλγόριθμοι, αλγόριθμοι τοπικής αναζήτησης)
Δεξιότητες: Εκμάθηση τεχνικών αναγωγών (σχέσεις μεταξύ διαφορετικών προβλημάτων ως προς τις απαιτήσεις τους στον υπολογισμό)
Γενικές Ικανότητες
- Προσαρμογή σε νέες καταστάσεις
- Λήψη αποφάσεων
- Αυτόνομη εργασία
- Σχεδιασμός και διαχείριση έργων
- Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης
Περιεχόμενο Μαθήματος
Γραμμικός προγραμματισμός (e.g., δυϊκότητα, η μέθοδος simplex, αλγόριθμοι εσωτερικού σημείου). Αριθμοθεωρητικοί αλγόριθμοι (π.χ., έλεγχος πρώτων αριθμών). Τυχαίοι αλγόριθμοι. Προσεγγιστικοί αλγόριθμοι. Πιθανοτική Ανάλυση. Άμεσης απόκρισης αλγόριθμοι και ανταγωνιστική ανάλυση. Τοπική Αναζήτηση.
Λέξεις Κλειδιά
Πολυπλοκότητα, Αλγόριθμοι
Τύποι Εκπαιδευτικού Υλικού
- Σημειώσεις
- Διαφάνειες
- Βιβλίο
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
Χρήση Τ.Π.Ε.
- Χρήση Τ.Π.Ε. στη Διδασκαλία
Οργάνωση Μαθήματος
| Δραστηριότητες | Φόρτος Εργασίας | ECTS | Ατομικά | Ομαδικά | Erasmus |
|---|---|---|---|---|---|
| Διαλέξεις | 39 | ✓ | |||
| Μελέτη και ανάλυση βιβλίων και άρθρων | 48 | ✓ | ✓ | ||
| Συγγραφή εργασίας / εργασιών | 60 | ✓ | ✓ | ||
| Εξετάσεις | 3 | ✓ | |||
| Τελική Εξέταση | |||||
| Σύνολο | 150 |
Αξιολόγηση Φοιτητών
Περιγραφή
Γραπτή εξέταση σε όλη την ύλη που έχει διδαχθεί (βιβλίο, διαφάνειες, ασκήσεις). Θεωρητικές/προγραμματιστικές εργασίες που παρέχουν προσθετικό βαθμό σε αυτόν του βαθμού εξέτασης.
Μέθοδοι Αξιολόγησης Φοιτητών
- Γραπτή Εξέταση με Ερωτήσεις Σύντομης Απάντησης (Συμπερασματική)
- Γραπτή Εξέταση με Ερωτήσεις Εκτεταμένης Απάντησης (Συμπερασματική)
- Δημόσια Παρουσίαση (Διαμορφωτική, Συμπερασματική)
- Γραπτή Εξέταση με Επίλυση Προβλημάτων (Διαμορφωτική, Συμπερασματική)
Βιβλιογραφία
Βιβλιογραφία μαθήματος (Εύδοξος)
1. Michael Sipser. Εισαγωγή στην Θεωρία Υπολογισμού. Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.
2. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
Επιπρόσθετη βιβλιογραφία για μελέτη
1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein: Εισαγωγή στους Αλγόριθμους, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.
Τελευταία Επικαιροποίηση
09-12-2020