Προσεγγιστικοί Αλγόριθμοι

Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Συνδιδασκαλία με το ΜΠΛΑ
Χειμερινό Εξάμηνο 2015-2016

Ώρες διδασκαλίας: Τρίτη 13:00-15:00 (αίθουσα Ζ' Πληροφορικής), Τετάρτη 15:00-17:00 (αίθουσα Ζ' Πληροφορικής).
Διδάσκων: Σταύρος Κολλιόπουλος
Γραφείο: Β6, κτήριο Πληροφορικής
Email: id@host.uoa.gr όπου host di και id sgk
Ώρες επικοινωνίας: Τετάρτη, 14:00 - 15:00 στο γραφείο Β6 ή με ραντεβού.






Περιεχόμενο Μαθήματος

Τα περισσότερα ενδιαφέροντα προβλήματα συνδυαστικής βελτιστοποίησης είναι υπολογιστικά δύσβατα, NP-hard ή χειρότερα. Οι προσεγγιστικοί αλγόριθμοι αποτελούν την κατεξοχήν μέθοδο αντιμετώπισης τέτοιων προβλημάτων. Αποτελούν μία από τις πιο πλούσιες περιοχές της Θεωρίας Αλγορίθμων που, ύστερα από μια αλματώδη ανάπτυξη τα τελευταία 20 χρόνια, προσεγγίζει πια το σημείο ωριμότητας.

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

Διαδικαστικά

Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/grad/APPR/
Περιέχει χρήσιμες πληροφορίες και καλό είναι να την επισκέπτεστε. Εδώ θα βρίσκετε πληροφορίες για το μάθημα, τυχόν ασκήσεις, ανακοινώσεις, κλπ.

Δεν θα ακολουθήσουμε αποκλειστικά ένα εγχειρίδιο. Δύο καλά βιβλία που καλύπτουν τα περισσότερα από τα θέματα του μαθήματος είναι τα εξής: Ένα παλιότερο αλλά πάντα χρήσιμο σύγγραμμα:

Δεκάδες άλλες πηγές είναι διαθέσιμες, βλ. διαδίκτυο.

Θα υπάρξουν δυο ή τρία σετ ασκήσεων. Αν είναι δύο, θα μετρήσουν για το 30% του τελικού βαθμού. Εάν υπάρξει τρίτο σετ, η συνεισφορά θα είναι συνολικά 40%. Με 10% θα προσμετρηθεί η παρουσία και η συμμετοχή στην τάξη. Το υπόλοιπο κομμάτι του τελικού βαθμού θα προέλθει από παρουσίαση ερευνητικής εργασίας από τη βιβλιογραφία η οποία θα σχετίζεται άμεσα με τα περιεχόμενα του μαθήματος. Η επιλογή της εργασίας για τον κάθε φοιτητή θα γίνει σε συνεννόηση με το διδάσκοντα. Είναι αυτονόητο πως θα είναι όλοι παρόντες στις παρουσιάσεις των συναδέλφων τους. Δεν θα υπάρξουν εξετάσεις.

Δεν θα ανατεθεί παρουσίαση, ούτε θα σταλεί βαθμός για όσους-όσες δεν έρχονται τακτικά, κατά την κρίση του διδάσκοντα, στις παραδόσεις.

Προτάσεις για τις παρουσιάσεις. (Προσθήκη Fri Dec 4 15:20:49 EET 2015)

Η παρουσίαση πρέπει να βασίζεται σε διαφάνειες που θα έχουν παραχθεί ηλεκτρονικά. Η διάρκεια της θα είναι μέχρι 45 λεπτά ώστε να υπάρχει χρόνος για ερωτήσεις. Μετά την προφορική παρουσίαση πρέπει να στείλετε στο διδάσκοντα τα εξής αρχεία, αποκλειστικά σε μορφή pdf: 1) το αρχείο με τις διαφάνειες 2) κριτική περίληψη της εργασίας που παρουσιάσατε, το πολύ μέχρι 2 σελίδες χωρίς τις αναφορές 3) την εργασία ή τις εργασίες που παρουσιάσατε.


Ασκήσεις

Πρώτη άσκηση (δημοσίευση 20.10.2015, παράδοση 03.11.2015) (Προσθήκη: Τρι 20 Οκτ 2015 19:17:02 EEST) | Βαθμολογία (Προσθήκη: Fri Dec 4 15:20:49 EET 2015)

Δεύτερη άσκηση (δημοσίευση Fri Nov 27 16:43:38 EET 2015, παράδοση 16.12.2015) | Βαθμολογία (Προσθήκη: Tue Jan 19 16:09:43 EET 2016)


Τελική βαθμολογία μαθήματος (Προσθήκη: Tue Feb 23 12:18:36 EET 2016)



http://www.di.uoa.gr/~sgk/teaching/grad/APPR/index.html
Τελευταία ανανέωση: Tue Feb 23 12:18:36 EET 2016