Ανάλυση και Σχεδίαση Αλγορίθμων

Μαθησιακά Αποτελέσματα

Το μάθημα καλύπτει τις βασικές αρχές του σχεδιασμού και ανάλυσης αλγορίθμων ενώ εμφαίνεται η κρισιμότητα της επιλογής κατάλληλων δομών δεδομένων για την αποδοτικότητα των λύσεων.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής / τρια θα είναι σε θέση να:

• Γνωρίζει, κατανοεί και εφαρμόζει τις θεμελιώδεις τεχνικές σχεδίασης αλγορίθμων (διαίρει και βασίλευε, δυναμικός προγραμματισμός, απληστία).
• Γνωρίζει να αναλύει αλγορίθμους και να εκτιμά την συμπεριφορά τους στην χειρότερη, την μέση και την επιμερισμένη περίπτωση, εκφράζοντας τους σε μία ψευδογλώσσα.
• Κατανοεί πώς η εφαρμογή κατάλληλων δομών δεδομένων επηρεάζει τις επιδόσεις των αλγορίθμων.
• Γνωρίζει πώς να εφαρμόζει βασικούς αλγορίθμους που αφορούν τα γραφήματα και τις συμβολοσειρές.
• Διακρίνει τις κλάσεις πολυπλοκότητας και να γνωρίζει τις ευρετικές τεχνικές επίλυσης προβλημάτων NPC.

Ενδεικτικό Περιεχόμενο Μαθήματος

• Εισαγωγή στις ασυμπτωτικές εκτιμήσεις, επιδόσεις χειρότερης, μέσης και επιμερισμένης περιπτώσεως
• Αλγόριθμοι Brute-Force
• Αναδρομικοί αλγόριθμοι
• Αλγόριθμοι «Διαίρει και Βασίλευε»
• Δυναμικός προγραμματισμός
• Άπληστοι αλγόριθμοι
• Αλγόριθμοι οπισθοδρόμησης
• Δυαδικά δέντρα αναζήτησης
• Αλγόριθμοι γράφων (Dijkstra, DFS, BFS)
• Συναρτήσεις κατακερματισμού
• Κλάσεις P, NP, NP complete, NP hard