ΑΛΓΟΡΙΘΜΟΙ - Εαρινό εξάμηνο 2016-17
Υπενθυμίζεται
ότι από τις 9 Μαίου έχει αρχίσει η διαδικασία αξιολόγησης στο σύστημα της
ΜΟΔΙΠ. Παρακαλείσθε να συμμετάσχετε.
Το
μάθημα αυτό έρχεται ως συνέχεια του ήδη διδαχθέντος μαθήματος «Δομές Δεδομένων»,
ενώ θα ακολουθήσει στο 6ο εξάμηνο το μάθημα «Αλγοριθμική Θεωρία
Γράφων». Το μάθημα αποτελείται από διαλέξεις θεωρίας, φροντιστηριακές ασκήσεις
και προγραμματιστικές ασκήσεις. Σύμφωνα με το πρόγραμμα οι διαλέξεις θεωρίας θα
γίνονται κάθε Τρίτη 9:00-11:00 και Τετάρτη 14:00-16:00 στην αίθουσα Β. Την
Παρασκευή και ώρα 14:00-16:00 στην αίθουσα Α22 θα γίνεται το δίωρο των
φροντιστηριακών και προγραμματιστικών ασκήσεων. Εδώ η σελίδα του φροντιστηρίου
.
Ο
τελικός βαθμός θα προκύψει κατά 70% από τις γραπτές εξετάσεις (απαραίτητη
προϋπόθεση ο βαθμός να είναι >4) και κατά 30% από τις υποχρεωτικές
προγραμματιστικές ασκήσεις. Θα υπάρξει 1 ατομική προγραμματιστική άσκηση, που
θα συνεισφέρει 30% στον τελικό βαθμό. Σημειώνεται ότι οι ασκήσεις θα ελέγχονται
από πρόγραμμα εντοπισμού αντιγραφών σε λογισμικό. Σε περίπτωση εντοπισμού
αντιγραφής, ο φοιτητής θα μηδενίζεται στο μάθημα συνολικά (συν πιθανή παραπομπή
του θέματος σε Γενική Συνέλευση του τμήματος). Υπόψη ότι η προθεσμία υποβολής
εργασιών είναι η ημέρα της εξέτασης του μαθήματος. Δεν είναι αποδεκτή παράδοση
των εργασιών το Σεπτέμβριο. Εδώ θα
βρείτε τη σελίδα του φροντιστηριακού δίωρου.
Επίσης, για την
πριμοδότηση όσων έρχονται στις παραδόσεις, θα δίνονται μικροασκήσεις κατά τη
διάρκεια του μαθήματος με προθεσμία ωρών. Το bonus από την επίλυση αυτών των
μικροασκήσεων μπορεί να φτάσει τη 1 μονάδα ή και περισσότερο (θα εξαρτηθεί στην
πορεία, πάντως κανείς δεν θα χάσει). Απαιτείται εντός της ίδιας ημέρας του
μαθήματος να αποστέλεται αρχείο pdf μίας (1) σελίδας αυστηρά, όπου επάνω
να αναφέρεται ονοματεπώνυμο και ΑΕΜ.
H περσινή σελίδα του μαθήματος
βρίσκεται εδώ. Η παρούσα σελίδα αποτελεί ένα
ημερολόγιο σχετικά με την πρόοδο του μαθήματος και θα ενημερώνεται σταδιακά. Το
περιεχόμενο των διαλέξεων αντιστοιχεί περίπου σε κεφάλαια του ακολουθούμενου
διδακτικού βοηθήματος, ενώ οι χρησιμοποιούμενες διαφάνειες θα καταχωρίζονται
σταδιακά (ωστόσο μπορείτε να βρείτε τις περσινές διαφάνειες στην αντίστοιχη
σελίδα). Για λόγους αρχής, δεν πρόκειται να δοθούν περαιτέρω εξηγήσεις σχετικά
με την ύλη είτε δημοσίως (προφορικά ή με ανακοίνωση) είτε ιδιωτικώς με email κλπ.
Επίσης,
εδώ
βρίσκονται παλαιότερες σημειώσεις σχετικά με την Ανάλυση Αλγορίθμων. Πιο
πρόσφατο είναι το ηλεκτρονικό βιβλίο «Σχεδίαση και Ανάλυση Αλγορίθμων»,
το οποίο έχει εκδοθεί από το πρόγραμμα Κάλλιπος και είναι ελεύθερα
διαθέσιμο εδώ.
Συνιστάται η μελέτη και αυτού του υλικού σε συνδυασμό με το κύριο σύγγραμα (το
πρώτο της βιβλιογραφίας που ακολουθεί), το οποίο διατίθεται από τον Εύδοξο. Σε
αυτό το βιβλίο είναι βασισμένες και οι διαφάνειες του μαθήματος. Το δεύτερο
σύγγραμμα της βιβλιογραφίας μπορεί να εντοπισθεί από τον παγκόσμιο ιστό.
Για κάθε ερώτηση σχετικά
με τη θεωρία απευθύνεστε στους διδάσκοντες Γιάννη Μανωλόπουλο (manolopo@csd.auth.gr) και Τάσο Γούναρη (gounaria@csd.auth.gr).
Τα
αποτελέσματα των εξετάσεων Ιουνίου εδώ.
Τα
αποτελέσματα των εξετάσεων Σεπτεμβρίου εδώ.
Πρόγραμμα
διαλέξεων
- Φεβ.14. Διάλεξη 1η. Εισαγωγή.
Αλγοριθμική επίλυση προβλημάτων (slides).
- Φεβ.15. Διάλεξη 2η. Εισαγωγή.
Δομές Δεδομένων.
- Φεβ.21. Διάλεξη 3η. Ανάλυση
αποδοτικότητας, συμβολισμοί Θ/Ο/Ω (slides).
- Φεβ.22. Εκδήλωση τμήματος (be
there!!!)
- Φεβ.28. Αργία
- Μαρ.1. Διάλεξη 4η. Ανάλυση
αποδοτικότητας, αναδρομικοί αλγόριθμοι.
- Μαρ.7. Διάλεξη 5η. Ανάλυση
αποδοτικότητας, master theorem.
- Μαρ.8. Διάλεξη 6η. Ωμή βία
(slides).
- Μαρ.14. Διάλεξη 7η. Διαίρεση
και Κυριαρχία (slides).
- Μαρ.15. Διάλεξη 8η. Διαίρεση
και Κυριαρχία.
- Μαρ.21. Διάλεξη 9η. Διαίρεση
και Κυριαρχία.
- Μαρ.22. Διάλεξη 10η. Μείωση και
Κυριαρχία (slides)
- Μαρ.28. Διάλεξη 11η. Φροντιστήριο.
- Μαρ.29. Διάλεξη 12η. Μείωση και
Κυριαρχία.
- Απρ.4. Διάλεξη 13η.
Μετασχηματισμός και Κυριαρχία (slides).
- Απρ.5. Διάλεξη 14η.
Μετασχηματισμός και Κυριαρχία.
- Απρ.25. Διάλεξη 15η.
Μετασχηματισμός και Κυριαρχία.
- Απρ.26. Διάλεξη 16η. Χωρικοί
και Χρονικοί Συμβιβασμοί (slides).
- Μάι.2. Διάλεξη 17η. Χωρικοί και
Χρονικοί Συμβιβασμοί.
- Μάι.3. Διάλεξη 18η. Δυναμικός
Προγραμματισμός (slides).
- Μάι.9. Διάλεξη 19η. Δυναμικός
Προγραμματισμός.
- Μάι.10. Διάλεξη 20η. Απληστοι
Αλγόριθμοι (slides).
- Μάι.16 Διάλεξη 21η. Απληστοι
Αλγόριθμοι.
- Μάι.17. Διάλεξη 22η.
Επαναληπτική Βελτίωση (slides).
- Μάι.23. Διάλεξη 23η.
Περιορισμοί Αλγοριθμικής Ισχύος (slides, slides).
- Μάι.24. Φοιτητικές εκλογές.
Βιβλιογραφία
- Anany Levitin: "Introduction to the Design and
Analysis of Algorithms", 2nd
edition, Pearson, 2006 (μετάφραση από Εκδόσεις Τζιόλα, 2008).
- Anany Levitin: "Introduction to the
Design and Analysis of Algorithms", 3rd
edition, Pearson, 2012 (εδώ διαθέσιμο στον παγκόσμιο ιστό).
- Κωνσταντίνος Τσίχλας,
Αναστάσιος Γούναρης και Ιωάννης Μανωλόπουλος: "Σχεδίαση και Ανάλυση Αλγορίθμων", Έργο Κάλλιπος, 2016 (εδώ διαθέσιμο
στον παγκόσμιο ιστό).
- Παναγιώτης Μποζάνης: "Αλγόριθμοι
- Σχεδιασμός και Ανάλυση", Εκδόσεις Τζιόλα, 2006.
- Παναγιώτης Μποζάνης: "Προβλήματα και Ασκήσεις στους
Αλγορίθμους", Εκδόσεις Τζιόλα, 2009.
- Ιωάννης Μανωλόπουλος και
Κωνσταντίνος Ζαχαρής: "Η
Tέχνη της Αλγοριθμικής Επίλυσης Προβλημάτων", Εκδόσεις Σαββάλα,
2002.
- Thomas
Cormen, Charles Leiserson and
Ronald Rivest: "Introduction to Algorithms",
3rd edition, MIT Press, 2009
(μετάφραση
από Πανεπιστημιακές Εκδόσεις Κρήτης).
- Sanjoy Dasgupta,
Christos Papadimitriou and Umesh Vazirani:
"Algorithms",
McGraw Hill,
2008 (εδώ διαθέσιμο στον
παγκόσμιο ιστό).
- Ellis
Horowitz,
Sartaj Sahni
and Sanguthevar Rajasekaran: "Fundamentals of Computer Algorithms", Orient Black Swan, 2008 (εδώ
διαθέσιμο στον παγκόσμιο ιστό).
- Steven Skienna: "The Algorithm Design Manual" Springer, 2nd edition, 2007.
- Jon Kleinberg and Eva Tardos: "Algorithm Design", Pearson, 2005 (μετάφραση από Εκδόσεις Κλειδάριθμος, εδώ διαθέσιμο στον παγκόσμιο ιστό).
- Robert Sedgewick: "Algorithms in C, Part 5 - Graph
Algorithms", 3rd edition, Addison
Wesley, 2002.
- Michael Goodrich and Roberto Tamassia: "Algorithm Design Foundations, Analysis, and Internet
Examples" John Wiley, 2002.
- Robert Sedgewick and Philippe Flajolet: "An
Introduction to the Analysis of Algorithms", Addisson Wesley, 1996.
- Gregory Rawlings: "Compared To What?: An Introduction to the Analysis of Algorithms",
Computer Science Press, 1992 (μετάφραση από Εκδόσεις Κριτική, "Αλγόριθμοι - Ανάλυση και Σύγκριση", 2004).
- Gilles Brassard and Paul Bratley: "Algorithmics - Theory and Practice", Prentice
Hall, 1988 (εδώ διαθέσιμο στον παγκόσμιο ιστό).
Ενημέρωση 23/5/2017