Αλγόριθμοι και Πολυπλοκότητα

Στον Άβακα θα βρεις εκφωνήσεις παλιών διαγωνισμάτων στους Αλγόριθμους και Πολυπλοκότητα της ΣΗΜΜΥ του ΕΜΠ

Σύντομη περιγραφή του μαθήματος

Αλγόριθμοι και Πολυπλοκότητα | ΣΗΜΜΥ ΕΜΠ

Τεχνικές σχεδιασμού και ανάλυσης αλγορίθμων, και εισαγωγή στη θεωρία υπολογιστικής πολυπλοκότητας. Τεχνικές για ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας, κριτήρια επιλογής αλγορίθμων, πολυωνυμικοί αλγόριθμοι. Διαίρει-και-Βασίλευε αλγόριθμοι, εκτίμηση υπολογιστικής πολυπλοκότητας αναδρομικών αλγορίθμων με το θεώρημα κυρίαρχου όρου, ταξινόμηση με συγχώνευση, ταξινόμηση με διαίρεση, επιλογή, πλησιέστερο
ζεύγος σημείων, κυρτό κάλυμμα. Ταξινόμηση γραμμικού χρόνου. Δυαδική αναζήτηση, αναζήτηση με παρεμβολή, ενημέρωση λίστας, ανάλυση με κατανομή κόστους. Άπληστοι αλγόριθμοι, αποδείξεις ορθότητας με επιχείρημα ανταλλαγής. Δυναμικός προγραμματισμός, πρόβλημα σακιδίου, μακρύτερη κοινή υπακολουθία, μακρύτερη αύξουσα υπακολουθία, γραμμικός διαχωρισμός, πολλαπλασιασμός ακολουθίας πινάκων, πρόβλημα πλανόδιου πωλητή. Αλγόριθμοι γραφημάτων, υπολογισμός ισχυρά συνεκτικών συνιστωσών. Ελάχιστο συνδετικό δέντρο, ορθότητα άπληστου υπολογισμού, αλγόριθμοι Kruskal, Prim, Boruvka, εφαρμογές και επεκτάσεις. Συντομότερα μονοπάτια, υπολογισμός συντομότερων μονοπατιών με ενημέρωση ετικετών, αλγόριθμοι Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Μέγιστη ροή και ελάχιστη τομή, αλγόριθμοι Ford-Fulkerson και Edmonds-Karp, εφαρμογές. Υπολογισιμότητα και υπολογιστική πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις P και NP, NP-complete προβλήματα. Κλάσεις χωρικής πολυπλοκότητας. Αλγόριθμοι προσέγγισης, κάλυμμα κορυφών, κάλυμμα συνόλων, πρόβλημα πλανόδιου πωλητή. Πιθανοτικοί αλγόριθμοι, αλγόριθμος για ελάχιστη τομή. \\ Εργαστήριο: Μια σειρά αλγοριθμικών προβλημάτων που πρέπει να λυθούν σε C++.

Στον Άβακα θα βρεις εξειδικευμένους καθηγητές που κάνουν φροντιστήριο και ιδιαίτερα μαθήματα στους Αλγόριθμους και Πολυπλοκότητα της ΣΗΜΜΥ του Εθνικού Μετσόβιου Πολυτεχνείου.