ΓραμματείαSecretariat: 2410 684574 | ΦοιτητικάStudents: 2410 684387 g-ds@uth.gr
Επιλογή Σελίδας

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

Κωδικός Μαθήματος

Y404

Εξάμηνο Σπουδών

4 (Δ)

Ώρες/Εβδομάδα - ECTS

4 – 5

Σάββας Ηλίας

Καθηγητής

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

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

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

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

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

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