Τεχνολογίες Υλοποίησης Αλγορίθμων

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

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

Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα έχουν αναπτύξει τις ακόλουθες δεξιότητες:

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

Περιεχόμενο (ύλη)

• Χαρακτηριστικά, ιδιαιτερότητες και σημασία ανάπτυξης τεχνολογιών υλοποίησης αλγορίθμων.
• Δημιουργία περιβαλλόντων και βιβλιοθηκών λογισμικού που επιτρέπουν την εύκολη υλοποίηση και πειραματική αξιολόγηση αλγορίθμων και δομών δεδομένων.
• Ζητήματα μεθοδολογίας σε ότι αφορά την πειραματική έρευνα αλγορίθμων και δομών δεδομένων. Εφαρμογή της επιστημονικής μεθόδου. Αναπαραγωγή πειραμάτων. Δημιουργία και αναζήτηση δεδομένων δοκιμής.
• Έλεγχος ορθότητας προγραμμάτων. Αλγόριθμοι και προγράμματα πιστοποίησης.
• Αποδοτική υλοποίηση και πειραματική αξιολόγηση βασικών και προηγμένων αλγορίθμων και δομών δεδομένων. Παραδείγματα μελέτης: αλγόριθμοι γραφημάτων, αλγόριθμοι συντομότερων διαδρομών, αλγόριθμοι εύρεσης μέγιστης ροής.
• Εμπλουτισμός υλοποιήσεων και αύξηση της απόδοσής τους με ευρετικές μεθόδους.
• Αριθμητικά σφάλματα και μέθοδοι περιορισμού τους.
• Ζητήματα μεθοδολογίας σε ότι αφορά τη διαδικασία μετατροπής των απαιτήσεων του χρήστη σε αποδοτικές αλγοριθμικές λύσεις και υλοποιήσεις.
• Περιβάλλον υλοποίησης: γλώσσα C++ μαζί με τις βιβλιοθήκες LEDA, STL και BOOST.
• Ειδικά θέματα: οπτικοποίηση αλγορίθμων, γενικευμένος προγραμματισμός αρχετύπων, σχεδίαση κλάσεων βασισμένη σε πολιτικές.

Αξιολόγηση

Γλώσσα αξιολόγησης: Ελληνική (Αγγλικά αν χρειαστεί)

Αξιολόγηση (τα κριτήρια βρίσκονται στην ιστοσελίδα του μαθήματος): - Προγραμματιστικές ασκήσεις (30% του τελικού βαθμού). - Τελική εξέταση (70% του τελικού βαθμού).

Τελική εξέταση: προφορική και γραπτή τελική εξέταση σε εκτενή προγραμματιστική εργασία που ανατίθεται ατομικά σε κάθε φοιτητή. Εξέταση στον κώδικα καθώς και στην αναφορά υλοποίησης και πειραματικής αξιολόγησης που υποβάλει ο φοιτητής.

Σειρά προγραμματιστικών ασκήσεων με στόχο την εξοικείωση, εξάσκηση και απόκτηση εμπειρίας:

• Στην αποδοτική υλοποίηση σύνθετων αλγορίθμων και δομών δεδομένων στη γλώσσα C++.
• Στη χρήση των περιβαλλόντων και βιβλιοθηκών ανάπτυξης αλγορίθμων LEDA και Boost.
• Στη χρήση των τεχνολογιών υλοποίησης αλγορίθμων που διδάσκονται στο μάθημα.
• Στη σωστή διεξαγωγή πειραματικών αξιολογήσεων υλοποιημένων αλγορίθμων και δομών δεδομένων.
• Στην ερμηνεία των πειραματικών αποτελεσμάτων και των σφαλμάτων που ενδεχομένως εμπεριέχουν.

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

• K. Mehlhorn and S. Naeher, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, 1999.
• M. Mueller-Hannemann and S. Schirra, Algorithm Engineering - Bridging the Gap between Algorithm Theory and Practice, Springer 2010.
• C.C. McGeoch, A Guide to Experimental Algorithmics, Cambridge University Press, 2012.
• A.Alexandrescu, Modern C++ design: Programming and Design Patterns Applied, Addison-Wesley, 2001.
• M.A. Weiss, Data structures and problem solving with C++, 2nd Edition, Addison-Wesley, 2000.
• A. Koenig and B.Moo, Accelerated C++, Addison-Wesley, 2000.
• S.B. Lippman and J. Lajoie, C++ Primer, 3rd Edition, Addison-Wesley, 1998.
• N.Jossutis, The C++ standard library: a tutorial and a reference, Addison Wesley, 1999.
• J.Siek, A.Lumsdaine, and L.Lee, The Boost Graph Library: User Guide and Reference Manual, Addison Wesley, 2002.
• Gamma, R. Helms, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.
• Διδακτικές σημειώσεις και διαφάνειες που αναρτώνται στην ιστοσελίδα του μαθήματος.

-Συναφή επιστημονικά περιοδικά:

• ACM Journal of Experimental Algorithmics.
• Algorithmica, Springer.
• Journal of Discrete Algorithms, Elsevier.