3632 Ειδικά Θέματα Αλγορίθμων

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

    URL: https://eclass.aueb.gr/courses/INF171/

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

    Περιεχόμενο

    Αλγόριθμοι για αριθμο-θεωρητικά προβλήματα και εφαρμογές στην κρυπτογραφία: ύψωση σε δύναμη, αλγόριθμος του Ευκλείδη για την εύρεση μέγιστου κοινού διαιρέτη, αριθμητική modulo, έλεγχος πρώτων αριθμών, κρυπτοσυστήματα RSA και ElGamal. Πολυπλοκότητα μέσης περίπτωσης και τυχαιοποιημένοι αλγόριθμοι: εισαγωγικά παραδείγματα, quicksort, στατιστικές τάξης, ανάλυση δυαδικών δένδρων αναζήτησης, κατακερματισμός. Αποσβεστική πολυπλοκότητα: UNION-FIND, αρθρωτά δένδρα. Αλγόριθμοι δυναμικού προγραμματισμού. Προβλήματα συνδυαστικής βελτιστοποίησης: κλίκα, ανεξάρτητο σύνολο, κάλυψη κορυφών, κάλυψη συνόλων, κύκλος και μονοπάτι Ηamilton, πρόβλημα περιοδεύοντα πωλητή (TSP), τρισδιάστατη αντιστοίχιση, άθροισμα υποσυνόλου, ακέραιο σακίδιο, διαμέριση, bin packing. Κλάσεις πολυπλοκότητας, NP-πληρότητα και πολυωνυμικές αναγωγές. Προσεγγιστικοί αλγόριθμοι: αλγόριθμοι σταθερού λόγου προσέγγισης, εφαρμογές στα προβλήματα κάλυψης κορυφών, στο πρόβλημα TSP υπό την τριγωνική ανισότητα, και σε προβλήματα χρονοπρογραμματισμού. Τυχαιοποιημένοι προσεγγιστικοί αλγόριθμοι. Προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS και FPTAS). Γραμμικός προγραμματισμός και ακέραιος γραμμικός προγραμματισμός. Μέγιστες ροές και ταιριάσματα. Συνθήκες συμπληρωματικής χαλάρωσης (complementary slackness), θεωρία δυικότητας γραμμικού προγραμματισμού. Χρήση γραμμικού προγραμματισμού για τον σχεδιασμό προσεγγιστικών αλγορίθμων (LP-rounding και primal-dual μεθοδολογίες).

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

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

    • Να αναλύουν την πολυπλοκότητα βασικών αριθμο-θεωρητικών αλγορίθμων, όπως η ύψωση σε δύναμη, ο υπολογισμός αριθμών Fibonacci, η εύρεση μέγιστου κοινού διαιρέτη, και ο έλεγχος για πρώτους αριθμούς.
    • Να σχεδιάζουν αλγορίθμους χρησιμοποιώντας την τεχνική του δυναμικού προγραμματισμού.
    • Να σχεδιάζουν προσεγγιστικούς αλγορίθμους για NP-πλήρη προβλήματα.
    • Να χρησιμοποιούν τεχνικές γραμμικού προγραμματισμού για τη μοντελοποίηση συνδυαστικών προβλημάτων και για την αλγοριθμική επίλυσή τους.

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

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

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

    • Εισαγωγή στους Αλγορίθμους, Τόμος 1, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (μετάφραση από αγγλικό πρωτότυπο), Πανεπιστημιακές Εκδόσεις Κρήτης, 2016.
    • Αλγόριθμοι, S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani (μετάφραση από αγγλικό πρωτότυπο), Εκδόσεις Κλειδάριθμος, 2009.
    • Σχεδιασμός Αλγορίθμων, J. Kleinberg, E. Tardos (μετάφραση από αγγλικό πρωτότυπο), Εκδόσεις Κλειδάριθμος, 2008.

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

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

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

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