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

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


Πρόγραμμα

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


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

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