Αλγόριθμοι: Σχεδίαση και Ανάλυση

Μάθημα Επιλογής Κορμού, Εαρινό Εξάμηνο, 6 μονάδες ECTS

Διδάσκουσα:  Δρ.Κάτια Παπακωνσταντινοπούλου

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

Περιεχόμενο

Αύξηση συναρτήσεων και ασυμπτωτικοί συμβολισμοί Ο, Ω, Θ. Σχεδίαση αλγορίθμων «διαίρει και βασίλευε», άπληστων και δυναμικού προγραμματισμού. Αλγόριθμοι γράφων. Γραμμικός προγραμματισμός, ακέραιος γραμμικός προγραμματισμός και εφαρμογές. Μέγιστες ροές και ταιριάσματα. ΝP πληρότητα. Προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS και FPTAS). Πιθανοτικοί αλγόριθμοι. Άμεσοι αλγόριθμοι. Αλγόριθμοι για δεδομένα μεγάλης κλίμακας.

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

Μετά την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής θα είναι σε θέση να σχεδιάζει και να αναλύει αλγόριθμους για ένα ευρύ φάσμα προβλημάτων με θεωρητικό και πρακτικό ενδιαφέρον. Πιο συγκεκριμένα:

• Θα έχει εμπεδώσει σε βάθος τις τεχνικές σχεδιασμού αλγορίθμων και τις δυνατότητές τους.
• Θα μπορεί να χρησιμοποιεί τις κατάλληλες δομές δεδομένων στο σχεδιασμό αλγορίθμων.
• Θα γνωρίζει τις κατάλληλες μαθηματικές μεθόδους και θα μπορεί να τις χρησιμοποιεί στην ανάλυση αλγορίθμων (ορθότητα και πολυπλοκότητα).
• Θα έχει κατανοήσει την έννοια των “δύσκολων” (NP-complete) προβλημάτων και θα μπορεί να εφαρμόζει μεθόδους αντιμετώπισής τους.

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

Οι φοιτητές πρέπει να έχουν μαθηματική ωριμότητα η οποία προκύπτει από την ολοκλήρωση ορισμένων προπτυχιακών μαθημάτων μαθηματικών. Ιδιαιτέρως, πρέπει να έχουν γνώσεις διακριτών μαθηματικών και θεωρίας πιθανοτήτων. Είναι χρήσιμο να έχουν ολοκληρώσει εισαγωγικό μάθημα αλγορίθμων.

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

• Sanjoy Dasgupta, Christos H. Papadimitriou, και Umesh Vazirani, Κλειδάριθμος, 1η έκδοση, 2009, ISBN-13: 978-9604612116. 
• Εισαγωγή στους Αλγόριθμους, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Πανεπιστημιακές εκδόσεις Κρήτης, 3η έκδοση, 2016, ISBN-13: 978-9605244736. 
• Σχεδιασμός Αλγορίθμων, Jon Kleinberg και Eva Tardos, Κλειδάριθμος, 2η έκδοση, 2008, ISBN-13: 978-9604612079. 
• Computational Complexity, Christos H. Papadimitriou, Pearson, 1st edition, 1993, ISBN-13: 978-0201530827.
• Computers and Intractability: A Guide to the Theory of NP-Completeness, Michael R. Garey, David S. Johnson, W. H. Freeman, 1st edition, 1979, ISBN-13: 978-0716710455.
• Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag Berlin Heidelberg, 1st edition, 2003, ISBN-13: 978-3540653677.

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

Μια διάλεξη 3 ωρών εβδομαδιαίως, ασκήσεις κατ’ οίκον.

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

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