Παρουσίαση/Προβολή
Ανάλυση Αλγορίθμων
(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
-
Περιεχόμενο μαθήματος
- Η έννοια του αλγορίθμου και της πολυπλοκότητας
- Ασυμπτωτικοί συμβολισμοί (o, O, ω, Ω, Θ) και ασυμπτωτική ανάλυση αλγορίθμων
- Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις
- Οι κλάσεις P και NP, προβλήματα NP-complete και NP-hard
- Τεχνικές σχεδίασης αλγορίθμων: ωμή βία, διαίρει και βασίλευε, διαίρει και κυρίευε, μείωση και κυριαρχία, απληστία, δυναμικός προγραμματισμός
- Αλγόριθμοι δένδρων: Δυαδικά δένδρα αναζήτησης, δένδρα σωροί, AVL δένδρα, Β δένδρα
- Αλγόριθμοι γράφων: αναπαράσταση, διερεύνηση κατά πλάτος και βάθος, τοπολογική ταξινόμηση, ελάχιστα συνδετικά δένδρα, συντομότερες διαδρομές
Μέθοδοι αξιολόγησης
Τελική γραπτή εξέταση.
Βιβλιογραφία
Βιβλίο [112690793]: Ανάλυση και Σχεδίαση Αλγορίθμων, Neapolitan Richard
Βιβλίο [13898]: ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS
Βιβλίο [68370088]: Ανάλυση και Σχεδίαση Αλγορίθμων, 3η Έκδοση, Levitin Anavy, Mάνος Ρουμελιώτης (επιμέλεια)
Προτεινόμενα συγγράμματα
Βιβλίο [112690793]: Ανάλυση και Σχεδίαση Αλγορίθμων, Neapolitan Richard
Βιβλίο [13898]: ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS
Βιβλίο [68370088]: Ανάλυση και Σχεδίαση Αλγορίθμων, 3η Έκδοση, Levitin Anavy, Mάνος Ρουμελιώτης (επιμέλεια)
Διδάσκοντες
Γιαννουτάκης Κωνσταντίνος, Επίκουρος Καθηγητής
kgiannou@uom.edu.gr