ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ - Χειμερινό Εξάμηνο
2007-08
Διδάσκοντες του
μαθήματος είναι οι Παναγιώτης Κατσαρός
(Λέκτορας) και Γιάννης Μανωλόπουλος
(Καθηγητής). Στους
φοιτητές διανέμεται το βιβλίο "Αλγόριθμοι - Ανάλυση και Σύγκριση" του
Rawlings σε μετάφραση από τις Εκδόσεις Κριτική (από
το βιβλιοπωλείο Αννικούλα στη Δ. Γούναρη), ενώ συνιστάται να δοθεί
ιδιαίτερη προσοχή στις σημειώσεις.
Η παρούσα σελίδα αποτελεί ένα ημερολόγιο των διαλέξεων με την ύλη που
διδάσκεται και το υλικό των παρουσιάσεων.
Το ημερολόγιο θα ενημερώνεται σταδιακά και θα προστίθεται υλικό. Η περσινή σελίδα του μαθήματος
βρίσκεται εδώ.
Πρόγραμμα διαλέξεων
- Οκτ. 8. Αποδοτικότητα χρόνου-χώρου, μέγεθος εισόδου,
μοντέλο RAM, μέτρηση μοναδιαίου κόστους, μέτρηση λογαριθμικού
κόστους, κοστολόγηση αλγορίθμων (διαφάνειες:
ppt ή pdf).
- Οκτ. 10. Κυρίαρχες πράξεις, κοστολόγηση SelectionSort,
ασυμπτωτικοί συμβολισμοί (O, Ω, Θ και ο), στενό ασυμπτωτικό όριο,
αποδείξεις ιδιοτήτων ασυμπτωτικών συμβολισμών (διαφάνειες:
ppt ή pdf).
- Οκτ. 15. Ανάλυση χειρότερης περίπτωσης, παράδειγμα QuickSort,
ανάλυση μέσης περίπτωσης, παράδειγμα QuickSort, παράδειγμα Straight
Insertion Sort (διαφάνειες: ppt ή pdf).
- Οκτ. 17. Ομογενείς και μη ομογενείς γραμμικές αναδρομικές
εξισώσεις (Κεφάλαιο 3 σημειώσεων).
- Οκτ. 22. Επίλυση αναδρομικής εξίσωσης με επαναληπτική
αντικατάσταση, δένδρα αναδρομών, τεχνική κοστολόγησης αναδρομικού
αλγορίθμου (Κεφάλαιο 3 σημειώσεων).
- Οκτ. 24. Το Γενικό Θεώρημα επίλυσης αναδρομικών εξισώσεων
(Κεφάλαιο 3 σημειώσεων).
- Οκτ. 29. Εύρεση μέγιστου κοινού διαιρέτη, υπολογισμός αριθμών
Fibonacci (Κεφάλαιο 4 σημειώσεων).
- Οκτ. 31. Yπολογισμός δύναμης (Κεφάλαιο 4
σημειώσεων).
- Νοεμ. 5. Υπολογισμός συνδυασμού, πολλαπλασιασμός πινάκων
(Κεφάλαιο 4 σημειώσεων).
- Νοεμ. 7. Κόστος στοιχειωδών πράξεων (Κεφάλαιο
5 σημειώσεων)
- Νοεμ. 12. Κόστος βασικών αλγορίθμων με μη
μοναδιαίο κόστος πράξεων (Κεφάλαιο 5
σημειώσεων)
- Νοεμ. 14. Μέγιστο άθροισμα υπακολουθίας (Κεφάλαιο
6 σημειώσεων)
- Νοεμ. 19. Τοποθέτηση 8 βασιλισσών (Κεφάλαιο
6 σημειώσεων)
- Νοεμ. 21. Περιοδεύων πωλητής (Κεφάλαιο 6
σημειώσεων)
- Νοεμ. 26. Σειριακή - Δυαδική Αναζήτηση (Κεφάλαιο
7 σημειώσεων)
- Νοεμ. 28. Κατακερματισμός - Ανοικτός
κατακερματισμός (Κεφάλαιο 7 σημειώσεων)
- Δεκ. 3. Κατακερματισμός με αλυσίδες -
Ταξινόμηση με εισαγωγή (Κεφάλαια 7-8
σημειώσεων)
- Δεκ. 5. Ταξινόμηση με επιλογή (Κεφάλαιο 8
σημειώσεων)
- Δεκ. 10. Γρήγορη ταξινόμηση (Κεφάλαιο 8
σημειώσεων)
- Δεκ. 12. Στατιστικά διάταξης (Κεφάλαιο 8
σημειώσεων)
- Δεκ. 17. Ταξινόμηση με συγχώνευση (Κεφάλαιο
8 σημειώσεων)
- Δεκ. 19. Ταξινόμηση του Shell (Κεφάλαιο 8
σημειώσεων)
Βιβλιογραφία
- Παναγιώτης Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση",
Εκδόσεις Τζιόλα, 2003.
- Gregory Rawlings: "Αλγόριθμοι - Ανάλυση και Σύγκριση",
Εκδόσεις Κριτική, 2004. (διανέμεται)
- Ιωάννης Μανωλόπουλος και Κωνσταντίνος Ζαχαρής: "Η Tέχνη της
Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα, 2002.
- Gilles Brassard and Paul Bratley: "Algorithmics - Theory and
practice", 1st edition, Prentice Hall, 1988. (διατίθεται μετάφραση)
- Anany Levitin: "Introduction
to the Design and Analysis of Algorithms", Addison Wesley, 2003.
- 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.
Ενδιαφέρουσες ιστοσελίδες
ΘΕΜΑΤΑ
ΕΞΕΤΑΣΕΩΝ ΙΑΝΟΥΑΡΙΟΥ 2006
ΘΕΜΑΤΑ
ΕΞΕΤΑΣΕΩΝ ΣΕΠΤΕΜΒΡΙΟΥ 2006
ΘΕΜΑΤΑ
ΕΞΕΤΑΣΕΩΝ ΣΕΠΤΕΜΒΡΙΟΥ 2007