Θέμα: Διαλέξεις | Αλγόριθμοι και Πολυπλοκότητα

Ημερολόγιο

Δευτέρα	Τρίτη	Τετάρτη	Πέμπτη	Παρασκευή	Σάββατο	Κυριακή
				Κανένα γεγονός, Παρασκευή, 1 Νοεμβρίου Κανένα γεγονός, Παρασκευή, 1 Νοεμβρίου	Κανένα γεγονός, Σάββατο, 2 Νοεμβρίου Κανένα γεγονός, Σάββατο, 2 Νοεμβρίου	Κανένα γεγονός, Κυριακή, 3 Νοεμβρίου Κανένα γεγονός, Κυριακή, 3 Νοεμβρίου
Κανένα γεγονός, Δευτέρα, 4 Νοεμβρίου Κανένα γεγονός, Δευτέρα, 4 Νοεμβρίου	Κανένα γεγονός, Τρίτη, 5 Νοεμβρίου Κανένα γεγονός, Τρίτη, 5 Νοεμβρίου	Κανένα γεγονός, Τετάρτη, 6 Νοεμβρίου Κανένα γεγονός, Τετάρτη, 6 Νοεμβρίου	Κανένα γεγονός, Πέμπτη, 7 Νοεμβρίου Κανένα γεγονός, Πέμπτη, 7 Νοεμβρίου	Κανένα γεγονός, Παρασκευή, 8 Νοεμβρίου Κανένα γεγονός, Παρασκευή, 8 Νοεμβρίου	Κανένα γεγονός, Σάββατο, 9 Νοεμβρίου Κανένα γεγονός, Σάββατο, 9 Νοεμβρίου	Κανένα γεγονός, Κυριακή, 10 Νοεμβρίου Κανένα γεγονός, Κυριακή, 10 Νοεμβρίου
Κανένα γεγονός, Δευτέρα, 11 Νοεμβρίου Κανένα γεγονός, Δευτέρα, 11 Νοεμβρίου	Κανένα γεγονός, Τρίτη, 12 Νοεμβρίου Κανένα γεγονός, Τρίτη, 12 Νοεμβρίου	Κανένα γεγονός, Τετάρτη, 13 Νοεμβρίου Κανένα γεγονός, Τετάρτη, 13 Νοεμβρίου	Κανένα γεγονός, Πέμπτη, 14 Νοεμβρίου Κανένα γεγονός, Πέμπτη, 14 Νοεμβρίου	Κανένα γεγονός, Παρασκευή, 15 Νοεμβρίου Κανένα γεγονός, Παρασκευή, 15 Νοεμβρίου	Κανένα γεγονός, Σάββατο, 16 Νοεμβρίου Κανένα γεγονός, Σάββατο, 16 Νοεμβρίου	Κανένα γεγονός, Κυριακή, 17 Νοεμβρίου Κανένα γεγονός, Κυριακή, 17 Νοεμβρίου
Κανένα γεγονός, Δευτέρα, 18 Νοεμβρίου Κανένα γεγονός, Δευτέρα, 18 Νοεμβρίου	Κανένα γεγονός, Τρίτη, 19 Νοεμβρίου Κανένα γεγονός, Τρίτη, 19 Νοεμβρίου	Κανένα γεγονός, Τετάρτη, 20 Νοεμβρίου Κανένα γεγονός, Τετάρτη, 20 Νοεμβρίου	Κανένα γεγονός, Πέμπτη, 21 Νοεμβρίου Κανένα γεγονός, Πέμπτη, 21 Νοεμβρίου	Κανένα γεγονός, Παρασκευή, 22 Νοεμβρίου Κανένα γεγονός, Παρασκευή, 22 Νοεμβρίου	Κανένα γεγονός, Σάββατο, 23 Νοεμβρίου Κανένα γεγονός, Σάββατο, 23 Νοεμβρίου	Κανένα γεγονός, Κυριακή, 24 Νοεμβρίου Κανένα γεγονός, Κυριακή, 24 Νοεμβρίου
Κανένα γεγονός, Δευτέρα, 25 Νοεμβρίου Κανένα γεγονός, Δευτέρα, 25 Νοεμβρίου	Κανένα γεγονός, Τρίτη, 26 Νοεμβρίου Κανένα γεγονός, Τρίτη, 26 Νοεμβρίου	Κανένα γεγονός, Τετάρτη, 27 Νοεμβρίου Κανένα γεγονός, Τετάρτη, 27 Νοεμβρίου	Κανένα γεγονός, Πέμπτη, 28 Νοεμβρίου Κανένα γεγονός, Πέμπτη, 28 Νοεμβρίου	Κανένα γεγονός, Παρασκευή, 29 Νοεμβρίου Κανένα γεγονός, Παρασκευή, 29 Νοεμβρίου	Κανένα γεγονός, Σάββατο, 30 Νοεμβρίου Κανένα γεγονός, Σάββατο, 30 Νοεμβρίου

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.

Νοεμβρίου 2024

Section outline