3ο εξάμηνο


Μάθημα: Αλγόριθμοι & Δομές Δεδομένων



Τίτλος μαθήματος Αλγόριθμοι και Δομές Δεδομένων
Κωδικός μαθήματος ΜΚ17
Είδος μαθήματος Υποχρεωτικό
Επίπεδο μαθήματος Προπτυχιακό
Έτος σπουδών 2ο
Εξάμηνο 3ο
Πιστωτικές μονάδες ECTS 5
Ιστοσελίδα eclass.uowm.gr/courses/ICTE267/
Ώρες ανά εβδομάδα 4
Διδάσκων Σταματία Μπίμπη (Έπικουρη Καθηγήτρια)
Περιεχόμενο μαθήματος Συγκεκριμένοι και Αφαιρετικοί Τύποι Δεδομένων. Σύνθετες Δομές Δεδομένων. Πίνακες, Εγγραφές, Συνδεδεμένες Λίστες, Στοίβες, Ουρές. Αναδρομικοί Αλγόριθμοι. Αλγόριθμοι Αναζήτησης και Ταξινόμησης. Γραφήματα και Δένδρα. Δένδρα Αναζήτησης. Κατακερματισμός. Προγραμματισμός σε C.
Αναμενόμενα μαθησιακά αποτελέσματα και δεξιότητες Ο βασικός στόχος του μαθήματος είναι η μελέτη των βασικών δομών δεδομένων και αλγορίθμων. Η μελέτη περιλαμβάνει τη θεωρητική ανάλυσή τους δίνοντας έμφαση στις εφαρμογές της κάθε δομής. Πιο συγκεκριμένα, μελετώνται: πίνακες, λίστες, στοίβες, ουρές προτεραιότητας, σωροί, δένδρα αναζήτησης, κατακερματισμός, βασικοί αλγόριθμοι αναζήτησης και ταξινόμησης. Το μάθημα δίνει έμφαση στην χρήση Αφηρημένων Τύπων Δεδομένων για την απεικόνιση των βασικών δομών καθώς και την υλοποίηση τους με τη γλώσσα προγραμματισμού JAVA. To μάθημα έχει ως στόχο να εξοικειώσει τους φοιτητές στη χρήση και ανάπτυξη ΑΤΔ, στον προγραμματισμό τους και τη σύνδεση τους με πραγματικές εφαρμογές. Οι φοιτητές που ολοκληρώνουν επιτυχώς το μάθημα Αλγόριθμοι και Δομές Δεδομένων θα πρέπει να είναι σε θέση να:
  • Να αναλύουν και να συγκρίνουν την αποδοτικότητα αλγορίθμων βάσει των τάξεων Ο, Ω και Θ.
  • Να χρησιμοποιούν, να υλοποιούν και να επεκτείνουν τις δομές δεδομένων όπως πίνακες, λίστες, ουρές, διπλοουρές και στοίβες και να γνωρίζουν τις εφαρμογές τους.
  • Να εφαρμόζουν τους αλγόριθμους που θα μελετηθούν στο μάθημα σε τυχαία δεδομένα.
  • Να επιλέγουν ή και να δημιουργούν τις κατάλληλες δομές δεδομένων και τους κατάλληλους αλγόριθμους για υλοποίηση αφηρημένων τύπων δεδομένων.
  • Να σχεδιάζουν και να υλοποιούν αποδοτικές λύσεις σε σύνθετα υπολογιστικά προβλήματα.
  • Να έχουν καταννοήσει και να υλοποιούν "συγκριτικούς" αλγόριθμους ταξινόμησης αλλά και αλγόριθμους ταξινόμησης "κατανομής"
  • Να μπορύν να υλοποίησουν και να τροποποίησουν βασικές δομές δεδομένων ισοζυγισμένων δέντρων όπως τα δέντρα AVL, τα ερθρόμαυρα αλλά και τα δέντρα a,b
  • Να εκτελούν ένωση εύρεση σε ξένα μεταξύ τους σύνολα
  • Να μπορούν να χρησιμοποιούν διάφορες τεχνικές κατακερματισμού για την αποθήκευση δεδομένων με βάση το κλείδι και το μέγεθος του πίνακα αποθήκευσης.
  • Να χειρίζονται βασικές λειτουργίες σε ουρές προτεραιότητας όπως η συνένωση ουρών και απομάκρυνση ελαχίστου στοιχείου.
Προαπαιτούμενα μαθήματα Κανένα
Μέθοδοι διδασκαλίας Διαλέξεις, ασκήσεις στον πίνακα, υλοποίηση βασικών αλγορίθμων σε C, ασκήσεις σε υπολογιστή
Αξιολόγηση Δύο υποχρεωτικά σετ εργασιών με τελική προφορική εξέταση (30%) Τελική Γραπτή Εξέταση (70%)
Γλώσσα διδασκαλίας Ελληνική
Βιβλιογραφία
  • ] S. Sahni. Δομές Δεδομένων, Αλγόριθμοι και Εφαρμογές στην C++ .
  • Π. Μποζάνης. Αλγόριθμοι: Σχεδιασμός και Ανάλυση. Εκδόσεις Τζιόλα, Θεσσαλονίκη, 2003.
  • ] Γ.Φ. Γεωργακόπουλος. Δομές Δεδομένων, Έννοιες, Τεχνικές και Αλγόριθμοι. Πανεπιστημιακές Εκδόσεις Κρήτης
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms (2nd Edition). The MIT Press, 2003.
  • K. Mehlhorn. Data Structures and Algorithms. Springer Verlag, EATCS Monographs, 1984.
  • G. Brassard and P. Bratley. Algorithmics: Theory and Practice.Prentice-Hall, 1988.


Διδάσκων: Μπίμπη Σταματία