ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ

Κωδικός Μαθήματος:     305
Εξάμηνο διδασκαλίας:     3ο Εξάμηνο

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

Στόχοι του μαθήματος
Η κατανόηση της αναγκαιότητας οργάνωσης των δεδομένων σε διαφορετικές δομές, στατικές-δυναμικές, γραμμικές-μη γραμμικές, είτε λόγω της φύσης του προβλήματος είτε λόγω του είδους και του περιβάλλοντος επεξεργασίας. Η απόκτηση δεξιοτήτων χειρισμού των διαφόρων δομών με τους κατάλληλους αλγορίθμους (αποθήκευσης, προσπέλασης, τροποποίησης) και η κατανόηση των προβλημάτων πολυπλοκότητας χώρου και χρόνου. Η απόκτηση δυνατοτήτων αξιολόγησης της καταλληλότερης δομής ανά εφαρμογή και της ανάλυσης αλγορίθμων ως προς την ορθότητα και την πολυπλοκότητα. Η κατανόηση της διαφοράς μεταξύ των επιπέδων λογικής δομής και φυσικής υλοποίησης και η ανάγκη ορισμού αφηρημένων τύπων και δομών δεδομένων. Η απόκτηση ικανοτήτων ορισμού και χειρισμού αφηρημένων τύπων και δομών με παραδείγματα χρήσης της Standard Τemplate Library.

Περιγραφή του μαθήματος
Γενικά περί αλγορίθμων. Είδη και Ανάλυση αλγορίθμων. Εισαγωγή στις γραμμικές δομές δεδομένων (πίνακες, στοίβες, ουρές, λίστες) και βασικοί αλγόριθμοι προσπέλασης και τροποποίησης. Μη γραμμικές δομές (δένδρα δυαδικά και ισοζυγισμένα, γραφήματα) και βασικοί αλγόριθμοι προσπέλασης και τροποποίησης. Προβλήματα εσωτερικής αναπαράστασης των δομών δεδομένων. Πολυπλοκότητα χρόνου-χώρου (πολυπλοκότητα χειρότερης περίπτωσης, πολυπλοκότητα μέσου όρου NP-complete). Αλγόριθμοι Ταξινόμησης (Insertion, Bubblesort, Quicksort, Heapsort, Shellsort, Merging Sort, Bucket and Tournament sort) και Σύζευξης. Εισαγωγή στους αφηρημένους τύπους και στις δομές δεδομένων. Η STL (Standard Τemplate Library). Θέματα οργάνωσης αρχείων. Μέθοδοι σχεδίασης αλγορίθμων (διαίρει και βασίλευε, αναδρομή, εξισορρόπησης, απληστίας, δυναμικός προγραμματισμός).
Εργαστήριο Μαθήματος: Δημιουργία και ανάλυση κώδικα για εμπέδωση της ύλης. Παρουσίαση πλήρους εφαρμογής που αξιοποιεί - συνδυάζει τις δομές δεδομένων και τους αλγόριθμους που έχουν αναλυθεί.

Ενδεικτική Βιβλιογραφία
  1. Δομές Δεδομένων, Ι. ΜΑΝΩΛΟΠΟΥΛΟΣ, Εκδόσεις Art of Text.
  2. Δομές Δεδομένων και Οργανώσεις Αρχείων, Χ. ΚΟΙΛΙΑΣ, Εκδόσεις Νέων Τεχνολογιών.
  3. Initiation à l’algorithmique et aux structures de données, 2. Récursivité et structures de données avancées, J. COURTIN, I. KOWARSKI, DUNOD-informatique.
  4. Data Structures and Algorithms, A. AHO, J, HOPCROFT, J. ULLMANN, Addison-Wesley, Reading, Mass.1983.
  5. Algorithms + Data Structures = Programs,  N. WIRTH, Prentice-Hall, Engelwood Cliffs, N.J., 1976.
  6. The art of computer programming, D.E. KNUTH, Addison-Wesley.
  7. Fundamentals of data structures, E. HOROWITZ, S. SAHNI, Computer Science Press.
  8. Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, R. SEDGEWICK, Pearson Higher Education, 1997