Πληροφορίες Μαθήματος
ΤίτλοςΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY
ΚωδικόςNGE-07-01
ΣχολήΘετικών Επιστημών
ΤμήμαΠληροφορικής
Κύκλος / Επίπεδο1ος / Προπτυχιακό
Περίοδος ΔιδασκαλίαςΧειμερινή
Υπεύθυνος/ηΓεώργιος Χριστοδούλου
ΚοινόΝαι
ΚατάστασηΕνεργό
Course ID40002972

Πρόγραμμα Σπουδών: ΠΠΣ-Τμήμα Πληροφορικής (2019-σήμερα)

Εγγεγραμμένοι φοιτητές: 23
ΚατεύθυνσηΤύπος ΠαρακολούθησηςΕξάμηνοΈτοςECTS
ΓΕΝΙΚΗ ΚΑΤΕΥΘΥΝΣΗΥΠΟΧΡΕΩΤΙΚΟ ΚΑΤΑ ΕΠΙΛΟΓΗ745

Πληροφορίες Τάξης
ΤίτλοςΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ
Ακαδημαϊκό Έτος2019 – 2020
Περίοδος ΤάξηςΧειμερινή
Διδάσκοντες άλλων Κατηγοριών
Ώρες Εβδομαδιαία3
Class ID
600154416
Τύπος Μαθήματος 2016-2020
  • Υποβάθρου
  • Γενικών Γνώσεων
  • Επιστημονικής Περιοχής
Τύπος Μαθήματος 2011-2015
Ειδικού Υποβάθρου / Κορμού
Τρόπος Παράδοσης
  • Πρόσωπο με πρόσωπο
Ηλεκτρονική Διάθεση Μαθήματος
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