Στόχοι
Σκοπός του μαθήματος είναι η παρουσίαση τεχνικών, ιδιοτήτων, υλοποιήσεων και εφαρμογών βασικών αλλά και προηγμένων αλγορίθμων και δομών δεδομένων. Θα συζητηθούν επίσης: (α) ζητήματα δημιουργίας περιβαλλόντων και βιβλιοθηκών λογισμικού που επιτρέπουν την εύκολη υλοποίηση και πειραματική αξιολόγηση αλγορίθμων, και (β) ζητήματα μεθοδολογίας σε ότι αφορά την πειραματική έρευνα αλγορίθμων και δομών δεδομένων, καθώς και σε ότι αφορά τη διαδικασία μετατροπής των απαιτήσεων του χρήστη σε αποδοτικές αλγοριθμικές λύσεις και υλοποιήσεις. Σαν πραγματικό περιβάλλον υλοποίησης, θα χρησιμοποιηθεί η γλώσσα C++ μαζί με τις βιβλιοθήκες LEDA, STL και BOOST.
Διδασκαλία και Εργαστήριο
- Παραδόσεις:
- Τετάρτη, 13-15, B4
- Φροντιστήριο:
- Δευτέρα, 15-17, Β3
- Εργαστήριο:
- Δευτέρα 17-19 και Τρίτη 15-17, Υπολογιστικό Κέντρο
Βιβλιογραφία
Βασικά Συγγράμματα
- Υλοποίηση Αλγορίθμων και Δομών Δεδομένων
- A.Alexandrescu, Modern C++ design: Programming and Design Patterns Applied, Addison-Wesley, 2001.
- K. Mehlhorn and S. Naeher, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, 1999.
- M.A. Weiss, Data structures and problem solving with C++, 2nd Edition, Addison-Wesley, 2000.
- H Γλώσσα C++
- A.Koenig and B.Moo, Accelerated C++, Addison-Wesley, 2000.
- S.B. Lippman and J. Lajoie, C++ Primer, 3rd Edition, Addison-Wesley, 1998.
Βοηθητικές Αναφορές
- Υλοποίηση Αλγορίθμων και Δομών Δεδομένων
- T. Budd, Data structures in C++ using the standard template library, Addison-Wesley, 1998.
- F. Carrano, P. Helman, and R. Veroff, Data abstraction and problem solving with C++, 2nd Edition, Addison-Wesley, 1998.
- N.Jossutis, The C++ standard library: a tutorial and a reference, Addison Wesley, 1999.
- E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++, Computer Science Press, 1995.
- S. Sahni, Data structures, algorithms and applications in C++, WCB/McGraw-Hill, 1998.
- J.Siek, A.Lumsdaine, and L.Lee, The Boost Graph Library: User Guide and Reference Manual, Addison Wesley, 2002.
- C++ και Αντικειμενοστρεφής Προγραμματισμός
- T. Budd, An Introduction to Object-Oriented Programming, 2nd Edition, Addison-Wesley, 1997.
- H.M. Deitel and P.J. Deitel, C++ : How to Program, 2nd Edition, Prentice-Hall, 1998.
- E. Gamma, R. Helms, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.
- S. Meyers, Effective C++, 2nd Edition, Addison-Wesley, 1997.
- B. Stroustrup, The C++ Programming Language, 3rd Edition, Addison-Wesley, 1997.
Σχολιασμένη Βιβλιογραφία
LEDA, STL, και BOOST
Οι βιβλιοθήκες λογισμικού LEDA, STL, και BOOST είναι απαραίτητες για αυτό το μάθημα. Τα manuals μπορείτε να τα βρείτε στους ακόλουθους συνδέσμους:
Άλλοι σύνδεσμοι με χρήσιμες πληροφορίες
Υλικό Παραδόσεων και Φροντιστηρίων
Παραδόσεις και Φροντιστήρια
- 1.
- Εισαγωγικά [PDF]
- Εισαγωγή στη C++ - 1 [PDF]
- Εισαγωγή στη C++ - 2 [PDF]
- Εισαγωγή στη C++ - 3 [PDF]
- Standard Template Library [PDF]
- 2.
- Υλοποίηση και Πειραματική Έρευνα Αλγορίθμων [PDF]
- Δοκιμή, Έλεγχος Ορθότητας, και Πειραματική Αξιολόγηση Αλγορίθμων [PDF]
- 3.
- Εισαγωγή στη LEDA - 1 [PDF]
- Εισαγωγή στη LEDA - 2 [PDF]
- 4.
- Γραφήματα και Βασικοί Αλγόριθμοι [PDF]
- 5.
- Συντομότερες Διαδρομές Ι [PDF]
- 6.
- Ο τύπος graphwin της LEDA [PDF]
- Υλοποίηση Παραμετρικών Τύπων [PDF]
- 7.
- Συντομότερες Διαδρομές ΙI [PDF]
- 8.
- Μέγιστη Ροή [PDF]
- 9.
- Εισαγωγη στη Boost Graph Library [PDF]
- 10. :
- Σχεδίαση Κλάσεων βασισμένη σε Πολιτικές [PDF]
Βοηθητικό Υλικό
- Το εργαλείο Make
- Χρήση της LEDA
- Παρουσίαση εργασίας: How to Present a Paper on Experimental Work with Algorithms, C.C. McGeoch and B.M.E. Moret, in SIGACT News 30:4 (Dec. 1999), pp. 85-90.
Παρουσιάσεις Μεταπτυχιακών Φοιτητών
Λίστα Ηλεκτρονικού Ταχυδρομείου
Για την καλύτερη οργάνωση του μαθήματος και την ορθολογιστικότερη χρήση του ηλεκτρονικού ταχυδρομείου, έχει δημιουργηθεί μία λίστα ηλεκτρονικού ταχυδρομείου για το μάθημα. Η διεύθυνση της είναι:
alg-eng-list @ ceid . upatras . gr
Στην λίστα αυτή μπορείτε να στέλνετε τυχόν απορίες σας (οι οποίες μπορεί να είναι και απορίες άλλων).
ΠΡΟΣΟΧΗ: Όλη η επικοινωνία που θα αφορά το μάθημα (π.χ. ανακοινώσεις ασκήσεων, διάφορα διαδικαστικά θέματα, λεπτομέρειες για τις εξετάσεις, κλπ) θα γίνεται αποκλειστικά μέσω της λίστας alg-eng-list. Για τό λόγο αυτό, παρακαλούμε να εγγραφείτε άμεσα στην παραπάνω λίστα.
Εγγραφή στη λίστα: Στείλτε ένα κενό μήνυμα στην διεύθυνση alg-eng-list-subscribe @ ceid . upatras . gr
Προβλήματα με τη λίστα: Στείλτε μήνυμα στην διεύθυνση alg-eng-list-owner @ ceid . upatras . gr
Ασκήσεις
ΟΔΗΓΙΕΣ ΠΑΡΑΔΟΣΗΣ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΩΝ ΑΣΚΗΣΕΩΝ
Άσκηση 1 [PDF] Προθεσμία Υποβολής:
Βαθμολογία
Άσκηση 2 [PDF] Προθεσμία Υποβολής:
Βαθμολογία