|
Class Notes |
|
|
Εισαγωγή
- Πολυπλοκότητα Αλγορίθμων
- Πρόβλημα, Στιγμιότυπο, Αλγόριθμος, Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n), Ανάλυση Πολυπλοκότητας Αλγορίθμων |
|
| Διάλεξη 2 | Αλγόριθμοι
Διαίρει και Βασίλευε
- Η Μέθοδος Σχεδιασμού Αλγορίθμων ‘Διαίρει και Βασίλευε’, Επίλυση Αναδρομικών Εξισώσεων |
|
|
|
Δυναμικός
Προγραμματισμός
- Σχεδιασμός αλγορίθμων με Δυναμικό Προγραμματισμό, Εύρεση μέγιστης κοινής υποακολουθίας |
|
|
|
Άπληστοι
Αλγόριθμοι
- Σχεδιασμός αλγορίθμων με Άπληστους Αλγόριθμους, Στοιχεία άπληστων αλγορίθμων, Το πρόβλημα επιλογής εργασιών |
|
|
|
Αλγόριθμοι
Οπισθοδρόμησης
- Η οπισθοδρόμηση στο σχεδιασμό αλγορίθμων, Το πρόβλημα των σταθερών γάμων και ο αλγόριθμος των Gale-Shapley, Το πρόβλημα των οκτώ βασιλισσών |
|
|
|
Βραχύτερα
Μονοπάτια σε Γράφους
- Εισαγωγή σε δεντρικές δομές δεδομένων, ορισμοί, πράξεις και αναπαράσταση στη μνήμη Δυαδικά Δένδρα και Δυαδικά Δένδρα Αναζήτησης |
|
|
|
Βραχύτερα
Μονοπάτια σε Γράφους
- Βραχύτερα μονοπάτια για όλα τα ζεύγη, Λύση Δυναμικού Προγραμματισμού, Ο αλγόριθμος των 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 |
|
|
|
|
|
|
|
|
|
|
|
Άννα Φιλίππου, Φεβρουάριος 2002