Παρουσίαση/Προβολή

Προηγμένα Θέματα Αλγορίθμων

(ΘΠ12) - Νάκος Βασίλειος

Περιγραφή Μαθήματος

Το μάθημα αυτό αποσκοπεί στην εμβάθυνση σε θέματα σχεδίασης και ανάλυσης αλγορίθμων. Μελετώνται προβλήματα και αλγόριθμοι με σκοπό την εμπέδωση των βασικών αλλά και πιο προχωρημένων τεχνικών. Προϋποθέτει γνώση σε ικανοποιητικό επίπεδο των βασικών μεθόδων σχεδίασης και ανάλυσης αλγορίθμων.

Το μάθημα χωρίζεται σε ζεύγη διαλέξεων και αφορά:

Δομές Δεδομένων

Αντισταθμιστική Ανάλυση

Αλγόριθμοι για ισχυρά συνεκτικές συνιστώσες

Μέγιστη Ροή-Ελάχιστη Τομή

Γρήγορος Μετασχηματισμός Fourier και Συνελίξεις

Γραμμικός Προγραμματισμός

Πιθανοτικοί Αλγόριθμοι

Γραμμική Άλγεβρα για Μηχανική Μάθηση

Αριθμητική Βελτιστοποίηση

Ημερομηνία δημιουργίας

Τρίτη 19 Ιανουαρίου 2021

Σελίδα μαθήματος

Περίγραμμα
Οργάνωση μαθήματος

Το μάθημα είναι βασικό για την 1η κατεύθυνση. Η διδασκαλία του μαθήματος διαρκεί 13 εβδομάδες, με 4 ώρες διαλέξεων ανά εβδομάδα. Οι διαλέξεις περιλαμβάνουν προηγμένες τεχνικές σχεδίασης και ανάλυσης αλγορίθμων, οι οποίες καλύπτουν όλο το φάσμα των σύγχρονων αλγορίθμων.

Στο μάθημα υπάρχουν γραπτές και προγραμματιστικές ασκήσεις.

Περιεχόμενο μαθήματος

Το μάθημα αφορά τους προπτυχιακούς φοιτητές για το χειμερινό εξάμηνο 2021-2022 και αποσκοπεί στην εμβάθυνση σε θέματα σχεδίασης και ανάλυσης αλγορίθμων.

Διαλέξεις 1-2: Δομές Δεδομένων RMQ και LCA
Διαλέξεις 3-4: Αντισταθμιστική ανάλυση
Διαλέξεις 5-6: Ισχυρά συνεκτικές συνιστώσες, δισυνεκτικές συνιστώστες, 2-SAT
Διαλέξεις 7-8: Γρήγορος Μετασχηματισμός Fourier και Συνελίξεις
Διαλέξεις 9-10: Μέγιστη ροή, ελάχιστη τομή
Διαλέξεις 11-14: Πιθανοτικοί Αλγόριθμοι, σχεδίαση και ανάλυση
Διαλέξεις 15-16: Γραμμικός προγραμματισμός

Διαλέξεις 17-18: Αλγόριθμοι Γραμμικής Άλγεβρας στη Μηχανικής Μάθηση
Διαλέξεις 19-20: Αλγόριθμοι Αριθμητικής Βελτιστοποίησης για Τεχνητή Νοημοσύνη και Μηχανική Μάθηση

Διαλέξεις 20+ (επιπρόσθετες): Προβλήματα επίλυσης προβλημάτων από διαγωνισμούς Πληροφορικής
Βιβλιογραφία
- Σχεδιασμός Αλγορίθμων, Jon Kleinberg , Eva Tardos, Εκδόσεις Κλειδάριθμος
- Aλγόριθμοι, S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Εκδόσεις Κλειδάριθμος
- Εισαγωγή στους αλγορίθμους, Cormen, Leiserson, Rivest, Stein, Τόμος Ι. Πανεπ. Εκδόσεις Κρήτης