|
Δε 7 Ιουν 2010
Η εξεταστέα ύλη του μαθήματος έχει ως εξής:
- Εισαγωγή
-
Προκαταρτικές έννοιες (Ενθετική ταξινόμηση,
Ανάλυση αλγορίθμων, Σχεδίαση αλγορίθμων)
-
Ρυθμός αύξησης συναρτήσεων (Ασυμπτωτικός
συμβολισμός, Καθιερωμένοι συμβολισμοί και
συνήθεις συναρτήσεις)
-
Αναδρομικές σχέσεις (Μέθοδος αντικατάστασης,
Μέθοδος δέντρου αναδρομής, Κεντρική μέθοδος)
-
Ταξινόμηση και διατακτικές στατιστικές
-
Ταξινόμηση σωρού (Σωροί, Διατήρηση
ιδιότητας σωρού, Κατασκευή σωρού, Αλγόριθμος
ταξινόμησης σωρού)
-
Ταχυταξινόμηση (Περιγραφή ταχυταξινόμησης,
επίδοση ταχυταξινόμησης, Τυχαιοκρατική
εκδοχή ταχυταξινόμησης, Ανάλυση ταχυταξινόμησης)
-
Ταξινόμηση σε γραμμικό χρόνο (Κάτω φράγματα
για αλγορίθμους ταξινόμησης, Απαριθμητική
ταξινόμηση, Αριθμοτακτική ταξινόμηση)
-
Διάμεσοι και διατακτικές στατιστικές
(Ελάχιστο, Μέγιστο, Επιλογή σε γραμμικό
αναμενόμενο χρόνο, Επιλογή σε γραμμικό χρόνο
χειρότερης περίπτωσης)
- Aνώτερες τεχνικές σχεδίασης και ανάλυσης
-
Δυναμικός προγραμματισμός
(Χρονοπρογραμματισμός γραμμής παραγωγής,
Πολλαπλασιασμός αλληλουχίας πινάκων, Στοιχεία
δυναμικού προγραμματισμού)
-
Άπληστοι αλγόριθμοι (Πρόβλημα επιλογής
δραστηριοτήτων, Στοιχεία άπληστης στρατιγικής,
Κώδικες Huffman)
-
Αλγόριθμοι γραφημάτων
-
Στοιχειώσεις αλγόριθμοι γραφημάτων
(αναπαραστάσεις γραφημάτων, Οριζόντια
διερεύνηση, Καθοδική διερεύνηση, Τοπολογική
ταξινόμηση, Ισχυρά συνδεδεμένες συνιστώσες)
-
Ελαφρύτατα συνδετικά δέντρα (Επέκταση
ελαφρύτατου συνδετικού δέντρου, Αλγόριθμος
Kruskal, Αλγόριθμος Prim)
-
Ομοαφετηριακές ελαφρύτατες διαδρομές
(Αλγόριθμων Bellman-Ford, Ομοαφετηριακές
ελαφρύτατες διαδρομές σε κατευθυνόμενα
άκυκλα γραφήματα, Αλγόριθμος Dijkstra)
-
Πανζευκτικές ελαφρύτατες διαδρομές
(Ελαφρύτατες διαδρομές και πολλαπλασιασμός
πινάκων, Αλγόριθμος Floyd-Warshall,
Αλγόριθμος Johnson για αραιά γραφήματα)
-
Μέγιστη ροή (Δίκτυα ροής, Μέθοδος
Ford-Fulkerson)
|