3432 Αλγόριθμοι

    Υποχρεωτικό Μάθημα Πυρήνα, Δ’ εξάμηνο, 7 μονάδες ECTS

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

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

    Περιεχόμενο

    Προβλήματα, αλγόριθμοι, ορθότητα και πολυπλοκότητα, παραδείγματα. Ανάλυση αλγορίθμων: αύξηση συναρτήσεων και ασυμπτωτικοί συμβολισμοί Ο, Ω, Θ, παραδείγματα. Διαίρει και βασίλευε: πολλαπλασιασμός ακεραίων και πινάκων, ταξινόμηση (mergesort, quicksort), επιλογή (διάμεσος και στατιστικές τάξης), επίλυση αναδρομικών εξισώσεων, Kύριο (Master) Θεώρημα. Βασικοί αλγόριθμοι γράφων: διάσχιση, συνεκτικές συνιστώσες, ακυκλικά γραφήματα με κατεύθυνση, ανίχνευση κύκλων, τοπολογική ταξινόμηση, ισχυρά συνεκτικές συνιστώσες. Άπληστοι αλγόριθμοι: συντομότερα μονοπάτια (αλγόριθμος Dijkstra), ελάχιστα επικαλυπτικά δέντρα (αλγόριθμοι Prim και Kruskal), προτάσεις Horn, κώδικας Huffman, κλασματικό σακίδιο. Δυναμικός προγραμματισμός: συντομότερα μονοπάτια (αλγόριθμοι Bellman-Ford και Floyd-Warsall), πολλαπλασιασμός πινάκων, βέλτιστο δυαδικό δέντρο αναζήτησης, μέγιστη αύξουσα υπακολουθία, διορθωτική απόσταση, ακέραιο σακίδιο, πρόβλημα περιοδεύοντα πωλητή. Εισαγωγή στην ΝP πληρότητα: κλάσεις P, NP και ΝP-complete, πολυωνυμικές αναγωγές, βασικά παραδείγματα.

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

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

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

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

    Για να εγγραφεί στο μάθημα, ο φοιτητής πρέπει να έχει εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο είτε στο μάθημα «Εισαγωγή στον Προγραμματισμό Υπολογιστών» είτε στο μάθημα «Προγραμματισμός Υπολογιστών με JAVA» είτε στο μάθημα «Διακριτά Μαθηματικά». Συνιστάται στους φοιτητές να έχουν εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο και στα τρία αυτά μαθήματα.

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

    • Εισαγωγή στους Αλγορίθμους, Τόμος 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 ωρών εβδομαδιαίως), γραπτή ενδιάμεση εξέταση και ατομικές ασκήσεις στο σπίτι (2 ομάδες ασκήσεων κατά τη διάρκεια του εξαμήνου).

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

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