Πανεπιστήμιο Κρήτης

Τμήμα Εφαρμοσμένων Μαθηματικών

Σχεδίαση και Ανάλυση Αλγορίθμων - ΕΜ 202

Εαρινό 2009

Ημερολόγιο - Ύλη

(12 Μαΐ. 2009) Ασκήσεις.

(11 Mαΐ. 2009) Ασκήσεις.

(06 Μαΐ. 2009) Ασκήσεις κεφ. 16.

(05 Μαΐ. 2009) Ασκήσεις κεφ. 9.

(04 Μαΐ. 2009) Προσεγγιστικοί Αλγόριθμοι. 2 – προσεγγιστικός για το πρόβλημα περιοδεύοντος πωλητή, ln(m) – προσεγγιστικός για το πρόβλημα Set Cover.

(29 Απρ. 2009) Παρουσιάσεις εργασιών ΙΙ.

(28 Απρ. 2009) Δεν έγινε μάθημα.

(27 Απρ. 2009) Αντισταθμιστική Ανάλυση (Αθροιστική , Χρεωπιστωτική και Ενεργειακή μέθοδος).

(08 Απρ. 2009) Άπληστοι Αλγόριθμοι (πρόβλημα επιλογής δραστηριοτήτων), χαρακτηριστικά άπληστων αλγόριθμων.

(07 Απρ. 2009) …εύρεση μέγιστης κοινής υπακολουθίας, χαρακτηριστικά δυναμικού προγραμματισμού.

(06 Απρ. 2009) Παρουσιάσεις εργασιών Ι.

(01 Απρ. 2009) Πρόοδος 2.

(31 Μαρ. 2009) Δυναμικός προγραμματισμός (χρονοπρογραμματισμός γραμμής παραγωγής, εύρεση μέγιστης κοινής υπακολουθίας...).

(30 Μαρ. 2009) Εύρεση i-διατακτικής στατιστικής σε γραμμικό χρόνο χειρότερης περίπτωσης.

(25 Μαρ. 2009) Αργία (Εθνική Επέτειος 1821, Ευαγγελισμός Θεοτόκου).

(24 Μαρ. 2009) συνέχεια...εύρεσης i-οστής στατιστικής σε αναμενόμενο γραμμικό χρόνο, Ασκήσεις κεφ. 7, 8.

(23 Μαρ. 2009) Δεν έγινε μάθημα (μή προσέλευση).

(18 Μαρ. 2009) Διάμεσοι και διατακτικές στατιστικές (ταυτόχρονη εύρεση 1ης και n-οστής στατιστικής, εύρεση i-οστής στατιστικής σε αναμενόμενο γραμμικό χρόνο).

(17 Μαρ. 2009) Ταξινόμηση σε γραμμικό χρόνο (...αριθμοτακτική ταξινόμηση, ταξινόμηση με δοχεία).

(16 Μαρ. 2009) Κάτω φράγματα αλγορίθμων συγκριτικής ταξινόμησης (δένδρα απόφασης). Ταξινόμηση σε γραμμικό χρόνο (απαριθμητική ταξινόμηση, αριθμοτακτική ταξινόμηση...).

(11 Μαρ. 2009) Μέσος χρόνος εκτέλεσης τυχαιοκρατικής ταχυταξινόμησης , ασκήσεις κεφ. 6.

(10 Μαρ. 2009) Ταχυταξινόμηση, τυχαιοκρατική ταχυταξινόμηση.

(09 Μαρ. 2009) Κατασκευή σωρού. Ταξινόμηση σωρού. Εφαρμογή σωρών στις ουρές προτεραιότητας.

(04 Μαρ. 2009) Ασκήσεις κεφ. 5, Εισαγωγή στις σωρούς (ιδιότητες σωρού , αποκατάσταση σωρού).

(03 Μαρ. 2009) Τυχαιοκρατικός Αλγόριθμος για το πρόβλημα της πρόσληψης. Λύση θεμάτων προόδου 1.

(02 Μαρ. 2009) Αργία (Καθαρή Δευτέρα).

(25 Φεβ. 2009) Πρόοδος 1.

(24 Φεβ. 2009) Εισαγωγή στην Πιθανοτική Ανάλυση Αλγορίθμων (το πρόβλημα της πρόσληψης).

(23 Φεβ. 2009) Ασκήσεις.

(18 Φεβ. 2009) Ασκήσεις, Κεντρική μέθοδος επίλυσης αναδρομικών σχέσεων.

(17 Φεβ. 2009) Αναδρομικές σχέσεις (κεφ. 4).

(16 Φεβ. 2009) Ασκήσεις.

(11 Φεβ. 2009) Πολυωνυμικοί αλγόριθμοι. Ασυμπτωτική συμπεριφορά συναρτήσεων. Συμβολισμοί Ο, Ω, Θ .

(10 Φεβ. 2009) Ανάλυση συγχωνευτικής ταξινόμησης (αναδρομικές σχέσεις με τη μέθοδο διαίρει και κυρίευε, δένδρο αναδρομής).

(09 Φεβ. 2009) Συγχωνευτική ταξινόμηση (σχεδιασμός αλγορίθμου, παραδείγματα, διαδικασία συγχώνευσης ταξινομημένων πινάκων).

(04 Φεβ. 2009) Ανάλυση ενθετικής ταξινόμησης (καλύτερη, χειρότερη και μέση περίπτωση).

(03 Φεβ. 2009) Οι αλγόριθμοι ώς τεχνολογία (Δραστικότητα Αλγορίθμων). Ενθετική ταξινόμηση. Ορθότητα ενθετικής ταξινόμησης. Μέθοδος αναλλοίωτων συνθηκών.

(02 Φεβ. 2009) Σύντομη περιγραφή του μαθήματος. Τί είναι Αλγόριθμος; Ο Αλγόριθμος του Ευκλείδη για τον υπολογισμό του Μ.Κ.Δ. δύο θετικών ακεραίων.