ΕΠΛ 232: Αλγόριθμοι και Πολυπλοκότητα
Class Notes

 
Διάλεξη 1
 Εισαγωγή - Πολυπλοκότητα Αλγορίθμων
 -  Πρόβλημα, Στιγμιότυπο, Αλγόριθμος, Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n),
Ανάλυση Πολυπλοκότητας Αλγορίθμων 
download (pdf)
Διάλεξη 2 Αλγόριθμοι Διαίρει και Βασίλευε 
 - Η Μέθοδος Σχεδιασμού Αλγορίθμων Διαίρει και Βασίλευε, Επίλυση Αναδρομικών Εξισώσεων 
download (pdf)
Διαλέξη 3
Δυναμικός Προγραμματισμός
 - Σχεδιασμός αλγορίθμων με Δυναμικό Προγραμματισμό, Εύρεση μέγιστης κοινής υποακολουθίας
download (pdf)
Διαλέξη 4
Άπληστοι Αλγόριθμοι 
 - Σχεδιασμός αλγορίθμων με Άπληστους Αλγόριθμους, Στοιχεία άπληστων αλγορίθμων, Το πρόβλημα επιλογής εργασιών
download (pdf)
Διαλέξη 5
Αλγόριθμοι Οπισθοδρόμησης
 - Η οπισθοδρόμηση στο σχεδιασμό αλγορίθμων, Το πρόβλημα των σταθερών γάμων και ο αλγόριθμος των Gale-Shapley, Το πρόβλημα των οκτώ βασιλισσών
download (pdf)
Διαλέξεις 6 και 7
Βραχύτερα Μονοπάτια σε Γράφους
  - Ο αλγόριθμος των Bellman-Ford και ο αλγόριθμος του Dijkstra
download (pdf)
 Διαλέξεις 8 και 9
Βραχύτερα Μονοπάτια σε Γράφους
 - Βραχύτερα μονοπάτια για όλα τα ζεύγη, Λύση Δυναμικού Προγραμματισμού, Ο αλγόριθμος των Floyd-Warshal
download (pdf)
 Διαλέξεις 10 και 11
Αλγόριθμοι Ροής σε Γράφους 
 - Δίκτυα ροής και το πρόβλημα της μέγιστης ροής, Η μεθοδολογία Ford-Fulkerson, Ο αλγόριθμος Edmonds-Karps
download (pdf)
 Διαλέξεις 12 και 13
Ταχύς Μετασχηματισμός Fourier
 - Παραστάσεις πολυωνύμων, Πολυωνυμική Παρεμβολή, Διακριτός Μετασχηματισμός Fourier, Ταχύς Μετασχηματισμός Fourier
 download (pdf)
Διαλέξεις 14 και 16
Γεωμετρικοί Αλγόριθμοι 
 - Γινόμενα σημεία, τομή ευθυγράμμων τμημάτων
   Εύρεση κυρτών περιβλημάτων: Ο αλγόριθμος του Graham και ο αλγόριθμος του Jarvis 
   Το πρόβλημα "Closest Pair"
download (pdf)
Διαλέξεις 17 και 19
Tυχαιοποιημένοι Αλγόριθμοι 
 - Ο τυχαιοποιμένος αλγόριθμος QuickSort
   Αλγόριθμοι Επιλογής: Τυχαιποιημένος Αλγόριθμος και ο αλγόριθμος των Βlum, Floyd, Pratt, Rivest, Tarjan
   Ο αλγόριθμος του Freivalds, Πρωτόκολα Μηδενικής Γνώσης
download (pdf)
Διαλέξεις 20 και 21
Δίκτυα Ταξινόμησης
- Δίκτυα σύγκρισης, δίκτυα ταξινόμησης, Αρχή 0-1, Διτονική ταξινόμηση
download (pdf)
Διάλεξη 22
Παράλληλοι Αλγόριθμοι
- Το μοντέλο PRAΜ, Πολλαπλασιασμός πινάκων, Υπολογισμός αθροισμάτων προθέματος
download (pdf)
Διαλέξεις 23-25
Αριθμοθεωρητικοί  Αλγόριθμοι και το Κρυπτοσύστημα RSA
- Υπολογισμός Μέγιστου Κοινού Διαιρέτη, Αλγόριθμος του Ευκλείδη, Κλάσεις Ισοδυναμίας και Αριθμητική modulo n, Γραμμικές Εξισώσεις modulo n, To Κινέζικο θεώρημα υπολοίπων, To Κρυπτοσύστημα RSA
download (pdf)

 
 
 
Main Course Page
Class Contract
Tutorials
Course Schedule
 What's New?
Assignments
Assignment Solutions
Related Link

Άννα Φιλίππου, Ιανουάριος 2004