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

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

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


Τα μαθήματα θα ξεκινήσουν την Τρίτη 12.10.2021. To μάθημα θα διεξάγεται με βάση τα ανακοινωμένα υγειονομικά πρωτόκολλα.




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

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

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

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

Ιστοσελίδα στην η-τάξη: https://eclass.uoa.gr/courses/DI538/
Προσβάσιμη μόνο μέσω ιδρυματικού λογαριασμού. Εδώ θα δημοσιεύονται όλες οι ανακοινώσεις και οι ασκήσεις του μαθήματος. Είναι απαραίτητη η εγγραφή όλων όσων επιθυμούν να παρακολουθήσουν το μάθημα.

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

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

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

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

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

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


Ασκήσεις

Δεν υπάρχουν ανακοινωμένες ασκήσεις.


http://www.di.uoa.gr/~sgk/teaching/grad/APPR/index.html
Τελευταία ανανέωση: Tue Oct 19 10:28:55 EEST 2021