Section outline
-
- Διάλεξη 30/9/2024: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
- Διάλεξη 3/10/2024: Ασυμπτωτικός Συμβολισμός (γρήγορη επανάληψη). Σύντομη αναφορά και επανάληψη βασικών εννοιών δομών δεδομένων: λεξικό - balanced binary search trees και hashing, ουρές προτεραιότητας - σωροί.
- Διάλεξη 7/10/2024: Γρήγορη επανάληψη βασικών εννοιών δομών δεδομένων: prefix-sums και binary indexed trees, min-range queries, lowest common ancestor, union-find, tries.
- Διάλεξη 10/10/2024: Min-range queries, lowest common ancestor (αναγωγές μεταξύ των δύο προβλημάτων), Αλγόριθμοι Διαίρει-και-Βασίλευε:mergesort, master theorem (δείτε και αυτές τις σημειώσεις για την επίλυση αναδρομικών σχέσεων και το master theorem).
- Διάλεξη 14/10/2024. Αλγόριθμοι Διαίρει-και-Βασίλευε: πλησιέστερο ζεύγος σημείων, μέτρηση αντιστροφών (γρήγορη αναφορά, δείτε την αντίστοιχη άσκηση στην 1η σειρά λυμένων ασκήσεων), σύντομη επανάληψη στο master theorem.
- Διάλεξη 17/10/2024. Κυρτό κάλυμμα (δείτε και αυτές τις σημειώσεις για αποδοτικούς αλγόριθμους που υπολογίζουν το κυρτό κάλυμμα). Quicksort.
- Διάλεξη 21/10/2024. Quicksort. Επιλογή σε γραμμικό χρόνο. Ντετερμινιστική επιλογή σε γραμμικό χρόνο.
- Διάλεξη 24/10/2024. Ταξινόμηση σε γραμμικό χρόνο. Αναζήτηση:Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις για το πρόβλημα αναδιοργάνωσης μιας γραμμικής λίστας (List Update) και την ανάλυση του Move-to-Front. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή.
- Διάλεξη 31/10/2024. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι αλγόριθμοι.
- Διάλεξη 4/11/2024. Άπληστοι αλγόριθμοι: επιλογή διαστημάτων, χρωματισμός διαστημάτων, coin change.
- Διάλεξη 5/11/2024. Άπληστοι αλγόριθμοι: ελαχιστοποίηση συνολικού χρόνου ολοκλήρωσης (χωρίς και με βάρη), κλασματικό πρόβλημα σακιδίου. Δυναμικός προγραμματισμός.
- Διάλεξη 7/11/2024. Δυναμικός προγραμματισμός: διακριτό πρόβλημα σακιδίου, subset sum, coin change, επιλογή διαστημάτων με βάρη.
- Διάλεξη 11/11/2024. Δυναμικός προγραμματισμός: επιλογή διαστημάτων με βάρη, αναδρομή με απομνημόνευση, μέγιστο ανεξάρτητο σύνολο στη γραμμή, σε δέντρα και σε πλέγμα σταθερού πλάτους.
- Διάλεξη 14/11/2024. Δυναμικός προγραμματισμός: πολλαπλασιασμός ακολουθίας πινάκων (παράδειγμα κώδικα python για το πρόβλημα πολλαπλασιασμού ακολουθίας πινάκων),
- Διάλεξη 19/11/2024. Δυναμικός προγραμματισμός: χωρισμός ακολουθίας σε διαστήματα, πρόβλημα πλανόδιου πωλητή (TSP). Συντομότερα μονοπάτια: βασικές έννοιες.
- Διάλεξη 21/11/2024. Συντομότερα μονοπάτια από μία αρχική κορυφή: ιδιότητα βέλτιστων επιμέρους λύσεων, βασικό αλγοριθμικό σχήμα, δυναμικός προγραμματισμός - αλγόριθμος Bellman-Ford, συντομότερα μονοπάτια σε DAG, απληστία - αλγόριθμος Dijkstra.
- Διάλεξη 25/11/2024. Συντομότερα μονοπάτια από μία αρχική κορυφή: αλγόριθμος Dijkstra. Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson.
- Διάλεξη 28/11/2024: Μέγιστη ροή και ελάχιστη τομή: υπολλειματικό δίκτυο, αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp, εφαρμογή στον υπολογισμό μέγιστου ταιριάσματος σε διμερή γραφή. Διαφάνειες Kleinberg-Tardos και σημειώσεις του Jeff Erickson για υπολογισμό μέγιστης ροής και ελάχιστης τομής.
- Διάλεξη 2/12/2024 String Matching: αλγόριθμοι Karp Rabin, KMP. Σημειώσεις του Jeff Erickson για string matching.
- Διάλεξη 5/12/2024 String Matching: υπολογισμός της Failure Function. Κωδικοποίηση Huffman.
- Διάλεξη 9/12/2024: Εισαγωγή στην υπολογισιμότητα. Υπολογιστικά προβλήματα και τυπικές γλώσσες. Η έννοια του αλγορίθμου. Μηχανές Turing. Αποκρίσιμες και ημι-αποκρίσιμες γλώσσες. Το πρόβλημα των Διοφαντικών εξισώσεων.
- Διάλεξη 12/12/2024: Η θέση Church-Turing. Μη υπολογισιμότητα. Το πρόβλημα τερματισμού (Halting Problem) και η μέθοδος της διαγωνιοποίησης. Δείτε και σημειώσεις του Jeff Erickson για μη υπολογισιμότητα (έως και ενότητα 7.10).
- Διάλεξη 16/12/2024: Υπολογιστική πολυπλοκότητα. Χρονική πολυπλοκότητα ντετερμινιστικής μηχανής Turing. Οι κλάσεις πολυπλοκότητας P και EXP. Αναγωγές (πολυωνυμικού χρόνου). Δύσκολα και πλήρη προβλήματα για κλάσεις πολυπλοκότητας. Η αναγωγή του Hamilton Cycle στο TSP.
- Διάλεξη 19/12/2024: Απλά παραδείγματα αναγωγών: πολυωνυμική ισοδυναμία Vertex Cover, Independent Set, και Clique. Πολυωνυμικός αλγόριθμος για 2-SAT (αναγωγή σε Non-Reachability).
Μη-ντετερμινισμός. Η κλάση NP. Περιγραφή της NP μέσω συνοπτικών πιστοποιητικών. NP-πλήρη προβλήματα. Η κλάση co-NP. Σημειώσεις Jeff Erickson για μη-ντετερμινισμό και για NP-πληρότητα. - Διάλεξη 9/1/2024: Το Θεώρημα του Cook: NP-πληρότητα του SAT. NP-πληρότητα των 3-SAT, Max 2-SAT, Independent Set, Integer Programming, Set Cover, Subgraph Isomorphism, 3-Colorability, 3-D Matching (απλή αναφορά).