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