Διδάσκων: Μιχάλης Πλεξουσάκης, Γ-118, Λευκό Κτήριο. E-mail: plex [at] tem uoc gr
Ώρες γραφείου: TBA

Βασικές έννοιες σχεδιασμού και ανάλυσης αλγορίθμων και αλγοριθμικής πολυπλοκότητας. Αλγοριθμικές τεχνικές. Αλγόριθμοι ταξινόμησης, εύρεσης και επιλογής. Δυναμικός προγραμματισμός. Άπληστοι αλγόριθμοι. Στοιχειώδεις αλγόριθμοι γραφημάτων. Αλγόριθμοι ελαχίστων επικαλυπτόντων δέντρων και ελαχίστων μονοπατίων. Επιλογή θεμάτων από τις εξής κατηγορίες αλγορίθμων: Αλγόριθμοι ροής σε δίκτυα, θεωρίας πινάκων, θεωρία αριθμών και συνδυαστικής.

Ώρες διαλέξεων: Τετάρτη, Παρασκευή 11:00-13:00, Αίθουσα B208
Ώρες εργαστηρίων/ασκήσεων: Πέμπτη 9:00-11:00, Αίθουσα B208

Διδακτικό υλικό

Για τις ανάγκες του μαθήματος θα χρησιμοποιηθεί το βιβλίο των Cormen, Leiserson, Rivest και Stein Εισαγωγή στους Αλγορίθμους, Τόμος Ι, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009. Συνιστούνται επίσης τα βιβλία Ανάλυση και Σχεδίαση Αλγορίθμων του A. Levitin, εκδόσεις Τζιόλα, 2008 και το βιβλίο Αλγόριθμοι, του Gregory Rawlings, εκδόσεις Κριτική, 2004. Στο μάθημα θα καλύψουμε τα κεφάλαια 1-4, 6, 7, 15, 16, 22-25 και αν επιτρέψει ο χρόνος, άλλα θέματα όπως πίνακες διασποράς, δυαδικά δένδρα και B-δένδρα.

Αξιολόγηση

Ο τελικός βαθμός, Β, του μαθήματος θα υπολογιστεί από τον τύπο B = 0.4 * E + 0.60 * T. Εδώ E είναι ο μέσος όρος των ασκήσεων και T ο βαθμός στο τελικό διαγώνισμα. Ο ίδιος τύπος υπολογισμού του τελικού βαθμού ισχύει και για την εξεταστική περίοδο του Σεπτεμβρίου.

Ανακοινώσεις

2013-05-29 Παρακαλώ παραδώστε τις ασκήσεις του 5ου φυλλαδίου ασκήσεων μέχρι την Δευτέρα 10 Ιουνίου.

2013-05-08 Παρακαλώ παραδώστε τις ασκήσεις του 4ου φυλλαδίου ασκήσεων μέχρι την Κυριακή 19 Μαϊου.

2013-04-07 Παρακαλώ παραδώστε τις ασκήσεις του 3ου φυλλαδίου ασκήσεων μέχρι την Τετάρτη 17 Απριλίου.

2013-03-12 Παρακαλώ παραδώστε τις ασκήσεις του 2ου φυλλαδίου ασκήσεων μέχρι την Τετάρτη 20 Μαρτίου.

2013-03-01 Παρακαλώ παραδώστε τις ασκήσεις του 1ου φυλλαδίου ασκήσεων μέχρι την Παρασκευή 8 Μαρτίου. Οι ασκήσεις μπορούν να παραδίδονται και με email.

Ημερολόγιο

2013-05-24 Το πρόβλημα των πανζευτικών ελαφρύτατων διαδρομών.

2013-05-23 Άσκήσεις Κεφ. 24.

2013-05-22 Γραφήματα περιορισμών (συνέχεια).

2013-05-20 Γραφήματα περιορισμών.

2013-05-17 Ο αλγόριθμος του Dahlquist (συνέχεια).

2013-05-16 Ο αλγόριθμος του Dahlquist.

2013-05-15 Ο αλγόριθμος των Bellman-Ford (συνέχεια).

2013-04-13 Ο αλγόριθμος των Bellmman-Ford.

2013-04-26 Αποδείξεις ιδιοτήτων ελαφρύτατων διαδρομών.

2013-04-25 Ασκήσεις.

2013-04-24 Το πρόβλημα των ομοαφετηριακών ελαφρύτατων διαδρομών (συνέχεια).

2013-04-22 Το πρόβλημα των ομοαφετηριακών ελαφρύτατων διαδρομών (συνέχεια).

2013-04-19 Οι αλοριθμοι των Kruskal και Prim.

2013-04-18 Ασκήσεις.

2013-04-17 Εύρεση ισχυρά συνδεδεμένων συνιστωσών.

2013-04-15 Ισχυρά συνδεδεμένες συνιστώσες.

2013-04-12 Αναπαράσταση δυναμικών συνόλων.

2013-03-13 Ταξινόμηση σωρού (συνέχεια). Η μέθοδος της ταχυταξινόμησης (Quicksort).

2013-03-08 Ταξινόμηση σωρού.

2013-03-07 Δεν έγινε μάθημα λόγω εκδηλώσεων του Τμήματος.

2013-03-06 Το Κεντρικό Θεώρημα. Παραδείγματα.

2013-03-01 Δέντρα αναδρομής. Το Κεντρικό Θεώρημα.

2013-02-28 Ασκήσεις Κεφ. 3 και 4.

2013-02-27 Αναδρομικές σχέσεις. Η μέθοδος της αντικατάστασης.

2013-02-22 Ρυθμός αύξησης συναρτήσεων.

2013-02-21 Η τεχνική σχεδίασης divide-and-conquer. Ο αλγόριθμος της συγωνευτικής ταξινόμησης. Ανάλυση του χρόνου εκτέλεσης με δέντρα αναδρομής.

2013-02-20 Η έννοια του αλγορίθμου. Παραδείγματα. Το πρόβλημα της ταξινόμησης. Ανάλυση αλγορίθμων. Μαθηματικό υπόβαθρο.