Section outline
-
- Διάλεξη 2/10/2023: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
- Διάλεξη 5/10/2023: Ασυμπτωτικός Συμβολισμός (γρήγορη επανάληψη). Αποδοτικοί αλγόριθμοι, fine-grained complexity (απλή αναφορά, δείτε ακόμη ένα survey και ένα σχετικό μάθημα για περισσότερες πληροφορίες), beyond worst case analysis (απλή αναφορά, δείτε ακόμη ένα πρόσφατο βιβλίο και ένα σχετικό μάθημα για περισσότερες πληροφορίες). Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem (δείτε και αυτές τις σημειώσεις για την επίλυση αναδρομικών σχέσεων και το master theorem).
- Διάλεξη 12/10/2023. Αλγόριθμοι Διαίρει-και-Βασίλευε: πλησιέστερο ζεύγος σημείων, μέτρηση αντιστροφών (γρήγορη αναφορά, δείτε την αντίστοιχη άσκηση στην 1η σειρά λυμένων ασκήσεων), σύντομη επανάληψη στο master theorem, κυρτό κάλυμμα.
- Διάλεξη 17/10/2023. Κυρτό κάλυμμα (δείτε και αυτές τις σημειώσεις για αποδοτικούς αλγόριθμους που υπολογίζουν το κυρτό κάλυμμα). Quicksort.
- Διάλεξη 19/10/2023. Quicksort. Επιλογή σε γραμμικό χρόνο. Ντετερμινιστική επιλογή σε γραμμικό χρόνο.
- Διάλεξη 23/10/2023. Ταξινόμηση σε γραμμικό χρόνο. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις για το πρόβλημα αναδιοργάνωσης μιας γραμμικής λίστας (List Update) και την ανάλυση του Move-to-Front. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή.
- Διάλεξη 26/10/2023. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι αλγόριθμοι.
- Διάλεξη 30/10/2023. Άπληστοι αλγόριθμοι: επιλογή διαστημάτων, χρωματισμός διαστημάτων, αθροίσματα με ελάχιστο πλήθος προσθετέων.
- Διάλεξη 2/11/2023. Άπληστοι αλγόριθμοι: ελαχιστοποίηση συνολικού χρόνου ολοκλήρωσης (χωρίς και με βάρη), σακίδιο. Δυναμικός προγραμματισμός.
- Διάλεξη 6/11/2023. Δυναμικός προγραμματισμός: σακίδιο, subset sum, coin change, πολλαπλασιασμός ακολουθίας πινάκων.
- Διάλεξη 9/11/2023. Δυναμικός προγραμματισμός: πολλαπλασιασμός ακολουθίας πινάκων, αναδρομή με απομνημόνευση, μέγιστο ανεξάρτητο σύνολο στη γραμμή και σε δέντρα, επιλογή διαστημάτων με βάρη, χωρισμός ακολουθίας σε διαστήματα.
- Διάλεξη 13/11/2023. Δυναμικός προγραμματισμός: μέγιστη κοινή υπακολουθία, edit distance, μέγιστη αύξουσα υπακολουθία.
- Διάλεξη 20/11/2023. Δυναμικός προγραμματισμός: travelling salesman problem. String Matching. Σημειώσεις του Jeff Erickson για string matching.
- Διάλεξη 23/11/2023: String Matching: υπολογισμός της Failure Function. Συντομότερα Μονοπάτια από μία αρχική κορυφή: αλγόριθμος Bellman-Ford.
- Διάλεξη 27/11/2023: Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra.
- Διάλεξη 30/11/2023: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Ασκήσεις.
- Διάλεξη 4/12/2023: Μέγιστη ροή και ελάχιστη τομή: υπολλειματικό δίκτυο, αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Διαφάνειες Kleinberg-Tardos και σημειώσεις του Jeff Erickson για υπολογισμό μέγιστης ροής και ελάχιστης τομής.
- Διάλεξη 7/12/2023: Μέγιστη ροή και ελάχιστη τομή: εφαρμογή στον υπολογισμό μέγιστου ταιριάσματος σε διμερή γραφή, μέγιστο ταίριασμα και ελάχιστο κάλυμμα κορυφών σε διμερή γραφήματα. Το πρόβλημα της ροής ελάχιστου κόστους. Σημειώσεις του Jeff Erickson για εφαρμογές των προβλημάτων μέγιστης ροής και ελάχιστης τομής.
- Διάλεξη 11/12/2023: Ροή ελάχιστου κόστους: αλγόριθμος απαλοιφής αρνητικών κύκλων, αλγόριθμος επαναλαμβανόμενων συντομότερων μονοπατιών. Σημειώσεις του Jeff Erickson για το πρόβλημα της ροής ελάχιστου κόστους.
- Διάλεξη 14/12/2023: Μηχανές Turing και υπολογισιμότητα.
- Διάλεξη 18/12/2023: Υπολογιστική πολυπλοκότητα. Αναγωγές.
- Διάλεξη 21/12/2023: Μη ντετερμινισμός. Η κλάση NP. NP-πληρότητα.
- Διάλεξη 8/1/2024: NP-πληρότητα: SAT (Θεώρημα Cook), 3-SAT, MAX 2-SAT, MIS, VC, CLIQUE, SET COVER.
- Πρόσθετη μελέτη: NP-πληρότητα: 3-COLORING, 3DM, Knapsack. Προσεγγιστικοί αλγόριθμοι: κλάσεις προσεγγισιμότητας, Vertex Cover (unweighted), Set Cover (logn- και Hn-προσεγγιστικός αλγόριθμος), Maximum Coverage, TSP inapproximability, Metric TSP: 2-προσεγγιστικός αλγόριθμος και 3/2-προσεγγιστικός αλγόριθμος (χωρίς απόδειξη).