Διδάσκων: Μιχάλης Πλεξουσάκης, Γ-118, Λευκό Κτήριο. E-mail: plex [at] tem uoc gr
Ώρες γραφείου: TBA
Βασικές έννοιες σχεδιασμού και ανάλυσης αλγορίθμων και αλγοριθμικής πολυπλοκότητας. Αλγοριθμικές τεχνικές. Αλγόριθμοι ταξινόμησης, εύρεσης και επιλογής. Δυναμικός προγραμματισμός. Άπληστοι αλγόριθμοι. Στοιχειώδεις αλγόριθμοι γραφημάτων. Αλγόριθμοι ελαχίστων επικαλυπτόντων δέντρων και ελαχίστων μονοπατίων. Επιλογή θεμάτων από τις εξής κατηγορίες αλγορίθμων: Αλγόριθμοι ροής σε δίκτυα, θεωρίας πινάκων, θεωρία αριθμών και συνδυαστικής.
Ώρες διαλέξεων: Δευτέρα, Τετάρτη 9:00-11:00, Θ-202
Ώρες εργαστηρίων/ασκήσεων: Παρασκευή 11:00-13:00, Θ-202
Διδακτικό υλικό
Για τις ανάγκες του μαθήματος θα χρησιμοποιηθεί το βιβλίο των Cormen, Leiserson, Rivest και Stein Εισαγωγή στους Αλγορίθμους, Τόμος Ι, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009. Συνιστούνται επίσης τα βιβλία Ανάλυση και Σχεδίαση Αλγορίθμων του A. Levitin, εκδόσεις Τζιόλα, 2008 και το βιβλίο Αλγόριθμοι, του Gṙegory Rawlings, εκδόσεις Κριτική, 2004.
Αξιολόγηση
Ο τελικός βαθμός, Β, του μαθήματος θα υπολογιστεί από τον τύπο B = 0.25 * E + 0.15 * Π + 0.60 * T. Εδώ E είναι ο μέσος όρος των ασκήσεων, Π ο βαθμός της προόδου και T ο βαθμός στο τελικό διαγώνισμα. Ο ίδιος τύπος υπολογισμού του τελικού βαθμού ισχύει και για την εξεταστική περίοδο του Σεπτεμβρίου. Η ημερομηνία διεξαγωγής της προόδου θα ανακοινωθεί σύντομα.
Ανακοινώσεις
2012-06-01 Παραδώστε το φυλλάδιο ασκήσεων μέχρι τις 6 Ιουνίου 9:00.
2012-05-20 Παραδώστε τις ασκήσεις 23.2-5, 24.3-1, 24.4-2 μέχρι τις 6 Ιουνίου 9:00.
2012-03-23 3ο φυλλάδιο ασκήσεων. Ημερομηνία παράδοσης 30 Μαρτίου 2012.
2012-03-21 Μια λύση του προβλήματος της μέγιστης κοινής υπακολουθίας.
2012-03-14 Μια υλοποίηση του αλγορίθμού πολλαπλασιαμού αλληλουχίας πινάκων στη γλώσσα C.
2012-03-10 2ο φυλλάδιο ασκήσεων. Ημερομηνία παράδοσης 23 Μαρτίου 2012.
2012-03-05 Η πρόοδος του μαθήματος θα γίνεις στις 19 Μαρτίου 2012 με ύλη μέχρι και το κεφάλαιο της ταχυταξινόμησης.
2012-02-24 1ο φυλλάδιο ασκήσεων. Ημερομηνία παράδοσης 5 Μαρτίου 2012.
Ημερολόγιο
2012-03-26 Άπληστοι αλγόριθμοι.
2012-03-23 Το πρόβλημα της μέγιστης κοινής υπακολουθίας (συνέχεια). Γραμματική απόσταση συμβολοσειρών.
2012-03-21 Το πρόβλημα της μέγιστης κοινής υπακολουθίας.
2012-03-19 Πρόοδος.
2012-03-16 Πολλαπλασιασμός αλληλουχίας πινάκων (συνέχεια).
2012-03-14 Χρονοπρογραμματισμός γραμμής παραγωγής. Πολλαπλασιασμός αλληλουχίας πινάκων.
2012-03-12 Δυναμικός προγραμματισμός. Αρχικές έννοιες και παραδείγματα.
2012-03-09 Ταχυταξινόμηση (συνέχεια). Επιλογή οδηγού. Χρόνος εκτέλεσης.
2012-03-07 Δεν έγινε μάθημα λόγω ασθένειας του διδάσκοντα.
2012-03-05 Ουρές προτεραιότητας. Εισαγωγή στην ταχυταξινόμηση (Quicksort).
2012-03-02 Ταξινόμηση σωρού (συνέχεια). Ασκήσεις.
2012-02-29 Ταξινόμηση σωρού. Η δομή δεδομένων σωρός (heap). Σωροί μεγίστου ελαχίστου. Αποκατάσταση ιδιότητας σωρού μεγίστου.
2012-02-27 Δεν έγινε μάθημα (Καθαρή Δευτέρα).
2012-02-24 Το κεντρικό θεώρημα (master theorem). Απόδειξη. Ασκήσεις.
2012-02-22 Το κεντρικό θεώρημα (master theorem). Παραδείγματα. Απόδειξη.
2012-02-20 Ο χρόνος εκτέλεσης της συγχωνευτικής ταξινόμησης. Λύση αναδρομικών σχέσεων.
2012-02-17 Ρυθμός αύξησης συναρτήσεων (συνέχεια). Άσκήσεις.
2012-02-15 Ρυθμός αύξησης συναρτήσεων. Η συγχωνευτική ταξινόμηση.
2012-02-13 Η έννοια του αλγορίθμου. Παραδείγματα. Τι σημαίνει ανάλυση αλγορίθμων. Ανάλυση χρόνου εκτέλεσης του αλγορίθμου ενθετικής ταξινόμησης.