ΥΠ11 - Δομές Δεδομένων

Πληροφορίες

Κωδικός : ΥΠ11

Τύπος : Υποχρεωτικό

Εξάμηνο : 3

Μονάδες ECTS: 6

URL: https://eclass.hua.gr/courses/DIT141/

Αναμενόμενα Αποτελέσματα

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

Φοιτητές που ολοκληρώνουν το μάθημα θα είναι σε θέση να γνωρίζουν:
Τις βασικές δομές δεδομένων που χρησιμοποιούνται στις γλώσσες προγραμματισμού.
Βασικούς αλγόριθμους όπως ταξινόμησης και αναζήτησης.
Την σχεδίασης απλών αλγορίθμων καθώς και τον τρόπο ανάλυσης και μέτρησης της απόδοσης τους.
Την χρήση της γλώσσας προγραμματισμού C ή/και Java για την υλοποίηση δομών δεδομένων.

Περιεχόμενο

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

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

Τρόπος Αξιολόγησης

Ι. Γραπτή τελική εξέταση 60% που περιλαμβάνει:
- Ερωτήσεις πολλαπλής επιλογής
- Επίλυση προβλημάτων με την χρήση της γλώσσας προγραμματισμού C ή/και Java
- Συγκριτική αξιολόγηση στοιχείων θεωρίας
ΙΙ. Ατομικές ή Ομαδικές Εργασίες 40%

Βιβλιογραφία

Robert Sedgewick, Αλγόριθμοι σε C: Θεμελιώδεις Έννοιες, Δομές Δεδομένων, Ταξινόμηση, Αναζήτηση. Εκδόσεις Κλειδάριθμος, 2005.

Kurt Mehlhorn και Peter Sanders. Αλγόριθμοι και Δομές Δεδομένων Τα βασικά εργαλεία. Εκδόσεις Κλειδάριθμος, 2014.

Γεώργιος Φ. Γεωργακόπουλος, Δομές Δεδομένων: Έννοιες, Τεχνικές, Αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2002.

Cormen, Leiserson, Rivest και Stein. Εισαγωγή στους αλγορίθμους, Τόμος Ι, Πανεπιστημιακές Εκδόσεις Κρήτης, 2006.