8143 Συνδυαστική Βελτιστοποίηση

    Μάθημα Επιλογής, Ζ’ εξάμηνο, 6 μονάδες ECTS

    Διδάσκων: Αναπληρωτής Καθηγητής Ιωάννης Μούρτος

    URL: https://edu.dmst.aueb.gr/

    Περιεχόμενο

    Το μάθημα εξετάζει τη θεωρία, τους αλγορίθμους και τις εφαρμογές της διακριτής (επίσης γνωστής και ως συνδυαστικής) βελτιστοποίησης, με έμφαση σε προβλήματα που αφορούν ροές, μονοπάτια και ταιριάσματα σε γραφήματα. Συγκεκριμένα, το μάθημα παρουσιάζει αλγορίθμους για τα προβλήματα του συντομότερου μονοπατιού, της μέγιστης ροής, της ροής ελαχίστου κόστους, του ταιριάσματος μέγιστου μεγέθους ή μέγιστου βάρους (κυρίως σε διμερή γραφήματα) και, τέλος, του ευσταθούς ταιριάσματος σε διμερή γραφήματα. Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με βασικές αρχές σχεδιασμού αλγορίθμων και ειδικότερα με αλγορίθμους διακριτής βελτιστοποίησης, οι οποίοι καταρχήν εφαρμόζονται σε γραφήματα, καθώς και με αλγορίθμους Ακέραιου Προγραμματισμού. Πέραν της κατανόησης των βασικών εννοιών στόχος, είναι η διερεύνηση εφαρμογών τέτοιων προβλημάτων (δηλαδή προβλημάτων ροής, μονοπατιών και ταιριασμάτων σε δίκτυα) σε πραγματικά προβλήματα βελτιστοποίησης.

    Μαθησιακά Αποτελέσματα

    Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

    • Να περιγράφουν και να χειρίζονται τις θεμελιώδεις έννοιες, τα βασικά θεωρήματα και τις μεθόδους ή αλγορίθμους Συνδυαστικής Βελτιστοποίησης.
    • Να εκτελούν τους υπολογισμούς για συγκεκριμένες μεθόδους ή αλγορίθμους Συνδυαστικής Βελτιστοποίησης σε λελογισμένου μεγέθους προβλήματα, π.χ., βήματα αλγορίθμου μέγιστης ροής, βήματα ακέραιου προγραμματισμού.
    • Να μοντελοποιούν πραγματικά προβλήματα από ένα εύρος εφαρμογών ως προβλήματα Συνδυαστικής Βελτιστοποίησης και να προσδιορίζουν τη κατάλληλη μέθοδο ή αλγόριθμο βελτιστοποίησής τους.
    • Να αντιλαμβάνονται τις αποδείξεις των σχετικών θεωρημάτων και της γενικότερης μαθηματικής θεμελίωσης του Συνδυαστικής Βελτιστοποίησης, να μπορούν να επικαλούνται συγκεκριμένα θεωρήματα (π.χ. μέγιστης ροής-ελάχιστης τομής) προκειμένου να επιλύσουν αποτελεσματικότερα σχετικά προβλήματα και να μπορούν να διατυπώσουν τις απλούστερες από αυτές τις αποδείξεις.
    • Να μελετούν αυτόνομα και να εμβαθύνουν στην τρέχουσα βιβλιογραφία από επιστημονικά περιοδικά και βιβλία Συνδυαστικής Βελτιστοποίησης, ακόμη και σε γνωστικές περιοχές οι οποίες οριακά εντάσσονται στο περιεχόμενο του μαθήματος.

    Προαπαιτούμενα Μαθήματα

    Δεν υπάρχουν υποχρεωτικά προαπαιτούμενα μαθήματα. Όμως, συνιστάται ο φοιτητής να έχει εξεταστεί επιτυχώς στα μαθήματα «Μαθηματικά Ι», Διακριτά Μαθηματικά» και «Μαθηματικά ΙΙ» σε προηγούμενο εξάμηνο.

    Συνιστώμενη Βιβλιογραφία

    • Διακριτή Βελτιστοποίηση, Π. Μηλιώτης, Ι. Μούρτος, Εκδόσεις Οικονομικού Πανεπιστημίου Αθηνών, 2009.

    Διδακτικές και Μαθησιακές Μέθοδοι

    Διαλέξεις (2 διαλέξεις των 2 ωρών εβδομαδιαίως), φροντιστήρια (1 φροντιστήριο των 2 ωρών εβδομαδιαίως) και προαιρετικές γραπτές ομάδες ασκήσεων (εβδομαδιαίως).

    Μέθοδοι Αξιολόγησης/Βαθμολόγησης

    Ο τελικός βαθμός ισούται με τον βαθμό της γραπτής τελικής εξέτασης, αν δεν έχει υλοποιηθεί η προαιρετική εργασία. Αλλιώς, ισούται με τον σταθμισμένο μέσο όρο της γραπτής τελικής εξέτασης (με βάρος 80%) και της προαιρετικής εργασίας (με βάρος 20%)