ΜΑΕ641 - Σχεδίαση και Ανάλυση Αλγορίθμων
Περιγραφή
Βασικά στοιχεία σχεδίασης και ανάλυσης αλγορίθμων, Αποδοτικότητα, Ασυμπτωτικός ρυθμός αύξησης, Συνηθισμένοι χρόνοι εκτέλεσης και δομές δεδομένων, Ευσταθές ταίριασμα, ορθότητα αλγορίθμου, Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων και επίλυση αναδρομικών σχέσεων.
Αλγόριθμοι γραφημάτων: διάσχιση κατά πλάτος (BFS), διάσχιση κατά βάθος (DFS), Συνεκτικότητα γραφημάτων και τοπολογική ταξινόμηση, Άπληστοι αλγόριθμοι, χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra), Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman.
Μέθοδος "δυναμικού προγραμματισμού": χρονοπρογραμματισμός και σακίδια.
Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα.