ΑΛΓΟΡΙΘΜΟΙ -
Εαρινό εξάμηνο 2014-15
Το μάθημα αυτό έρχεται ως συνέχεια του ήδη
διδαχθέντος μαθήματος «Δομές Δεδομένων», ενώ θα ακολουθήσει στο 6ο
εξάμηνο το μάθημα «Αλγοριθμική Θεωρία Γράφων». Το μάθημα αποτελείται από διαλέξεις
θεωρίας, φροντιστηριακές ασκήσεις και προγραμματιστικές ασκήσεις. Σύμφωνα με το πρόγραμμα
οι διαλέξεις θεωρίας θα γίνονται κάθε Τρίτη
17:00-19:00 και Πέμπτη 9:00-11:00 στην αίθουσα Β. Την Τετάρτη και ώρα
11:00-13:00 στην αίθουσα Δ21 θα γίνεται το δίωρο των φροντιστηριακών και
προγραμματιστικών ασκήσεων. Επειδή στο φροντιστήριο θα γίνεται εμβάθυνση στην ήδη αναπτυχθείσα
θεωρία, το δίωρο αυτό θα αρχίσει από την Τετάρτη 4/3/2015.
Ο τελικός βαθμός θα προκύψει κατά 70% από τις γραπτές εξετάσεις
(απαραίτητη προϋπόθεση ο βαθμός να είναι >4) και κατά 30% από τις
υποχρεωτικές προγραμματιστικές ασκήσεις. Θα υπάρξει 1 ατομική προγραμματιστική
άσκηση, που θα συνεισφέρει 30% στον τελικό βαθμό. Σημειώνεται ότι οι ασκήσεις θα ελέγχονται από πρόγραμμα εντοπισμού αντιγραφών
σε λογισμικό. Σε περίπτωση εντοπισμού αντιγραφής, ο φοιτητής θα μηδενίζεται στο
μάθημα συνολικά (επιπρόσθετα με πιθανή παραπομπή του θέματος σε ΓΣ). Υπόψη ότι η προθεσμία
υποβολής εργασιών είναι η ημέρα της εξέτασης του μαθήματος. Δεν είναι αποδεκτή
παράδοση των εργασιών το Σεπτέμβριο. Εδώ θα
βρείτε τη σελίδα του φροντιστηριακού δίωρου. Σχετικά με το φροντιστήριο και τη
βαθμολόγηση των εργασιών, να απευθύνεστε στον Ανδρέα Κοσματόπουλου
(akosmato@delab.csd.auth.gr) και το Θανάση Νάσκο (anaskos@delab.csd.auth.gr).
H περσινή σελίδα του μαθήματος βρίσκεται εδώ. Η παρούσα σελίδα
αποτελεί ένα ημερολόγιο σχετικά με την πρόοδο του μαθήματος, το οποίο
προοδευτικά θα ενημερώνεται. Το περιεχόμενο των διαλέξεων αντιστοιχεί περίπου
σε κεφάλαια του ακολουθούμενου διδακτικού βοηθήματος, ενώ οι χρησιμοποιούμενες
διαφάνειες θα καταχωρούνται σταδιακά (ωστόσο μπορείτε να βρείτε τις περσινές
διαφάνειες στην αντίστοιχη σελίδα). Για λόγους αρχής, δεν πρόκειται να δοθούν
περαιτέρω εξηγήσεις σχετικά με την ύλη είτε δημοσίως (προφορικά ή με
ανακοίνωση) είτε ιδιωτικώς με email κλπ.
Επίσης, εδώ
βρίσκονται σημειώσεις σχετικά με την Ανάλυση Αλγορίθμων. Συνιστάται η μελέτη
και αυτού του υλικού σε συδυασμό με το κύριο σύγγραμα (το πρώτο της
βιβλιογραφίας που ακολουθεί).
Για κάθε
ερώτηση σχετικά με τη θεωρία απευθύνεστε στους διδάσκοντες Γιάννη Μανωλόπουλο (manolopo@csd.auth.gr) και Κώστα Τσίχλα (tsichlas@csd.auth.gr).
Προθεσμία
υποβολής εργασιών: 7 Ιουνίου. Στη συνέχεια απώλεια 25%.
Συνολικά
αποτελέσματα Ιουνίου (εδώ). Πληροφορίες στο
γραφείο την Πέμπτη το πρωί.
Συνολικά
αποτελέσματα Σεπτεμβρίου (εδώ).
Πρόγραμμα διαλέξεων
- Φεβ.17. Διάλεξη 1η.
Εισαγωγή. Αλγοριθμική επίλυση προβλημάτων (slides).
- Φεβ.26. Διάλεξη 2η.
Εισαγωγή. Σημαντικοί τύποι προβλημάτων.
- Μαρ.3. Διάλεξη 3η.
Εισαγωγή. Πανόραμα δομών δεδομένων.
- Μαρ.5. Διάλεξη 4η.
Συμβολισμοί Ο,Θ,Ω. Ανάλυση επαναληπτικών αλγορίθμων (slides).
- Μαρ.10. Διάλεξη 5η.
Ανάλυση αναδρομικών αλγορίθμων.
- Μαρ.12. Διάλεξη 6η.
Ομογενείς και μη ομογενείς γραμμικές αναδρομικές εξισώσεις.
- Μαρ.17. Διάλεξη 7η.
Ωμή Βία. (slides).
- Μαρ.19. Διάλεξη 8η.
Διαίρεση & Κυριαρχία. Κύριο
Θεώρημα. Γρήγορη Ταξινόμηση (slides).
- Μαρ.24. Διάλεξη 9η. Ταξινόμηση Συγχώνευσης.
Πολλαπλασιασμός Πινάκων Strassen.
- Μαρ.26. Διάλεξη
10η. Πρόβλημα
Εγγύτερου Ζεύγους. Πρόβλημα Κυρτού Εσωτερικού.
- Μαρ.31. Διάλεξη
11η. Μείωση
& Κυριαρχία. Ταξινόμηση Εισαγωγής. DFS-BFS. Δυαδική Αναζήτηση.
Πρόβλημα Παραχαραγμένου νομίσματος. Πρόβλημα Επιλογής. Αναζήτηση
Παρεμβολής (slides).
- Απρ.2. Διάλεξη 12η. Μετασχηματισμός
& Κυριαρχία. Προταξινόμηση. Γκαουσιανή Απαλοιφή. 2-3 δένδρα (επιπλέον slides
διδάσκοντα).
- Απρ.21. Διάλεξη
13η. Horner. Εκθετικοποίηση.
Αναγωγή προβλήματος. ΜΚΔ-ΕΚΠ. Μέτρηση μονοπατιών σε γράφο.
- Απρ.23. Διάλεξη
14η.Χωρικοί και χρονικοί συμβιβασμοί. Ταξινομήσεις χωρίς σύγκριση.
Αλγόριθμος Horspool.
- Μάιος.5. Διάλεξη
15η. Αλγόριθμος Boyer-Moore. Κατακερματισμός.
- Μάιος.7. Διάλεξη
16η. Β-δένδρα (slides, slides). Δυναμικός προγραμματισμός (slides).
- Μάιος.12. Διάλεξη
17η. Το
πρόβλημα των ρέστων.
- Μάιος.14. Διάλεξη
18η. Το
πρόβλημα δρομολόγησης εργασιών με βάρη, Μεταβατική κλειστότητα, Αλγόριθμος
Warshall.
- Μάιος.19.
Διάλεξη.19η. Αλγόριθμος Floyd, Πρόβλημα
Σακιδίου, Συναρτήσεις μνήμης (slides).
- Μάιος.21.Διάλεξη
20η. Ευθυγράμμιση Συμβολοσειρών, Εισαγωγή στην Απληστία,
Το πρόβλημα των ρέστων.
- Μάιος.26. Διάλεξη
21η. Αλγόριθμος Kruskal, Αλγόριθμοι Union-find (slides).
- Ιούν.2. Διάλεξη
22η. Αλγόριθμος Dijkstra (slides),
Ευσταθές ταίριασμα (slides).
Βιβλιογραφία
- Anany
Levitin: "Introduction to the Design and
Analysis of Algorithms", Addison Wesley, 2003
(μετάφραση από τις Εκδόσεις Τζιόλα,
2008) Σε αυτό το βιβλίο είναι βασισμένες και οι διαφάνειες του μαθήματος.
- Παναγιώτης
Μποζάνης: "Αλγόριθμοι - Σχεδιασμός και Ανάλυση", Εκδόσεις Τζιόλα,
2003.
- Jon Kleinberg and Eva Tardos: "Algorithm Design",
Addison Wesley, 2005 (μεταφρασμένο
από τις Εκδόσεις Κλειδάριθμος).
- Steven Skienna: "The Algorithm Design
Manual" Springer, 2nd edition, 2007.
- Thomas Cormen, Charles Leiserson
and Ronald Rivest: "Introduction to
Algorithms", 1st edition, MIT Press, 1990 (μεταφρασμένο από τις Πανεπιστημιακέρς Εκδόσεις Κρήτης).
- Sanjoy
Dasgupta, Christos Papadimitriou and Umesh Vazirani: Algorithms (μεταφρασμένο από τις Εκδόσεις Κλειδάριθμος).
- Ιωάννης Μανωλόπουλος και Κωνσταντίνος Ζαχαρής:
"Η
Tέχνη της Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα,
2002.
- Gregory Rawlings: "Αλγόριθμοι - Ανάλυση και
Σύγκριση", Εκδόσεις Κριτική, 2004.
- Gilles Brassard and
Paul Bratley: "Algorithmics
- Theory and practice", 1st edition, Prentice Hall, 1988.
- 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.
- Michael Goodrich and
Roberto Tamassia: "Algorithm Design
Foundations, Analysis, and Internet Examples"
John Wiley, 2002.
Ενημέρωση 7/7/2015