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

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

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

Εαρινό 2009

Ασκήσεις – Προβλήματα – επιπρόσθετο υλικό

(30-Μαρ.-09) Εργασίες στο δυναμικό προγραμματισμό και στους άπληστους αλγορίθμους : Ομαδοποίηση (clustering) , αποθήκευση αρχείων σε δίσκους , Υπολογισμός Δυωνυμικών Συντελεστών , Κωδικοποίηση Huffman (Huffman encoding) , Knapsack , Αλυσιδωτός Πολλαπλασιασμός Πινάκων , Τμηματοποιημένα Ελάχιστα Τετράγωνα . Στο μάθημα μπορείτε να δηλώσετε ποιά εργασία θέλετε.

(01-Μαρ.-09) Εργασίες στους τυχαιοκρατικούς αλγόριθμους : τυχαιοκρατικός αλγόριθμος για το πρόβλημα εγγύτερου ζεύγους , τυχαιοκρατική ελάχιστη τομή μη κατευθυνόμενου γράφου . Στο μάθημα μπορείτε να δηλώσετε ποιά εργασία θέλετε.

(24-Φεβ.-09) An introduction to randomized algorithms , R. Karp

(19-Φεβ.-09) Δέντρα αναδρομής : δέντρο , δέντρο , δέντρο , δέντρο ! , πρόγραμμα που ζωγραφίζει δέντρα !!

(09-Φεβ.-09) Εργασίες στη μέθοδο Divide and Conquer: Πολλαπλασιασμός ακεραίων, Η ακολουθία Fibonacci, το πρόβλημα του κυρτού Εσωτερικού, το πρόβλημα του εγγύτερου ζεύγους. Στο μάθημα μπορείτε να δηλώσετε ποιά εργασία θέλετε.

(02-Φεβ.-09) Τα στοιχεία του Ευκλείδη (στα Αγγλικά). Ο αλγόριθμος για τον Μ.Κ.Δ. βρίσκεται στο βιβλίο VII πρόταση 2. Επίσης: The story of One , ευχάριστο Ντοκιμαντέρ του BBC (διάρκειας μίας ώρας περίπου) για μία εκλαϊκευμένη πορεία του αριθμού 1 μέσα στο χρόνο (ρυθμίστε το παράθυρο για να μη σας ενοχλούν οι διαφημίσεις).

Σε αυτή τη σελίδα ανακοινώνονται εργασίες και ασκήσεις αλλά και πληροφορίες για τυχόν επιπρόσθετο υλικό που αναφέρουμε στο μάθημα.