Δομές Δεδομένων

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

Στόχοι Μαθήματος

- Μοντελοποίηση ενός προβλήματος μέσω της κατάλληλης αφαίρεσης. - Σχεδίαση ή επιλογή των κατάλληλων δομών δεδομένων για συγκεκριμένα προγραμματιστικά προβλήματα. - Προγραμματισμός με δομημένο τρόπο μέσω της αφαίρεσης δεδομένων. - Υλοποίηση και αξιολόγηση διαφορετικών δομών. - Μελέτη βασικών αλγοριθμικών τεχνικών. - Μελέτη τυπικών αποδείξεων ορθότητας.

Προαπαιτούμενες Γνώσεις

Κωδικοί και σύνδεσμοι (στο Πανεπιστήμιο Κρήτης): - HY100 - Εισαγωγή στην Επιστήμη Υπολογιστών - HY150 - Προγραμματισμός

Περιεχόμενα

- Εισαγωγή: Βασικές έννοιες αλγορίθμων και δομών δεδομένων, τεχνικές απόδειξης (μέσω παραδείγματος ή αντιπαραδείγματος, μέσω απαγωγής σε άτοπο, μέσω μαθηματικής επαγωγής), μοντέλο RAM, ανάλυση αλγορίθμων, χρονική πολυπλοκότητα, ασυμπτωτική ανάλυση (σε Ο, Ω, Θ), πρότυπες τάξεις πολυπλοκότητας, μαθηματικό υπόβαθρο, αναδρομικοί αλγόριθμοι και η ανάλυσή τους, αναδρομικές σχέσεις, πειραματική ανάλυση. - Πίνακες: Πράξεις πάνω σε πίνακες, πολυδιάστατοι πίνακες, συμμετρικοί και τριγωνικοί πίνακες, αραιοί πίνακες. - Βασικές δομές δεδομένων: Στοίβες (αφηρημένη δομή δεδομένων, στατικές και δυναμικές υλοποιήσεις, στατική υλοποίηση πολλαπλών στοιβών, εφαρμογές, πολυπλοκότητα). Ουρές (αφηρημένη δομή δεδομένων, στατικές και δυναμικές υλοποιήσεις, πολυπλοκότητα, εφαρμογές). Λίστες (ταξινομημένες και μη ταξινομημένες λίστες, κόμβος φύλακας, διάσχιση λίστας, διάσχιση zig-zag, διπλά συνδεδεμένες λίστες, πολυπλοκότητα, εφαρμογές). - Δέντρα: Ορισμός, τύποι δέντρων και οι ιδιότητές τους, υλοποίηση, διάσχιση δέντρου, ταξινομημένα δέντρα. - Σύνολα & Λεξικά: Αφηρημένη δομή δεδομένων, υλοποίηση μέσω συνδεδεμένης λίστας, δυαδική αναζήτηση, αναμενόμενη ανάλυση, δυαδικά δέντρα αναζήτησης. - Ισορροπημένα Δέντρα: Δέντρα AVL, δέντρα-(2,3), δέντρα Red-Black. - Κατακερματισμός: Αλυσιδωτός κατακερματισμός, στρατηγικές open addressing (linear probing, double hashing), ανάλυση διαφορετικών στρατηγικών, ταξινομημένος κατακερματισμός, εκτατός κατακερματισμός, συναρτήσεις κατακερματισμού, καθολικός κατακερματισμός. - Ουρές προτεραιότητας: Αφηρημένη δομή δεδομένων, υλοποίηση μέσω ισορροπημένων δυαδικών δέντρων αναζήτησης, μερικώς ταξινομημένα δέντρα, υλοποιήσεις μέσω σωρών. - Ταξινόμηση: InsertionSort, SelectionSort, MergeSort, HeapSort, QuickSort. - Σύνολα με ειδικές λειτουργίες: Ξένα σύνολα που υποστηρίζουν Union-find, Up-Trees. - Γράφοι: Αναπαράσταση, υλοποίηση, διάσχιση, εφαρμογές.