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

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

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


Την Πέμπτη 29/03 θα γίνει μάθημα αναπλήρωσης στην Αίθουσα Β', 10:00-11:00.



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

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

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

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

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

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

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

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

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

Προτάσεις για τις παρουσιάσεις. (Προσθήκη Mon Apr 2 17:37:39 EEST 2018)

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


Ασκήσεις

Πρώτη άσκηση (δημοσίευση Mon Mar 5 14:40:15 EET 2018)

Δεύτερη άσκηση (δημοσίευση Mon Apr 2 17:37:39 EEST 2018)

Τρίτη άσκηση (δημοσίευση Tue May 8 15:12:36 EEST 2018)



http://www.di.uoa.gr/~sgk/teaching/grad/APPR/index.html
Τελευταία ανανέωση: Tue May 8 15:12:36 EEST 2018