Αλγόριθμοι και Πολυπλοκότητα
| Κωδικός | 3.4.3105.7 |
|---|---|
| Εξάμηνο | 7o |
| Ροή | Λ - Λογισμικό Η/Υ |
| Κατηγορία | Υποχρεωτικό στην κύρια και τη μισή ροή |
| Ώρες Διδασκαλίας - Ώρες Εργαστηρίου | 4 - 1 |
| Διδάσκοντες | Αριστείδης Παγουρτζής, Δημήτριος Φωτάκης, Θεοδώρα Σούλιου (Ε.ΔΙ.Π.), Διδάσκων ΠΔ 407/80 ή ΑΥ |
| Σύνδεσμοι | Helios, Ιστοσελίδα Μαθήματος |
| Λεπτομέρειες Διδασκαλίας |
Δίνονται 4 σειρές γραπτών ασκήσεων και 4 σειρές προγραμματιστικών ασκήσεων, που αξιολογούνται αυτόματα (grader) και εξετάζονται δειγματοληπτικά στο εργαστήριο. |
Περιγραφή
Τεχνικές σχεδιασμού και ανάλυσης αλγορίθμων, και εισαγωγή στη θεωρία
υπολογιστικής πολυπλοκότητας. Τεχνικές για ασυμπτωτική εκτίμηση
υπολογιστικής πολυπλοκότητας, κριτήρια επιλογής αλγορίθμων, πολυωνυμικοί
αλγόριθμοι. Διαίρει-και-Βασίλευε αλγόριθμοι, εκτίμηση υπολογιστικής
πολυπλοκότητας αναδρομικών αλγορίθμων με το θεώρημα κυρίαρχου όρου,
ταξινόμηση με συγχώνευση, ταξινόμηση με διαίρεση, επιλογή, πλησιέστερο
ζεύγος σημείων, κυρτό κάλυμμα. Ταξινόμηση γραμμικού χρόνου. Δυαδική
αναζήτηση, αναζήτηση με παρεμβολή, ενημέρωση λίστας, ανάλυση με κατανομή
κόστους. Άπληστοι αλγόριθμοι, αποδείξεις ορθότητας με επιχείρημα
ανταλλαγής. Δυναμικός προγραμματισμός, πρόβλημα σακιδίου, μακρύτερη κοινή
υπακολουθία, μακρύτερη αύξουσα υπακολουθία, γραμμικός διαχωρισμός,
πολλαπλασιασμός ακολουθίας πινάκων, πρόβλημα πλανόδιου πωλητή. Αλγόριθμοι
γραφημάτων, υπολογισμός ισχυρά συνεκτικών συνιστωσών. Ελάχιστο συνδετικό
δέντρο, ορθότητα άπληστου υπολογισμού, αλγόριθμοι Kruskal, Prim, Boruvka,
εφαρμογές και επεκτάσεις. Συντομότερα μονοπάτια, υπολογισμός συντομότερων
μονοπατιών με ενημέρωση ετικετών, αλγόριθμοι Bellman-Ford, Dijkstra,
Floyd-Warshall, Johnson. Μέγιστη ροή και ελάχιστη τομή, αλγόριθμοι
Ford-Fulkerson και Edmonds-Karp, εφαρμογές. Υπολογισιμότητα και υπολογιστική
πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις
P και NP, NP-complete προβλήματα. Κλάσεις χωρικής πολυπλοκότητας. Αλγόριθμοι
προσέγγισης, κάλυμμα κορυφών, κάλυμμα συνόλων, πρόβλημα πλανόδιου
πωλητή. Πιθανοτικοί αλγόριθμοι, αλγόριθμος για ελάχιστη τομή.\\
Εργαστήριο: Μια σειρά αλγοριθμικών προβλημάτων που πρέπει να λυθούν σε C++.