|
Class Notes |
|
|
Εισαγωγή
- Πολυπλοκότητα Αλγορίθμων - Πρόβλημα, Στιγμιότυπο, Αλγόριθμος, Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n), Ανάλυση Πολυπλοκότητας Αλγορίθμων |
|
| Διάλεξη 2 | Αλγόριθμοι
Διαίρει και Βασίλευε - Η Μέθοδος Σχεδιασμού Αλγορίθμων Διαίρει και Βασίλευε, Επίλυση Αναδρομικών Εξισώσεων |
|
|
|
Δυναμικός
Προγραμματισμός - Σχεδιασμός αλγορίθμων με Δυναμικό Προγραμματισμό, Εύρεση μέγιστης κοινής υποακολουθίας |
|
|
|
Άπληστοι
Αλγόριθμοι - Σχεδιασμός αλγορίθμων με Άπληστους Αλγόριθμους, Στοιχεία άπληστων αλγορίθμων, Το πρόβλημα επιλογής εργασιών |
|
|
|
Αλγόριθμοι
Οπισθοδρόμησης - Η οπισθοδρόμηση στο σχεδιασμό αλγορίθμων, Το πρόβλημα των σταθερών γάμων και ο αλγόριθμος των Gale-Shapley, Το πρόβλημα των οκτώ βασιλισσών |
|
|
|
Βραχύτερα
Μονοπάτια σε Γράφους - Ο αλγόριθμος των Bellman-Ford και ο αλγόριθμος του Dijkstra |
|
|
|
Βραχύτερα
Μονοπάτια σε Γράφους - Βραχύτερα μονοπάτια για όλα τα ζεύγη, Λύση Δυναμικού Προγραμματισμού, Ο αλγόριθμος των Floyd-Warshal |
|
|
|
Αλγόριθμοι
Ροής σε Γράφους - Δίκτυα ροής και το πρόβλημα της μέγιστης ροής, Η μεθοδολογία Ford-Fulkerson, Ο αλγόριθμος Edmonds-Karps |
|
|
|
Ταχύς
Μετασχηματισμός Fourier - Παραστάσεις πολυωνύμων, Πολυωνυμική Παρεμβολή, Διακριτός Μετασχηματισμός Fourier, Ταχύς Μετασχηματισμός Fourier |
|
|
|
Γεωμετρικοί
Αλγόριθμοι - Γινόμενα σημεία, τομή ευθυγράμμων τμημάτων Εύρεση κυρτών περιβλημάτων: Ο αλγόριθμος του Graham και ο αλγόριθμος του Jarvis Το πρόβλημα "Closest Pair" |
|
|
|
Tυχαιοποιημένοι
Αλγόριθμοι - Ο τυχαιοποιμένος αλγόριθμος QuickSort Αλγόριθμοι Επιλογής: Τυχαιποιημένος Αλγόριθμος και ο αλγόριθμος των Βlum, Floyd, Pratt, Rivest, Tarjan Ο αλγόριθμος του Freivalds, Πρωτόκολα Μηδενικής Γνώσης |
|
|
|
Δίκτυα
Ταξινόμησης - Δίκτυα σύγκρισης, δίκτυα ταξινόμησης, Αρχή 0-1, Διτονική ταξινόμηση |
download (pdf) |
|
|
Παράλληλοι
Αλγόριθμοι - Το μοντέλο PRAΜ, Πολλαπλασιασμός πινάκων, Υπολογισμός αθροισμάτων προθέματος |
download (pdf) |
|
|
Αριθμοθεωρητικοί
Αλγόριθμοι και το Κρυπτοσύστημα RSA - Υπολογισμός Μέγιστου Κοινού Διαιρέτη, Αλγόριθμος του Ευκλείδη, Κλάσεις Ισοδυναμίας και Αριθμητική modulo n, Γραμμικές Εξισώσεις modulo n, To Κινέζικο θεώρημα υπολοίπων, To Κρυπτοσύστημα RSA |
|
|
|
|
|
|
|
|
|
|
|
Άννα Φιλίππου, Ιανουάριος 2004