Τίτλος Μαθήματος Αλγόριθμοι και Πολυπλοκότητα
Κωδικός Μαθήματος 321-4201
Εξάμηνο 4
ECTS 5
Ώρες (Θεωρία) 4
Ώρες (Εργαστηρίο) 2
Διδάσκοντας Καπόρης Αλέξιος

Ύλη μαθήματος

Προβλήματα συνδυαστικής βελτιστοποίησης. Αλγόριθμοι διαίρει-και-βασίλευε, FFT. Δυναμικός προγραμματισμός. Μέθοδος απληστίας. Αλγόριθμοι γραφημάτων: αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος, εφαρμογές. Ελάχιστα επικαλύπτοντα δέντρα, αλγόριθμοι Prim και Kruskal. Συντομότερα μονοπάτια, αλγόριθμοι Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Μέγιστη ροή, θεώρημα μέγιστης ροής - ελάχιστης τομής, αλγόριθμοι επαυξητικών μονοπατιών. Ροή ελάχιστου κόστους, αλγόριθμοι απάλειψης κύκλων αρνητικού μήκους. Υπολογιστική πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ-πληρότητα, αλγοριθμικές συνέπειες. Αλγόριθμοι προσέγγισης. Πιθανοτικοί αλγόριθμοι.

Επιδιωκόμενα μαθησιακά αποτελέσματα

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα:

  • Έχει την γνώση να μελετάει και να αναλύει θεωρητικά και πειραματικά (γλώσσα C) σημαντικούς αλγόριθμους.
  • Έχει την δεξιότητα να εφαρμόζει τεχνικές θεωρητικής και πειραματικής αναλύσεως σημαντικών αλγορίθμων.
  • Έχει την ικανότητα να επιλύει προβλήματα χρονικής πολυπλοκότητας.

Προαπαιτούμενα

Δεν απαιτούνται.

Εγχειρίδια του μαθήματος

1. Σχεδιασμός Αλγορίθμων, Jon Kleinberg, Eva Tardos.
2. Αλγόριθμοι, Sanjou Dasgupta, Christos Papadimitriou, Umesh Vazirani.
3. Introduction to Algorithms by Cormen , Leiserson, Rivest and Stein.

Συμπληρωματική βιβλιογραφία

Algorithmica,Springer.

Διδακτικές και μαθησιακές μέθοδοι

Ατομικές και ομαδικές εργασίες, πρακτική εξάσκηση στο εργαστήριο, μικρά τεστ στη μορφή κουίζ, τελική γραπτή εξέταση.

Δραστηριότητα Φόρτος Εργασίας Εξαμήνου
Διαλέξεις 52 ώρες
Εργαστηριακές Ασκήσεις 26 ώρες
Προσωπική μελέτη 43 ώρες
Πρόοδος 1 ώρα
Τελική εξέταση 3 ώρες
Σύνολο Μαθήματος 125 ώρες (5 ECTS)

Μέθοδοι αξιολόγησης / βαθμολόγησης

Τελική εξέταση και πρόοδος

Γλώσσα διδασκαλίας

Ελληνικά (Αγγλικά αν υπάρχουν φοιτητές/φοιτήτριες ERASMUS)

Τρόπος παράδοσης μαθήματος

Φυσική Παρουσία.