Τα περισσότερα ενδιαφέροντα προβλήματα συνδυαστικής βελτιστοποίησης είναι υπολογιστικά δύσβατα, NP-hard ή χειρότερα. Οι προσεγγιστικοί αλγόριθμοι αποτελούν την κατεξοχήν μέθοδο αντιμετώπισης τέτοιων προβλημάτων. Αποτελούν μία από τις πιο πλούσιες περιοχές της Θεωρίας Αλγορίθμων που, ύστερα από μια αλματώδη ανάπτυξη τα τελευταία 20 χρόνια, προσεγγίζει πια το σημείο ωριμότητας.
Το μάθημα θα έχει θεματικό χαρακτήρα με έμφαση σε τεχνικές σχεδιασμού αλγορίθμων. Θα εξεταστούν κυρίως αντιπροσωπευτικά αποτελέσματα των ακόλουθων μεθόδων.
Ιστοσελίδα μαθήματος:
http://www.di.uoa.gr/~sgk/teaching/grad/APPR-S11/
Περιέχει χρήσιμες πληροφορίες και καλό είναι να την επισκέπτεστε συχνά.
Εδώ θα βρίσκετε πληροφορίες για το μάθημα, τυχόν
σημειώσεις, ασκήσεις, ανακοινώσεις,
κλπ.
Το μεγαλύτερο κομμάτι του τελικού βαθμού (άνω του 60%) θα προέλθει από μία παρουσίαση ερευνητικής δουλειάς από τη βιβλιογραφία η οποία θα σχετίζεται άμεσα με τα περιεχόμενα του μαθήματος. Η επιλογή της εργασίας για τον κάθε φοιτητή θα γίνει σε συνεννόηση με το διδάσκοντα. Θα υπάρξουν ένα ή δυο σετ ασκήσεων με συμμετοχή μέχρι 25% στον τελικό βαθμό. Περίπου 15% θα προσμετρηθεί η παρουσία και η συμμετοχή στην τάξη. Είναι αυτονόητο πως θα είναι όλοι παρόντες στις παρουσιάσεις των συναδέλφων τους. Δεν θα υπάρξουν εξετάσεις.
Πρώτη άσκηση (δημοσίευση 18.03.2011, παράδοση 11.04.2011) | Βαθμολογία (Προσθήκη: Tue May 3 19:35:00 EEST 2011)
Δεύτερη άσκηση (δημοσίευση 09.05.2011, παράδοση 03.06.2011) | Βαθμολογία (Προσθήκη: Mon Jul 11 15:28:28 EEST 2011)
Τελική βαθμολογία μαθήματος (Προσθήκη: Tue Jul 12 18:04:42 EEST 2011)