ECE8211 Δομές Δεδομένων και Αλγόριθμοι

Το μάθημα παρέχει στους φοιτητές μία εισαγωγή στις βασικές δομές δεδομένων, τους κύριους αλγορίθμους ταξινομήσεως και αναζητήσεως και τις τεχνικές σχεδίασης και ανάλυσης αλγορίθμων. Τα καλυπτόμενα θέματα περιλαμβάνουν: εισαγωγή στις ασυμπτωτικές εκτιμήσεις, επιδόσεις χειρότερης, μέσης και επιμερισμένης περιπτώσεως. Βασικές δομές δεδομένων (Πίνακες, Λίστες, Στοίβες, ουρές FIFO, Διπλοουρές), Στατικά – Δυναμικά Δένδρα και οι διελεύσεις τους, Δυαδικό Ψάξιμο και Εισαγωγή και Ανάλυση των συγκριτικών αλγορίθμων ταξινομήσεως (Εισαγωγής, Επιλογής, Φυσαλίδας, Αναμικτήρα, Ταχυδιάταξη, Σωρού, Συγχωνεύσεως), και των με διανομή αλγορίθμων ταξινομήσεως (Κάδου, Σημαντικότερου Ψηφίου και Λιγότερου Σημαντικού Ψηφίου), Δενδρικές Δομές Λεξικού: Απλά και Ισοζυγισμένα Δένδρα (AVL, (a,b), Ερυθρόμαυρα) Εισαγωγή στον Κατακερματισμό και στα Αδιάτακτα Λεξικά (Κατακερματισμός με Αλυσίδες, Με Ανοικτή Διευθυνσιοδότηση), Ουρές Προτεραιότητας, Γραφήματα (Μη κατευθυνόμενα και Κατευθυνόμενα). Διαπεράσεις Γραφημάτων και Εφαρμογές τους (Συνεκτικότητα, Δισυνεκτικότητα, Συντομότερα Μονοπάτια, Επικαλύπτοντα Δένδρα), Τεχνικές Σχεδιασμού Αλγορίθμων (Διαίρει και Βασίλευε, Δυναμικός Προγραμματισμός, Απληστία, Οπισθοδρόμηση, Διακλάδωση και Οριοθέτηση), Δυσεπίλυτα Προβλήματα.

Δεδομένου ότι το ΠΜΣ είναι διατμηματικό, υπάρχει μεγάλη ανομοιομορφία στο επίπεδο γνώσεων των φοιτητών σε θέματα σχετικά με την πληροφορική. Ενδεικτικά αναφέρω ότι το ΠΜΣ το παρακολουθούν στελέχη της ΠΑ, πτυχιούχοι μαθηματικών, απόφοιτοι ΤΕΕΦΑ κλπ.
Συνεπώς η ύλη του μαθήματος επιβάλλεται να ξεκινήσει εκ του μηδενός. Σκοπός του διδάσκοντος είναι να εισάγει απλές και κατανοητές έννοιες οι οποίες θα φανούν χρήσιμες στους φοιτητές και όχι να εμβαθύνει σε πολύπλοκες τεχνικές λεπτομέρειες με περιορισμένο εύρος εφαρμογών και δυσκολία κατανόησης. Για παράδειγμα, στην περίπτωση των δέντρων, γίνεται ανάλυση της χειρότερης περίπτωσης για τα δυαδικά δέντρα αναζήτησης και παρουσιάζεται η ανάγκη για εισαγωγή self-balancing δομών δεδομένων. Παρουσιάζεται η έννοια των περιστροφών, αλλά η ανάλυση περιορίζεται στα δέντρα AVL. Δεν διδάσκονται τα self-balancing δέντρα RedBlack και (α,β) που είναι ιδιαιτέρως πιο πολύπλοκα και δυσνόητα από το AVL. Ανάλογη τακτική ακολουθεί ο διδάσκων σε όλες τις διδακτικές υποενότητες της ύλης.
Με τον τρόπο αυτό οι φοιτητές αποκτούν σφαιρικά τη σχετική γνώση και εφοδιάζονται με τα εργαλεία που απαιτούνται για να εμβαθύνουν οι ίδιοι σε περίπτωση που το επιθυμούν. Η δυσκολία κρατείται σε μέτρια επίπεδα, ώστε να είναι δυνατή η παρακολούθηση των μαθημάτων από όλους και να μην αποκλειστούν οι απόφοιτοι άλλων τμημάτων.