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