Ανακοινώσεις

Σε αντίστροφη χρονολογική σειρά.

 

Iουνίος

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

 

Μάρτιος

Πα 12 Μαρ 2010
Στην ιστοσελίδα των ασκήσεων του μαθήματος μπορείτε να βρείτε την 1η Άσκηση του μαθήματος.

 

Φεβρουάριος

Δε 22 Φεβ 2010
Οι διαλέξεις του μαθήματος της 12ης, 15ης, 17ης και 19ης Φεβρουαρίου δεν έγιναν λόγω απουσίας του διδάσκοντος. Οι αναπληρώσεις των διαλέξεων αυτών θα γίνουν Παρασκευές από 11πμ ως 1μμ. Οι συγκεκριμένες μέρες θα ανακοινωθούν.