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

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


Πρόγραμμα

Εβδομάδα Θέμα
1η Εισαγωγή - Βασικές έννοιες αλγορίθμων και δομών δεδομένων
2η Χρονικές Πολυπλοκότητες - Επιμερισμένο Κόστος, Απλά παραδείγματα αναδρομικών σχέσεων - Πίνακες
3η Βασικές Δομές Δεδομένων: Λίστες, Στοίβες, Ουρές
4η Λίστες
5η Δένδρα
6η Δένδρα
7η Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
8η Κατακερματισμός
9η Κατακερματισμός - Σύνολα που υποστηρίζουν ειδικές λειτουργίες
10η Ουρές Προτεραιότητας - Γράφοι
11η Γράφοι
12η Ταξινόμηση
13η Τεχνικές Σχεδίασης Αλγορίθμων


Παρακολούθηση

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