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

Σκοπός μαθήματος

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

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

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

Περιγραφή μαθήματος

Η ανάγκη για αποτελεσματικούς αλγορίθμους προκύπτει σχεδόν σε κάθε τομέα της επιστήμης των υπολογιστών μολονότι το είδος του προβλήματος που πρέπει να επιλυθεί, η έννοια του ποιος αλγόριθμος είναι αποτελεσματικός και το μοντέλο  υπολογισμού μπορεί να διαφέρει  από τομέα σε τομέα. Στο πλαίσιο του μαθήματος, θα μελετηθούν τεχνικές  σχεδιασμού αποτελεσματικών αλγορίθμων και προηγμένες δομές δεδομένων, και θα μελετηθεί η εφαρμογή τους  σε διαφορετικά  πεδία εφαρμογής. Στις  τεχνικές που θα καλυφθούν περιλαμβάνονται ο δυναμικός προγραμματισμός, ο γραμμικός προγραμματισμός, η άπληστη τεχνική καθώς και πιθανοτικές τεχνικές. Θα μελετηθούν αλγόριθμοι ταξινόμησης και αναζήτησης, εύρεσης βέλτιστων μονοπατιών σε δίκτυα,  ελαχίστων επικαλυπτόντων δέντρων σε γραφήματα καθώς και αλγόριθμοι ροής σε δίκτυα. Επίσης, θα μελετηθούν προηγμένες δομές δεδομένων (Red-black trees, B trees) και θα καλυφθούν θέματα  αποδοτικής υλοποίησης και πειραματικής αξιολόγησης βασικών και προηγμένων δομών δεδομένων και αλγορίθμων.

Βιβλιογραφία

  1. Aho A.V., J.E. Hopcroft and J.D. Ullman. The Design and Analysis of Computer Algorithms,  Addison Wesley, 2008
  2. T.H. Cormen, C.E. Leiserson , R.L. Rivest and C. Stein. Εισαγωγή στους Αλγορίθµους, Ελληνική Έκδοση, Πανεπιστηµιακές Εκδόσεις Κρήτης, 2012
  3. Peter Brass.  Advanced Data Structures. Cambridge University Press, 2008
  4. J. Kleinberg και E. Tardos, Σχεδιασμός Αλγορίθμων, Εκδόσεις  Κλειδάριθμος, 2008
  5. S. Dasgupta, C. Papadimitriou και U. Vazirani.  Αλγόριθμοι, Εκδόσεις  Κλειδάριθμος
  6.  R. Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice-Hall, 1993
  7. R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983
  8.  K. Mehlhorn and S. Naeher, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, 1999
  9. M. Mueller-Hannemanni and S. Schirra, Algorithm Engineering – Bridging the Gap between Algorithm Theory and Practice, Springer 2010