Σχεδίαση και Ανάλυση Αλγορίθμων
Υ306 Σχεδίαση και Ανάλυση Αλγορίθμων
Διδάσκων: Δημήτρης Kουκόπουλος
Στόχος του μαθήματος είναι η απόκτηση από τους φοιτητές ικανοτήτων μεθοδολογικού χαρακτήρα που αφορούν το σχεδιασμό, την ανάπτυξη και τον έλεγχο των αλγορίθμων, ώστε να μπορούν να επιλύουν προβλήματα ανεξάρτητα από τις γλώσσες προγραμματισμού που θα χρησιμοποιούν. Οι φοιτητές εισάγονται σε βασικές τεχνικές σχεδιασμού και ανάλυσης αλγορίθμων, ενώ παρουσιάζονται αλγόριθμοι επίλυσης κλασικών προβλημάτων διαχείρισης δεδομένων. Ειδικότερα παρουσιάζονται: Εισαγωγικές έννοιες αλγορίθμων. Αναπαράσταση Αλγορίθμων. Αναπαράσταση Δεδομένων: Γραφήματα, Δέντρα, Ουρές, Στοίβες. Τεχνικές διάσχισης δέντρου. Κατηγορίες αλγοριθμικών προβλημάτων (P και NP προβλήματα). Εισαγωγή στους ευρετικούς αλγορίθμους. Ανάλυση πολυπλοκότητας αλγορίθμων αναζήτησης: διαδοχική και δυαδική αναζήτηση. Χρήση δομής σωρού: αλγόριθμος Heapsort, ανάλυση πολυπλοκότητας μέσου όρου και χειρότερης περίπτωσης. Βασικές τεχνικές σχεδιασμού και ανάλυσης αλγορίθμων: εξισορρόπηση, διαίρει και βασίλευε (γενική ανάλυση, παραδείγματα – αλγόριθμος γρήγορης ταξινόμησης-Quicksort, δυαδική αναζήτηση, συμβολή και αλγόριθμος mergesort). Tεχνικές σχεδιασμού και ανάλυσης αλγορίθμων για προβλήματα με απαγορευτικό αριθμό περιπτώσεων: απληστία (κατάταξη έργων με προθεσμίες, το πρόβλημα του κλασματικού σακιδίου, το πρόβλημα του πλανόδιου πωλητή). Διάτρεξη γραφημάτων: αναζήτηση πρώτα κατά πλάτος, αναζήτηση πρώτα κατά βάθος. Αλγόριθμοι γραφημάτων. Δυναμικός προγραμματισμός (αρχή του Bellman, εφαρμογές). Εργαστήριο: σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον με έμφαση σε θέματα ψηφιακής διαχείρισης πολιτισμικού περιεχομένου.
Προτεινόμενα συγγράμματα
- Βιβλίο [13898]: ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS Λεπτομέρειες
- Βιβλίο [68370088]: Ανάλυση και Σχεδίαση Αλγορίθμων, 3η Έκδοση, Levitin Anavy, Mάνος Ρουμελιώτης (επιμέλεια) Λεπτομέρειες