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

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• Επιδιωκόμενα μαθησιακά αποτελέσματα του μαθήματος

Στο τέλος αυτού του μαθήματος ο φοιτητής θα μπορεί:

1. να παρουσιάζει τις βασικές αρχές σχεδίασης δομών δεδομένων και τις βασικές δομές δεδομένων
2. να σχεδιάζει και να υλοποιεί δομές δεδομένων
3. να εφαρμόζει μεθοδολογικά και συνεργατικά δομές δεδομένων για την επίλυση δύσκολων αλγοριθμικών προβλημάτων

Δεξιότητες

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

Περιεχόμενο (ύλη)

Βασικές έννοιες πολυπλοκότητας (χωρικές και χρονικές πολυπλοκότητες, επιμερισμένη πολυπλοκότητα), Διάταξη στοιχείων, Διάταξη στοιχείων σε κύρια μνήμη, Bubblesort, Heapsort με ανάλυση, Quicksort με ανάλυση, Διάταξη στοιχείων σε δευτερεύουσα μνήμη. Δομημένοι τύποι στοιχείων, array, record, file, σωροί και ουρές, ουρές με προτεραιότητα, λίστες, δένδρα. O Γραμμικός Median-Aλγόριθμος. Tο πρόβλημα του Λεξικού. Συνοπτικές δομές δεδομένων. Δυϊκό ψάξιμο. Interpolation-ψάξιμο, Binary Interpolation ψάξιμο, Interpolation-ψάξιμο για άγνωστες μη ισοπιθανές κατανομές. Δυναμικές συνοπτικές δομές δεδομένων. Eκτενείς δομές δεδομένων. Ζυγισμένα δένδρα: AVL- δένδρο, Kόκκινο-Mαύρο Δένδρο ή BB-δένδρο, (a,b) δένδρα, το BB[α] δένδρο, Yβριδικές δομές δεδομένων. Tries, Δυναμικό Interpolation ψάξιμο, Tο interpolation search tree (IST), Tο ψάξιμο στο interpolation search tree. Union-find, Hashing, Hashing με αλυσίδες, Hashing με ανοικτή διεύθυνση (open addressing), Extendible Hashing. Ευρετηρίαση στη Δευτερεύουσα μνήμη. Διαχρονικές δομές δεδομένων. Δομές δεδομένων στο μοντέλο μηχανής RAM (van Emde Boas δέντρο και δομές που αξιοποιούν μεγάλα μήκη λέξεων).

Αξιολόγηση

Γραπτή εξέταση (70% του συνολικού βαθμού)

Project (30% στη συνολική βαθμολογία σε ομάδες από 1-3 άτομα, το project υπολογίζεται μόνο αν ο βαθμός γραπτής εξέτασης είναι >=5).

Για φοιτητές μεγαλύτερων ετών αρκεί η γραπτή εξέταση (100% του συνολικού βαθμού).

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

• Weiss M.A., Δομές Δεδομένων και Ανάλυση Αλγορίθμων με C++, 1/2023 BROKEN HILL PUBLISHERS LTD
• Μποζάνης Παναγιώτης Δ. Δομές Δεδομένων, 3η Έκδοση, 3η Έκδοση/2022 ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε.
• Kurt Mehlhorn, Peter Sanders, Αλγόριθμοι και Δομές Δεδομένων: Τα βασικά εργαλεία 1η/2013, ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ
• Γεωργακόπουλος Γ.Φ., Δομές Δεδομένων, 1η/2008, ΙΔΡΥΜΑ ΤΕΧΝΟΛΟΓΙΑΣ & ΕΡΕΥΝΑΣ-ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ 1η/2016