Δομές Δεδομένων και Αλγόριθμοι

• Ορισμοί (δεδομένα, δομές δεδομένων, αφηρημένοι τύποι δεδομένων), αλγόριθμοι, πολυπλοκότητα αλγορίθμων • Πίνακες, δυαδική, γραμμική αναζήτηση. Διάταξη, διάταξη επιλογής, διάταξη φυσαλίδας. • Λίστες (συνεχόμενη, συνδεδεμένη), πράξεις (διαπέραση, εισαγωγή, διαγραφή, αναζήτηση), κατηγορίες συνδεδεμένης λίστας (διπλά συνδεδεμένη, κυκλική) • Ειδικές λίστες (στοίβα, ουρά, κυκλική ουρά, διπλή ουρά, ουρά προτεραιότητας) και πράξεις με αυτές • Δένδρα, δυαδικά δέντρα και διαπέραση, δυαδικά δέντρα αναζήτησης (αναζήτηση, εισαγωγή, διαγραφή), δέντρα σωροί (εισαγωγή, διαγραφή), υψηζυγισμένα, βαροζυγισμένα δένδρα • Γραφήματα ή γράφοι. Εύρεση μήκους μικρότερου μονοπατιού. • Σταδιακή χρησιμοποίηση όλων των παραπάνω στη λύση προβλημάτων με χρήση προγραμμάτων.

Στόχοι Μαθήματος

Σκοπός του μαθήματος είναι να: Γνωρίζει την έννοια της δομής δεδομένων (αφηρημένος τύπος δεδομένων) και τη διαφορά της από έναν ατομικό τύπο δεδομένων, τη λειτουργικότητα των δομών δεδομένων: πίνακας, λίστα, στοίβα, ουρά, δέντρο δυαδικής αναζήτησης, δέντρο σωρός Κατανοεί τους διαφορετικούς τρόπους με τους οποίους μία δομή δεδομένων μπορεί να αναπαρασταθεί στην κύρια μνήμη του υπολογιστή, τους διαφορετικούς αλγορίθμους διάταξης στοιχείων και τους διαφορετικούς τρόπους αναζήτησης στοιχείων (γραμμική, δυαδική) σε έναν πίνακα Μπορεί να υπολογίζει τις συναρτήσεις πολυπλοκότητας απλών αλγορίθμων, την τάξη μεγέθους μίας συνάρτησης πολυπλοκότητας από την αναλυτική της έκφραση, να υπολογίζει τη συνάρτηση απεικόνισης και τον τρόπο υλοποίησης ενός πίνακα όταν δίνεται ο τρόπος αναπαράστασής του και, αντιστρόφως, να υπολογίζουν τη διεύθυνση ενός τυχαίου στοιχείου ενός πίνακα από τη συνάρτηση απεικόνισης, να σχεδιάζει τροποποιήσεις επεκτάσεις ή συνδυασμούς των βασικών αλγορίθμων Να υλοποιεί προγράμματα που χρησιμοποιούν τις βασικές δομές δεδομένων Να αξιολογεί την αποδοτικότητα μίας δομής δεδομένων χρησιμοποιώντας τις έννοιες της χωρικής και χρονικής πολυπλοκότητας

Προαπαιτούμενες Γνώσεις

Καλή γνώση μαθηματικών (μαθηματικής ανάλυσης και γραμμικής άλγεβρας) μέσα από το μάθημα: Μαθηματικά. Καλή γνώση διαδικασιακού και/ή αντικειμενοστρεφούς προγραμματισμού.

Περιεχόμενα

Ορισμοί (δεδομένα, δομές δεδομένων, αφηρημένοι τύποι δεδομένων), αλγόριθμοι, πολυπλοκότητα αλγορίθμων Πίνακες, δυαδική, γραμμική αναζήτηση. Διάταξη, διάταξη επιλογής, διάταξη φυσαλίδας. Λίστες (συνεχόμενη, συνδεδεμένη), πράξεις (διαπέραση, εισαγωγή, διαγραφή, αναζήτηση), κατηγορίες συνδεδεμένης λίστας (διπλά συνδεδεμένη, κυκλική) Ειδικές λίστες (στοίβα, ουρά, κυκλική ουρά, διπλή ουρά, ουρά προτεραιότητας) και πράξεις με αυτές Δένδρα, δυαδικά δέντρα και διαπέραση, δυαδικά δέντρα αναζήτησης (αναζήτηση, εισαγωγή, διαγραφή), δέντρα σωροί (εισαγωγή, διαγραφή), υψηζυγισμένα, βαροζυγισμένα δένδρα Γραφήματα ή γράφοι. Εύρεση μήκους μικρότερου μονοπατιού. Σταδιακή χρησιμοποίηση όλων των παραπάνω στη λύση προβλημάτων με χρήση προγραμμάτων.