Παρουσίαση/Προβολή
Προηγμένα Θέματα Αλγορίθμων
(ΘΠ12) - Νάκος Βασίλειος
Περιγραφή Μαθήματος
Το μάθημα αυτό αποσκοπεί στην εμβάθυνση σε θέματα σχεδίασης και ανάλυσης αλγορίθμων. Μελετώνται προβλήματα και αλγόριθμοι με σκοπό την εμπέδωση των βασικών αλλά και πιο προχωρημένων τεχνικών. Προϋποθέτει γνώση σε ικανοποιητικό επίπεδο των βασικών μεθόδων σχεδίασης και ανάλυσης αλγορίθμων.
Ημερομηνία δημιουργίας
Τρίτη 19 Ιανουαρίου 2021
-
Οργάνωση μαθήματος
Το μάθημα είναι βασικό για την 1η κατεύθυνση. Η διδασκαλία του μαθήματος διαρκεί 13 εβδομάδες, με 4 ώρες διαλέξεων ανά εβδομάδα. Οι διαλέξεις περιλαμβάνουν βασικές και προηγμένες τεχνικές σχεδίασης και ανάλυσης αλγορίθμων, καθώς και συμπληρωματικά θέματα υπολογιστικής πολυπλοκότητας και κυρίως NP-πληρότητας. H διδασκαλία κάθε ενότητας ολοκληρώνεται με την επίλυση ασκήσεων.
Περιεχόμενο μαθήματος
Το μάθημα αφορά τους προπτυχιακούς φοιτητές για το χειμερινό εξάμηνο 2021-2022 και αποσκοπεί στην εμβάθυνση σε θέματα σχεδίασης και ανάλυσης αλγορίθμων.
Διαλέξεις 1-2: Δομές Δεδομένων RMQ και LCA
Διαλέξεις 3-4: Αντισταθμιστική ανάλυση, διωνυμικός σωρός και σωρός Fibonacci.
Διαλέξεις 5-6: Ισχυρές συνεκτικές συνιστώσες, 2-SAT και παραδείγματα
Διαλέξεις 7-8: Γρήγορος Μετασχηματισμός Fourier και Συνελίξεις
Διαλέξεις 9-10: Μέγιστη τομή, ελάχιστη ροή και παραδείγματα
Διαλέξεις 11-14: Πιθανοτικοί Αλγόριθμοι (Las Vegas/ Monte Carlo, Quicksort, 3-SAT, χρωματική κωδικοποίηση)
Διαλέξεις 15-16: Γραμμικός προγραμματισμός, θεωρία και εφαρμογές
Διαλέξεις 17-18: Προσεγγιστικοί αλγόριθμοι
Διαλέξεις 19-20: Αλγόριθμοι Γραμμικής Άλγεβρας και Μηχανικής Μάθησης
Διαλέξεις 21-22: Αλγόριθμοι Αριθμητικής ΒελτιστοποίησηςΒιβλιογραφία
- Σχεδιασμός Αλγορίθμων, Jon Kleinberg , Eva Tardos, Εκδόσεις Κλειδάριθμος
- Aλγόριθμοι, S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Εκδόσεις Κλειδάριθμος
- Εισαγωγή στους αλγορίθμους, Cormen, Leiserson, Rivest, Stein, Τόμος Ι. Πανεπ. Εκδόσεις Κρήτης