ΑΠΟΤΕΛΕΣΜΑΤΑ ΕΞΕΤΑΣΕΩΝ 20/9/2006

ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ - Χειμερινό Εξάμηνο 2005-06

Πρόγραμμα διαλέξεων

• Οκτ. 4. Αποδοτικότητα χρόνου-χώρου, μέγεθος εισόδου, μοντέλο RAM, μέτρηση μοναδιαίου κόστους, μέτρηση λογαριθμικού κόστους, κοστολόγηση αλγορίθμων (διαφάνειες: ppt ή pdf).
• Οκτ. 6. Κυρίαρχες πράξεις, κοστολόγηση SelectionSort, ασυμπτωτικοί συμβολισμοί (O, Ω, Θ και ο), στενό ασυμπτωτικό όριο, αποδείξεις ιδιοτήτων ασυμπτωτικών συμβολισμών (διαφάνειες: ppt ή pdf).
• Οκτ. 11. Ανάλυση χειρότερης περίπτωσης, παράδειγμα QuickSort, ανάλυση μέσης περίπτωσης, παράδειγμα QuickSort, παράδειγμα Straight Insertion Sort (διαφάνειες: ppt ή pdf).
• Οκτ. 13. Μαθηματικά εργαλεία: εκθετικά, λογάριθμοι, αθροίσματα κλπ. (Κεφάλαιο 2 σημειώσεων).
• Οκτ. 18. Ομογενείς και μη ομογενείς γραμμικές αναδρομικές εξισώσεις (Κεφάλαιο 3 σημειώσεων).
• Οκτ. 20. Επίλυση αναδρομικής εξίσωσης με επαναληπτική αντικατάσταση, δένδρα αναδρομών, τεχνική κοστολόγησης αναδρομικού αλγορίθμου (Κεφάλαιο 3 σημειώσεων).
• Οκτ. 25. Το Γενικό Θεώρημα επίλυσης αναδρομικών εξισώσεων (Κεφάλαιο 3 σημειώσεων).
• Οκτ 27. Διακοπή.
• Νοεμ. 1. Εύρεση μέγιστου κοινού διαιρέτη, υπολογισμός αριθμών Fibonacci (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 3. Πύργοι Hanoi, υπολογισμός δύναμης (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 8. Υπολογισμός συνδυασμού, πολλαπλασιασμός πινάκων (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 10. Κόστος στοιχειωδών πράξεων (Κεφάλαιο 5 σημειώσεων) 
• Νοεμ. 15. Κόστος βασικών αλγορίθμων με μη μοναδιαίο κόστος πράξεων (Κεφάλαιο 5 σημειώσεων) 
• Νοεμ. 17. Διακοπή.
• Νοεμ. 22. Το πρόβλημα του μέγιστου αθροίσματος υπακολουθίας (Κεφάλαιο 6 σημειώσεων)
• Νοεμ. 24. Το πρόβλημα της τοποθέτησης 8 βασιλισσών (Κεφάλαιο 6 σημειώσεων)
• Νοεμβ. 29 Το πρόβλημα του πλανόδιου πωλητή (Κεφάλαιο 6 σημειώσεων)
• Δεκ. 1 Σειριακή αναζήτηση, δυαδική αναζήτηση (Κεφάλαιο 7 σημειώσεων)
• Δεκ. 6 Κατακερματισμός, γραμμική αναζήτηση (Κεφάλαιο 7 σημειώσεων)
• Δεκ. 8 Κατακερματισμός με αλυσίδες (Κεφάλαιο 7 σημειώσεων)
• Δεκ. 13 Ταξινόμηση με εισαγωγή, Ταξινόμηση με επιλογή (Κεφάλαιο 8 σημειώσεων)
• Δεκ. 15 Γρήγορη ταξινόμηση (Κεφάλαιο 8 σημειώσεων)
• Δεκ. 20 Στατιστικά διάταξης, Ταξινόμηση με συγχώνευση (Κεφάλαιο 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.

Ενδιαφέρουσες ιστοσελίδες

• Φοιτητικές σημειώσεις των παραδόσεων του χειμερινού εξαμήνου 2003
• Analysis of Algorithms Home Page
• Design and Analysis of Algorithms Home Page
• Robert Sedgewick

ΘΕΜΑΤΑ ΕΞΕΤΑΣΕΩΝ ΙΑΝΟΥΑΡΙΟΥ 2006

ΑΠΟΤΕΛΕΣΜΑΤΑ ΕΞΕΤΑΣΕΩΝ ΙΑΝΟΥΑΡΙΟΥ 200

ΑΠΟΤΕΛΕΣΜΑΤΑ ΠΤΥΧΙΑΚΗΣ ΕΞΕΤΑΣΗΣ 15/9/2006