Τα περισσότερα ενδιαφέροντα προβλήματα συνδυαστικής βελτιστοποίησης είναι υπολογιστικά δύσβατα, NP-hard ή χειρότερα. Οι προσεγγιστικοί αλγόριθμοι αποτελούν την κατεξοχήν μέθοδο αντιμετώπισης τέτοιων προβλημάτων. Αποτελούν μία από τις πιο πλούσιες περιοχές της Θεωρίας Αλγορίθμων που, ύστερα από μια αλματώδη ανάπτυξη τις τελευταίες δεκαετίες, προσεγγίζει πια το σημείο ωριμότητας.
Το μάθημα θα έχει θεματικό χαρακτήρα με έμφαση σε τεχνικές σχεδιασμού αλγορίθμων. Θα εξεταστούν μεταξύ άλλων αντιπροσωπευτικά αποτελέσματα των ακόλουθων μεθόδων.Ιστοσελίδα στην η-τάξη: 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) την εργασία ή τις εργασίες που παρουσιάσατε.