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

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

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

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

Η απόκτηση αλγοριθμικής σκέψης και καλλιέργεια της αυστηρής αναλυτικής σκέψης για επίλυση προβλημάτων. Η σύνδεση της θεωρητικής μελέτης αλγορίθμων με την πειραματική υλοποίηση τους.

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

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

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

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)

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

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