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

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

ΑΠΟΤΕΛΕΣΜΑΤΑ ΕΞΕΤΑΣΕΩΝ ΣΕΠΤΕΜΒΡΊΟΥ 2007

Απαλλακτικές εργασίες

Οι φοιτητές που επιθυμούν να περάσουν το μάθημα με εργασίες θα πρέπει να έχουν υπόψη τους ότι οι εργασίες είναι ΑΤΟΜΙΚΕΣ. Περιλαμβάνουν την επίλυση προβλημάτων από αυτά που είναι διαθέσιμα στη διεύθυνση http://acm.uva.es/problemset/

Πιο συγκεκριμένα:

- Με την επίλυση 6 προβλημάτων ο φοιτητής παίρνει ΔΕΚΑ (10) και απαλλάσσεται της εξέτασης.
- Με την επίλυση 3 προβλημάτων ο φοιτητής παίρνει ΠΕΝΤΕ (5) και απαλλάσσεται της εξέτασης.
- Με την επίλυση 2 προβλημάτων ο φοιτητής παίρνει ΔΥΟ (2) ΜΟΝΑΔΕΣ BONUS στο βαθμό της εξέτασης.
- Με την επίλυση 1 προβλήματος ο φοιτητής παίρνει ΜΙΑ (1) ΜΟΝΑΔΑ BONUS στο βαθμό της εξέτασης.

Ένα πρόβλημα θεωρείται ότι επιλύθηκε αν ο φοιτητής προσκομίσει εκτύπωση της ιστοσελίδας που εμφανίζει το όνομά του σε αυτούς που επέλυσαν το πρόβλημα και μία αναφορά με τον κώδικα που χρησιμοποίησε και την ανάλυση του αλγορίθμου (που θα ελεγχθεί για την ορθότητά της).

Η προθεσμία παράδοσης των εργασιών είναι η ημερομηνία εξέτασης του μαθήματος. Δεν γίνονται αποδεκτές λύσεις που δε συνοδεύονται από την ανάλυση του αλγορίθμου που χρησιμοποιήθηκε. Οι φοιτητές που παραδίδουν εργασία θα έχουν υποχρέωση να προσέλθουν στις εξετάσεις και να παραδώσουν μία λευκή κόλα στην οποία θα επισυνάπτεται η εργασία τους.

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

• Οκτ. 23. Αποδοτικότητα χρόνου-χώρου, μέγεθος εισόδου, μοντέλο RAM, μέτρηση μοναδιαίου κόστους, μέτρηση λογαριθμικού κόστους, κοστολόγηση αλγορίθμων (διαφάνειες: ppt ή pdf).
• Οκτ. 24. Κυρίαρχες πράξεις, κοστολόγηση SelectionSort, ασυμπτωτικοί συμβολισμοί (O, Ω, Θ και ο), στενό ασυμπτωτικό όριο, αποδείξεις ιδιοτήτων ασυμπτωτικών συμβολισμών (διαφάνειες: ppt ή pdf).
• Οκτ. 30. Ανάλυση χειρότερης περίπτωσης, παράδειγμα QuickSort, ανάλυση μέσης περίπτωσης, παράδειγμα QuickSort, παράδειγμα Straight Insertion Sort (διαφάνειες: ppt ή pdf).
• Οκτ. 31. Ομογενείς και μη ομογενείς γραμμικές αναδρομικές εξισώσεις (Κεφάλαιο 3 σημειώσεων).
• Νοεμ. 6. Επίλυση αναδρομικής εξίσωσης με επαναληπτική αντικατάσταση, δένδρα αναδρομών, τεχνική κοστολόγησης αναδρομικού αλγορίθμου (Κεφάλαιο 3 σημειώσεων).
• Νοεμ. 7. Το Γενικό Θεώρημα επίλυσης αναδρομικών εξισώσεων (Κεφάλαιο 3 σημειώσεων).
• Νοεμ. 13. Εύρεση μέγιστου κοινού διαιρέτη, υπολογισμός αριθμών Fibonacci (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 14. Yπολογισμός δύναμης (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 20. Υπολογισμός συνδυασμού, πολλαπλασιασμός πινάκων (Κεφάλαιο 4 σημειώσεων).
• Νοεμ. 21. Κόστος στοιχειωδών πράξεων (Κεφάλαιο 5 σημειώσεων) 
• Νοεμ. 27. Κόστος βασικών αλγορίθμων με μη μοναδιαίο κόστος πράξεων (Κεφάλαιο 5 σημειώσεων) 
• Νοεμ. 28. Το πρόβλημα του μέγιστου αθροίσματος υπακολουθίας (Κεφάλαιο 6 σημειώσεων)
• Δεκ. 4. Το πρόβλημα της τοποθέτησης 8 βασιλισσών (Κεφάλαιο 6 σημειώσεων) 
• Δεκ. 5. Το πρόβλημα του πλανόδιου πωλητή (Κεφάλαιο 6 σημειώσεων) 
• Δεκ. 11. Σειριακή αναζήτηση, δυαδική αναζήτηση (Κεφάλαιο 7 σημειώσεων)  
• Δεκ. 12. Το μάθημα δεν έγινε λόγω κωλύματος του διδάσκοντα. Θα ανακοινωθεί ημερομηνία αναπλήρωσης.
• Δεκ. 18. Κατακερματισμός, Γραμμική αναζήτηση, Κατακερματισμός με αλυσίδες (Κεφάλαιο 7 σημειώσεων) 
• Δεκ. 19. Ταξινόμηση με εισαγωγή, Ταξινόμηση με επιλογή, Γρήγορη ταξινόμηση (Κεφάλαιο 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

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

ΘΕΜΑΤΑ ΕΞΕΤΑΣΕΩΝ ΣΕΠΤΕΜΒΡΙΟΥ 2007