Section outline
-
- Διάλεξη 11/10/2021: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
- Διάλεξη 14/10/2021: Ασυμπτωτικός Συμβολισμός (εκτενής επανάληψη).
- Διάλεξη 18/10/2021: Αποδοτικοί αλγόριθμοι, fine-grained complexity (απλή αναφορά, δείτε διαφάνειες, διαφάνειες και survey, για περισσότερες πληροφορίες). Δομές δεδομένων, abstract data types, λεξικό, hash tables (δείτε σημειώσεις και εκτενείς σημειώσεις για περισσότερες πληροφορίες) ουρές προτεραιότητας, σωρός (απλή αναφορά). Union - Find. Δείτε και τις βιντεοσκοπήσεις των αντίστοιχων περυσινών διαλέξεων: 15/10/2020 και 19/10/2020.
- Διάλεξη 21/10/2021: Union - Find. Λίγο περισσότερες δομές δεδομένων: Range Sum Queries και Binary Indexed Trees, Range Minimum Queries και Lowest Common Ancestor. Δείτε και τις βιντεοσκοπήσεις της αντίστοιχης περυσινής διάλεξης: 22/10/2020.
- Διάλεξη 25/10/2021: Range Minimum Queries και Lowest Common Ancestor. Ταξινόμηση σε γραμμικό χρόνo.
- Διάλεξη 1/11/2021:Σύντομη επανάληψη συγκριτικών μεθόδων ταξινόμησης. Ταξινόμηση σε γραμμικό χρόνo (links με σχετικό υλικό: 1, 2, 3, 4, 5). Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem. Δείτε και τις βιντεοσκοπήσεις των αντίστοιχων περυσινών διαλέξεων: 26/10/2020 και 29/10/2020.
- Διάλεξη 4/11/2021: Master theorem και εφαρμογές. Πλησιέστερο ζεύγος σημείων. Quicksort.
- Διάλεξη 8/11/2021: Πιθανοτική Quicksort. Το πρόβλημα της επιλογής. Ντετερμινιστική επιλογή σε γραμμικό χρόνο. Δείτε και τις βιντεοσκοπήσεις των αντίστοιχων περυσινών διαλέξεων: 2/11/2020, 5/11/2020 και 9/11/2020.
- Διάλεξη 11/11/2021: Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή. Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης.
- Διάλεξη 18/11/2021: Άπληστοι Αλγόριθμοι.
- Διάλεξη 22/11/2021: Άπληστοι Αλγόριθμοι. Δυναμικός Προγραμματισμός.
- Διάλεξη 25/11/2021: Δυναμικός Προγραμματισμός.
- Διάλεξη 29/11/2021: Δυναμικός Προγραμματισμός.
- Διάλεξη 2/12/2021: Περισσότερα παραδείγματα και ασκήσεις σε δυναμικός προγραμματισμό. Δείτε ακόμη το 1ο πρόβλημα από μια παλιά σειρά προγραμματιστικών ασκήσεων.
- Διάλεξη 9/12/2021: Αναζήτηση κατά Πλάτος (BFS) και Αναζήτηση κατά Βάθος (DFS) (γρήγορη επανάληψη - για μια πιο αναλυτική παρουσίαση, δείτε τις περυσινές διαλέξεις: 3/12/2020 και 7/12/2020). Εφαρμογές: αναγνώριση διμερούς γραφήματος, υπολογισμός σημείων κοπής και γεφυρών, τοπολογική ταξινόμηση, υπολογισμός ισχυρά συνεκτικών συνιστωσών. Ελάχιστο Συνδετικό Δέντρο: άπληστος αλγόριθμος, ορθότητα.
- Διάλεξη 13/12/2021: Ελάχιστο Συνδετικό Δέντρο: άπληστος αλγόριθμος, ορθότητα (επανάληψη). Αλγόριθμοι Kruskal, Prim, Boruvka. Ασκήσεις (μοναδικότητα, bottleneck spanning tree, second best spanning tree). Δείτε και τις περυσινές διαλέξεις: 7/12/2020 και 10/12/2020.
- Διάλεξη 16/12/2021: Συζήτηση 2ης σειράς γραπτών ασκήσεων. Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικές έννοιες.
- Διάλεξη 20/12/2021: Συντομότερα μονοπάτια από μία αρχική κορυφή: Αλγόριθμος Bellman-Ford (επανάληψη), συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. Ασκήσεις.
- Διάλεξη 21/12/2021: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Μέγιστη ροή - ελάχιστη τομή.
- Διάλεξη 10/1/2022: Μέγιστη ροή - ελάχιστη τομή: Αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Μηχανές Turing και Υπολογισιμότητα.
- Διάλεξη 11/1/2022: Μηχανές Turing και Υπολογισιμότητα. Υπολογιστική Πολυπλοκότητα. Αναγωγές.
- Διάλεξη 13/1/2022: Αναγωγές. Μη Ντετερμινισμός.Η κλάση NP.
- Διάλεξη 17/1/2022: NP-Πληρότητα και NP-πλήρη προβλήματα. Παραδείγματα Αναγωγών.
- Διάλεξη 20/1/2022: Παραδείγματα Αναγωγών. Συζήτηση για εξετάσεις.