Δομές Δεδομένων
Κωδικός: | 9214 |
Κατηγορία: | Υποχρεωτικό Ροής |
Κατεύθυνση: | Μαθηματικού Εφαρμογών |
Ροή: | Ροή Μ.Π.: Μαθηματικά Πληροφορικής |
Εξάμηνο: | 6ο |
Ώρ./εβδ.: | 3 |
Ιστότοπος Μαθήματος: | mycourses.ntua.gr/courses/SEMFE1155 |
Σχολή: | ΣΠΜ |
Περιγραφή Μαθήματος
Εισαγωγή. Δομές δεδομένων και αλγόριθμοι. Ασυμπτωτική ανάλυση. Δυαδική αναζήτηση. Αλγόριθμοι ταξινόμησης. Συγκριτικοί αλγόριθμοι ταξινόμησης (ταξινόμηση «εισαγωγής», Ταξινόμηση «επιλογής», ταξινόμηση «φυσαλίδας», «ταχεία» ταξινόμηση (quick sort), ταξινόμηση συγχώνευσης). Κάτω όριο για συγκριτικούς αλγόριθμους ταξινόμησης. Αλγόριθμοι ταξινόμησης μέσω κατανομής (ταξινόμηση «κάδου/δοχείου» (bucket sort, bin sort), ταξινόμηση «βάσης» (radix sort)). Απλές Δομές Δεδομένων. Διανύσματα. Λίστες. Αφηρημένοι Τύποι Δεδομένων (ΑΤΔ). Απλές ουρές, στοίβα (stack), ουρά FIFO. Δένδρικές δομές (στατικά δένδρα, διελεύσεις δένδρων, δυναμικά δένδρα). Ο ΑΔΤ «Ουρά προτεραιότητας (priority queue)». Δομή σωρού (υλοποίηση με δενδρική δομή, υλοποίηση με διάνυσμα). Ο ΑΔΤ «Λεξικό» (dictionary) ή «Πίνακας συμβόλων» (symbol table). Δένδρα αναζήτησης. Δένδρα‐(a,b). Β-δένδρα Κατακερματισμός (με αλυσίδες (chaining), γραμμική δοκιμή (linear probing) Ο ΑΔΤ «Ταξινομημένο λεξικό». Ο ΑΔΤ «Ξένα μεταξύ τους σύνολα» (disjoint sets).