Παρουσίαση/Προβολή
Ανάλυση Αλγορίθμων
(CSC401) - ΚΩΝΣΤΑΝΤΙΝΟΣ ΓΙΑΝΝΟΥΤΑΚΗΣ
Περιγραφή Μαθήματος
Τιμώντας τους Aho, Ullman
The Design and Analysis of Computer Algorithms (1974)
Co-authored by Aho, Ullman, and John Hopcroft, this book is considered a classic in the field and was one of the most cited books in computer science research for more than a decade.
2020 ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms
Columbia’s Aho and Stanford’s Ullman Developed Tools and Seminal Textbooks Used by Millions of Software Programmers around the World
Στόχος του μαθήματος είναι η κατάρτιση σε μεθόδους ανάλυσης αλγορίθμων, εξοικείωση με προχωρημένες στρατηγικές επίλυσης και ανάλυσης προβλημάτων και κατανόηση των ιδιαίτερων χαρακτηριστικών τους.
Ημερομηνία δημιουργίας
Τρίτη 9 Φεβρουαρίου 2021
-
Περιεχόμενο μαθήματος
- Ανάλυση Αλγορίθμων: Λεπτομερές και απλοποιημένο μοντέλο του Υπολογιστή, Παραδείγματα
- Ασυμπτωτικός συμβολισμός: Ασυμπτωτικό άνω φράγμα – Ο, Ασυμπτωτικό κάτω φράγμα – Ω, Συμβολισμός Θ και ο
- Ασυμπτωτική ανάλυση αλγορίθμων – Παραδείγματα
- Μεθοδολογία μη αναδρομικών αλγορίθμων – υπολογισμός αθροισμάτων
- Μεθοδολογία αναδρομικών αλγορίθμων – μέθοδος διαίρει και βασίλευε – Παραδείγματα
- Αναζήτηση, Σειριακή αναζήτηση, Δυαδική Αναζήτηση, ανάλυση πολυπλοκότητας
- Αλγόριθμοι Ταξινόμησης Ι: Ταξινόμηση με Εισαγωγή, Ταξινόμηση με Επιλογή, ανάλυση πολυπλοκότητας καλύτερη, χειρότερη, μέση περίπτωση
- Αλγόριθμοι Ταξινόμησης ΙΙ: Γρήγορη ταξινόμηση, Ταξινόμηση με Συγχώνευση, ανάλυση πολυπλοκότητας καλύτερη, χειρότερη, μέση περίπτωση
- Ταξινόμηση του Shell, ανάλυση πολυπλοκότητας
- Σύγκριση αλγορίθμων ταξινόμησης, Ανάλυση Αλγορίθμων Ταξινόμησης και σύγκριση με εμπειρικά δεδομένα
- Αλγόριθμοι Ταξινόμησης ΙΙΙ: Ταξινόμηση με Μέτρημα, Ταξινόμηση με βάση τη Ρίζα, ανάλυση πολυπλοκότητας
- Όρια Αλγόριθμων Ταξινόμησης. Στατιστικά Διάταξης, Στατιστικά σε Μέσο Γραμμικό Χρόνο
- Αλγόριθμοι Σωρών: Σωρός Μεγίστων, Ταξινόμηση με Σωρό, Σωρός Ελαχίστων Μεγίστων, Διπλός Σωρός, ανάλυση πολυπλοκότητας
- Γραφήματα: Βασικές έννοιες γραφημάτων, Αλγόριθμοι διερεύνησης γραφήματος κατά πλάτος & κατά βάθος, Ελάχιστα Δένδρα καλύμματα – αλγόριθμοι Prim & Kruskal, Ελάχιστα μονοπάτια – αλγόριθμοι Bellman-Ford, Dijkstra, Floyd. Ανάλυση πολυπλοκότητας των παραπάνω αλγορίθμων.
Μέθοδοι αξιολόγησης
Τελική γραπτή εξέταση.
Βιβλιογραφία
- ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΤΟΜΟΣ Ι, CORMEN T.H., LEISERSON C.E., RIVEST R.L., STEIN C., ΙΔΡΥΜΑ ΤΕΧΝΟΛΟΓΙΑΣ & ΕΡΕΥΝΑΣ-ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ.
- Ανάλυση και σχεδίαση αλγορίθμων, Παπαρρίζος Κωνσταντίνος, ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ
- Ανάλυση Αλγορίθμων, Ι. Μανωλόπουλος, Σ. Σιούτας, Α. Τσακαλίδης, Κ. Τσίχλας, Ηλεκτρονικές σημείωσεις
Προτεινόμενα συγγράμματα
Βιβλίο [59359780]: ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Βιβλίο [18548861]: Ανάλυση και σχεδίαση αλγορίθμων, Παπαρρίζος Κωνσταντίνος
Βιβλίο [13898]: ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS
Βιβλίο [18549038]: Ανάλυση και σχεδίαση αλγορίθμων, Levitin Anany
Διδάσκοντες
Γιαννουτάκης Κωνσταντίνος, Επίκουρος Καθηγητής
kgiannou@uom.edu.gr