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

    Υποχρεωτικό Μάθημα Πυρήνα, Γ’ εξάμηνο, 7 μονάδες ECTS

    Διδάσκων: Μέλος ΕΔΙΠ Αικατερίνη Παπακωνσταντινοπούλου

    URL: https://eclass.aueb.gr/courses/INF231/

    Περιεχόμενο

    Εισαγωγή στην ανάλυση αλγορίθμων. Αναζήτηση και ταξινόμηση, ασυμπτωτικές προσεγγίσεις και συμβολισμοί. Στοίβες και ουρές: ορισμός, λειτουργίες, υλοποίηση με πίνακα. Συνδεδεμένες λίστες: μονή, διπλή και κυκλική σύνδεση, διάσχιση, εισαγωγή, διαγραφή. Δυαδικά δέντρα: ορισμοί και θεμελιώδη θεωρήματα, διάσχιση κατά βάθος και κατά πλάτος, αναδρομική και επαναληπτική διάσχιση, περίπατοι Euler. Δυαδικά δέντρα αναζήτησης: ορισμός, αναζήτηση, εισαγωγή, διαγραφή. Προσαρμοστικά, εκτατικά και τυχαία δυαδικά δέντρα αναζήτησης. Ισοζυγισμένα δέντρα αναζήτησης: δέντρα AVL, δέντρα 2-3, ερυθρόμαυρα δέντρα, δέντρα Β. Ουρές προτεραιότητας. Δυαδικοί σωροί: ορισμός, λειτουργίες, ταξινόμηση με σωρό. Υλοποίηση ουρών προτεραιότητας με δυαδικό σωρό. Πίνακες κατακερματισμού. Πολυωνυμικός κατακερματισμός. Συμπίεση χώρου διευθύνσεων: διαίρεση, πολλαπλασιασμός, αποκοπή. Διαχείριση συγκρούσεων: αλυσίδωση, γραμμική δοκιμή, διπλός κατακερματισμός. Εξωτερική αναζήτηση: δέντρα Β και πίνακες κατακερματισμού.

    Μαθησιακά Αποτελέσματα

    Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

    • Να περιγράφουν το ρόλο και τις λειτουργίες των σημαντικότερων δομών δεδομένων στην επιστήμη των υπολογιστών, όπως οι συνδεδεμένες λίστες, οι ουρές FIFO και LIFO, οι ουρές προτεραιότητας, τα δέντρα δυαδικής αναζήτησης και οι παραλλαγές τους.
    • Να αναλύουν την υπολογιστική πολυπλοκότητα των βασικών μεθόδων που υποστηρίζουν οι δομές δεδομένων που παρουσιάζονται στο μάθημα.
    • Να συγκρίνουν αλγορίθμους με βάση την χρονική και χωρική πολυπλοκότητά τους.
    • Να σχεδιάζουν νέους αλγορίθμους κάνοντας χρήση των δομών που παρουσιάζονται στο μάθημα.
    • Να επιλέγουν κατάλληλες δομές δεδομένων προς την επίλυση αλγοριθμικών προβλημάτων.

    Προαπαιτούμενα Μαθήματα

    Για να εγγραφεί στο μάθημα, ο φοιτητής πρέπει να έχει εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο είτε στο μάθημα «Εισαγωγή στον Προγραμματισμό Υπολογιστών» είτε στο μάθημα «Προγραμματισμός Υπολογιστών με JAVA». Συνιστάται στους φοιτητές να έχουν εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο και στα δύο άνω μαθήματα.

    Συνιστώμενη Βιβλιογραφία

    • Αλγόριθμοι σε Java, Μέρη 1-4, R. Sedgewick (μετάφραση από αγγλικό πρωτότυπο), Εκδόσεις Κλειδάριθμος, 2005.
    • Δομές Δεδομένων και Αλγόριθμοι στη Java, R. Lafore (μετάφραση από αγγλικό πρωτότυπο), 2η έκδοση, Εκδόσεις Γκιούρδας, 2008.
    • Δομές Δεδομένων, Γ. Φ. Γεωργακόπουλος, Πανεπιστημιακές Εκδόσεις Κρήτης, 2002.

    Διδακτικές και Μαθησιακές Μέθοδοι

    Διαλέξεις (2 διαλέξεις των 2 ωρών εβδομαδιαίως), εργαστηριακές ασκήσεις (2 ώρες εβδομαδιαίως), και ομαδικές προγραμματιστικές εργασίες (3 εργασίες κατά τη διάρκεια του εξαμήνου).

    Μέθοδοι Αξιολόγησης/Βαθμολόγησης

    Ο τελικός βαθμός ισούται με τον βαθμό της γραπτής τελικής εξέτασης, αν αυτός δεν είναι προβιβάσιμος και, σε περίπτωση που ο βαθμός της γραπτής τελικής εξέτασης είναι προβιβάσιμος, με τον σταθμισμένο μέσο όρο του βαθμού της γραπτής τελικής εξέτασης (με βάρος 70%) και του συνολικού βαθμού από τις ομαδικές προγραμματιστικές εργασίες (με βάρος 30%).