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