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

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

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


Τα μαθήματα θα ξεκινήσουν την Τρίτη 01.10.2019.

Τελική βαθμολογία του μαθήματος (προσθήκη Thu Feb 13 13:03:33 EET 2020).



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

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

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

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

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

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

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

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

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

Προτάσεις για τις παρουσιάσεις. (Προσθήκη Wed Oct 30 15:16:07 EET 2019)

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


Ασκήσεις

Πρώτη άσκηση (δημοσίευση Thu Oct 10 15:33:46 EEST 2019)

Δεύτερη άσκηση (δημοσίευση Tue Oct 22 13:02:45 EEST 2019) Bαθμολογία (Προσθήκη: Tue Nov 12 12:49:36 EET 2019)

Τρίτη άσκηση (δημοσίευση Fri Nov 22 19:49:41 EET 2019)

Τέταρτη άσκηση (δημοσίευση Fri Dec 6 15:59:08 EET 2019, διόρθωση στο Πρόβλημα 3 Tue Dec 17 14:12:32 EET 2019)



http://www.di.uoa.gr/~sgk/teaching/grad/APPR/index.html
Τελευταία ανανέωση: Thu Feb 13 13:03:33 EET 2020