Παρουσίαση/Προβολή
Αλγόριθμοι και Πολυπλοκότητα
(Κ17) - Γιαννοπούλου Αρχοντία, Εμίρης Ιωάννης, Ζησιμόπουλος Βασίλειος
Περιγραφή Μαθήματος
Το μάθημα αφορά όλους/όλες τους προπτυχιακούς/ες φοιτητές/τριες για το εαρινό εξάμηνο 2023-24.
Διαλέξεις:
Τετάρτη 11:00 - 13:00
Παρασκευή 13:00 - 15:00
Φροντιστήρια: Ανάλογα με τον Α.Μ. σας σύμφωνα το πρόγραμμα του Τμήματος
Ημερομηνία δημιουργίας
Τρίτη 2 Δεκεμβρίου 2
-
Περιγραφή
Το μάθημα απευθύνεται σε προπτυχιακούς/ες φοιτητές/τριες με στόχο να καλύψει τις βασικές αρχές σχεδίασης και ανάλυσης αλγορίθμων.
Περιεχόμενο μαθήματος
Το μάθημα καλύπτει τα θέματα:
- βασικές αρχές και τεχνικές ανάλυσης χρόνου εκτέλεσης αλγορίθμων και ασυμπτωτικοί συμβολισμοί Ο, Ω και Θ
- κάποιες δομές δεδομένων (π.χ. σωροί και ουρές προτεραιότητας)
- αλγόριθμοι ταξινόμησης και αναζήτησης
- τρεις βασικές τεχνικές σχεδίασης αλγορίθμων: άπληστη προσέγγιση, διαίρει-και-βασίλευε, δυναμικός προγραμματισμός
- στοιχειώδεις αλγόριθμοι γραφημάων (αναζήτηση κατα πλάτος και βάθος και εφαρμογές τους , δέντρα επικάλυψης, συντομότερα μονοπάτια, ταίριασμα)
- NP-completeness, αναγωγές
Βιβλιογραφία
Το μάθημα θα βασιστεί κυρίως στο πρώτο από τα προτεινόμενα συγγράμματα:
- Cormen, Leiserson, Rivest, Stein. Εισαγωγή στους αλγορίθμους, Τόμος Ι. Πανεπ. Εκδόσεις Κρήτης, 2006.
- J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005. Μεταφρασμένο στα Ελληνικά με τίτλο Σχεδιασμός αλγορίθμων από τις εκδόσεις Κλειδάριθμος.
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, McGraw Hill, 2006.
Τα παρακάτω βιβλία καλύπτουν την ίδια ύλη και προτείνονται σαν εναλλακτικές καλές πηγές:- Β. Ζησιμόπουλος. Αλγόριθμοι και Πολυπλοκότητα - Σημειώσεις
- Π. Δ. Μποζάνης. Αλγόριθμοι: Σχεδιασμός και ανάλυση. Εκδόσεις Α. Τζιόλα, 2003