ΣΧΕΔΙΑΣΗ ΑΛΓΟΡΙΘΜΩΝ - Εαρινό Εξάμηνο 2007-08
Η παρούσα σελίδα αποτελεί ένα ημερολόγιο σχετικά μην πρόοδο του μαθήματος και
εδώ θα αναρτώνται σταδιακά οι διαφάνειες των διαλέξεων. Σε αντίθεση με την
περσινή χρονιά, φέτος δεν θα υπάρξει δυνατότητα εκπόνησης προαιρετικών
προγραμματιστικών θεμάτων γιατί έγινε κατάχρηση της διευκόλυνσης.
Από το Βιβλιοπωλείο Τζιόλα (Οδός Μελενίκου) θα διανεμηθεί δωρεάν το πρώτο
βιβλίο της ακόλουθης βιβλιογραφίας, το οποίο αποτελεί ένα άριστο και χρήσιμο
βοήθημα τόσο στο φετεινό μάθημα όσο και στο μάθημα της ΑΝΑΛΥΣΗΣ ΑΛΓΟΡΙΘΜΩΝ του 5ου
εξαμήνου. Για λόγους αρχής, δεν πρόκειται να δοθούν περαιτέρω εξηγήσεις σχετικά με
την ύλη είτε δημοσίως (προφορικά ή με ανακοίνωση) είτε ιδιωτικώς με email κλπ.
Πρόγραμμα διαλέξεων
- Φεβ.25, Δευτέρα. Διάλεξη 1η. Δομή Μαθήματος. Εισαγωγή.
(slides1).
- Φεβ.26, Τρίτη. Διάλεξη 2η. Ανάλυση αλγορίθμων. Επαναληπτικοί αλγόριθμοι.
- Μαρ.3, Δευτέρα. Διάλεξη 3η. Ανάλυση αλγορίθμων. Αναδρομικοί αλγόριθμοι.
(slides2).
- Μαρ.4, Τρίτη. Διάλεξη 4η. Ωμή Βία. Ταξινόμηση. Ταύτιση προτύπου.
- Μαρ.24, Δευτέρα. Διάλεξη 5η. Κυρτό περόβλημα. Εγγύτερο ζεύγος.
Εξαντλητική αναζήτηση (slides3).
- Μαρ.31, Δευτέρα. Διάλεξη 6η. Διαίρει και Βασίλευε. Ταξινόμηση με συγχώνευση.
Γρήγορη ταξινόμηση.
- Απρ.1, Τρίτη. Διάλεξη 7η. Πολλαπλασιασμός μεγάλων ακεραίων. Strassen.
Κυρτό περίβλημα (slides4).
- Απρ.7, Δευτέρα. Διάλεξη 8η. Διαίρει και Κυριάρχησε. Ύψωση σε δύναμη. Ταξινόμηση με εισαγωγή
(slides5).
- Απρ.8, Τρίτη. Διάλεξη 9η. DFS-BFS. Τοπολογική ταξινόμηση. Κίβδηλο
νόμισμα. Υπολογισμός μέσου.
- Απρ.14, Δευτέρα. Διάλεξη 10η. Δημιουργία μεταθέσεων και υποσυνόλων. Αναζήτηση παρεμβολής.
- Απρ.15, Τρίτη. Διάλεξη 11η. Μετασχημάτισε και Κυριάρχησε. Απλοποίηση στιγμιοτύπου
(slides6).
- Μαι.5, Δευτέρα. Διάλεξη 12η. Μετασχημάτισε και Κυριάρχησε. Αλλαγή αναπαράστασης.
- Μαι.6, Τρίτη. Διάλεξη 13η. Μετασχημάτισε και Κυριάρχησε. Μείωση προβλήματος.
- Μαι.12, Δευτέρα. Διάλεξη 14η. Χωροχρονικοί συμβιβασμοί. Ταξινόμηση μη βασισμένη
σε συγκρίσεις. Ταύτιση προτύπου.
- Μαι.13, Τρίτη. Διάλεξη 15η. Χωροχρονικοί συμβιβασμοί. Ανοικτός και κλειστός
κατακερματισμός
(slides7).
- Μαι.19, Δευτέρα. Διάλεξη 16η. Δυναμικός προγραμματιμός. Δυνωνυμικοί συντελεστές.
Αλγόριθμοι Warshall και Floyd.
- Μαι.20, Τρίτη. Διάλεξη 17η. Δυναμικός προγραμματιμός. Βέλτιστα δυαδικά δένδρα
αναζήτησης. Πρόβλημα σάκου και συναρτήσεις μνήμης
(slides8).
- Μαι.26, Δευτέρα. Διάλεξη 18η. Απληστοι αλγόριθμοι. MST (Prim, Kruskal). Αλγόριθμος Dijkstra
(slides9).
- Μαι.27, Τρίτη. Διάλεξη 19η. Κατηγοριοποίηση πολυπλοκοτήτων. Κλάσεις P και NP.
CNF satisfiability
(slides10).
Βιβλιογραφία
- Anany Levitin: "Introduction
to the Design and Analysis of Algorithms", Addison Wesley, 2003.
(Μετάφραση από τις Εκδόσεις Τζιόλα, 2008.)
- Παναγιώτης
Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση",
Εκδόσεις Τζιόλα, 2003.
- Gregory Rawlings: "Αλγόριθμοι - Ανάλυση και Σύγκριση",
Εκδόσεις Κριτική, 2004.
- Ιωάννης Μανωλόπουλος και Κωνσταντίνος Ζαχαρής: "Η Tέχνη της
Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα, 2002.
- Gilles Brassard and Paul Bratley: "Algorithmics - Theory and
practice", 1st edition, Prentice Hall, 1988.
- Thomas Cormen, Charles Leiserson and Ronald Rivest: "Introduction
to Algorithms", 1st edition, MIT Press, 1990.
- Robert Sedgewick: "Algorithms in C, Part 5 - Graph Algorithms", 3rd
edition, Addison Wesley, 2002.
- Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran: ""Computer
Algorithms"", Computer Science Press, 1998.
- Robert Sedgewick and Philippe Flajolet: "An Introduction to the Analysis of Algorithms",
Addisson Wesley, 1996.
- Steven Skienna: "The
Algorithm Design Manual" Springer-Telos, 1998.
- Michael Goodrich and Roberto Tamassia: "Algorithm Design
Foundations, Analysis, and Internet Examples" John Wiley, 2002.
Ενημέρωση 25/5/2008.