Παρουσίαση/Προβολή

 

Προβλήματα συνδυαστικής βελτιστοποίησης. Αλγόριθμοι διαίρει-και-βασίλευε, FFT. Δυναμικός προγραμματισμός. Μέθοδος απληστίας. Αλγόριθμοι γραφημάτων: αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος, εφαρμογές. Ελάχιστα επικαλύπτοντα δέντρα, αλγόριθμοι Prim και Kruskal. Συντομότερα μονοπάτια, αλγόριθμοι Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Μέγιστη ροή, θεώρημα μέγιστης ροής – ελάχιστης τομής, αλγόριθμοι επαυξητικών μονοπατιών. Ροή ελάχιστου κόστους, αλγόριθμοι απάλειψης κύκλων αρνητικού μήκους. Υπολογιστική πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ-πληρότητα, αλγοριθμικές συνέπειες. Αλγόριθμοι προσέγγισης. Πιθανοτικοί αλγόριθμοι.