Τεχνικές σχεδιασμού και ανάλυσης αλγορίθμων, εισαγωγή στη θεωρία υπολογιστικής πολυπλοκότητας. Τεχνικές για ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας, κριτήρια επιλογής αλγορίθμων, πολυωνυμικοί αλγόριθμοι. Διαίρει-και-Βασίλευε αλγόριθμοι, εκτίμηση υπολογιστικής πολυπλοκότητας αναδρομικών αλγορίθμων με το θεώρημα κυρίαρχου όρου, ταξινόμηση με συγχώνευση, ταξινόμηση με διαίρεση, επιλογή, πλησιέστερο ζεύγος σημείων, κυρτό κάλυμμα. Ταξινόμηση γραμμικού χρόνου. Δυαδική αναζήτηση, αναζήτηση με παρεμβολή, ενημέρωση λίστας, ανάλυση με κατανομή κόστους. Άπληστοι αλγόριθμοι, αποδείξεις ορθότητας με επιχείρημα ανταλλαγής. Δυναμικός προγραμματισμός, πρόβλημα σακιδίου, μακρύτερη κοινή υπακολουθία, μακρύτερη αύξουσα υπακολουθία, γραμμικός διαχωρισμός, πολλαπλασιασμός ακολουθίας πινάκων, πρόβλημα πλανόδιου πωλητή. Αλγόριθμοι γραφημάτων. Συντομότερα μονοπάτια, υπολογισμός συντομότερων μονοπατιών με ενημέρωση ετικετών, αλγόριθμοι Bellman-Ford, Dijkstra, Floyd-Warshall, Johnson. Μέγιστη ροή και ελάχιστη τομή, αλγόριθμοι Ford-Fulkerson και Edmonds-Karp, εφαρμογές. Υπολογισιμότητα και υπολογιστική πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις P και NP, NP-complete προβλήματα. Κλάσεις χωρικής πολυπλοκότητας. Αλγόριθμοι προσέγγισης, κάλυμμα κορυφών, κάλυμμα συνόλων, πρόβλημα πλανόδιου πωλητή. Πιθανοτικοί αλγόριθμοι, αλγόριθμος για ελάχιστη τομή. Εργαστήριο: Μια σειρά αλγοριθμικών προβλημάτων που πρέπει να λυθούν σε C++.
- Διδάσκων: Δημήτριος Φωτάκης
Τομέας: Τεχνολογίας Πληροφορικής και Υπολογιστών
Κατεύθυνση: Πληροφορικής, Ροή Λ
Διδακτικές Μονάδες : 6
Φόρτος Εργασίας : theory 4, lab 1
Γλώσσα : el
Μαθησιακά Αποτελέσματα : Το μάθημα αποτελεί το βασικό μάθημα στην ευρύτερη περιοχή των Αλγορίθμων και της Υπολογιστικής Πολυπλοκότητας. Στοιχεία αλγοριθμικής σκέψης και της προσέγγισης που εφαρμόζει η περιοχή της υπολογιστικής πολυπλοκότητας, κάποιες βασικές έννοιες σχεδιασμού και ανάλυσης αλγορίθμων, και κάποιοι βασικοί αλγόριθμοι διδάσκονται διάσπαρτα σε μαθήματα κορμού (Προγραμματισμός Ηλεκτρονικών Υπολογιστών, Προγραμματιστικές Τεχνικές, Θεμελιώδη Θέματα Επιστήμης Υπολογιστών). Με αυτό ως δεδομένο, η ύλη του μαθήματος στοχεύει στο να δώσει στους φοιτητές μια συνολική, συστηματική και σε βάθος εικόνα της περιοχής των Αλγορίθμων και της Υπολογιστικής Πολυπλοκότητας. Ειδικότερα, η ύλη του μαθήματος καλύπτει, και αντιμετωπίζει με ενιαίο και συστηματικό τρόπο, αφενός τις βασικές τεχνικές σχεδιασμού και ανάλυσης αποδοτικών δομών δεδομένων και αλγορίθμων (όπως η έννοια της ιεραρχικής οργάνωσης και διαχείρισης δεδομένων για την περιοχή των δομών δεδομένων, και οι τεχνικές του διαίρει-και-βασίλευε, των άπληστων αλγορίθμων, του δυναμικού προγραμματισμού, και της τοπικής αναζήτησης), και αφετέρου συγκεκριμένες δομές δεδομένων και αλγόριθμους ως αποτέλεσμα εφαρμογής αυτών των τεχνικών (βλ. ουρές προτεραιότητας, διαχείριση ξένων συνόλων, αλγόριθμους ταξινόμησης, αλγόριθμους για υπολογισμό ελάχιστου συνδετικού δέντρου και συντομότερων μονοπατιών, και αλγόριθμους για τον υπολογισμό μέγιστης τομής-ελάχιστης ροής). Επιπλέον, η ύλη του μαθήματος επιχειρεί μια συστηματική εισαγωγή στις βασικές αρχές της θεωρίας Υπολογιστικής Πολυπλοκότητας, ξεκινώντας από μια συστηματική προσέγγιση της θεμελιώδους έννοιας της αναγωγής, και τις εφαρμογές της στην περιοχή των αλγορίθμων και στην περιοχή της υπολογιστικής πολυπλοκότητας, και εμβαθύνοντας στη θεωρία της NP-πληρότητας. Το μάθημα συνοδεύεται από εργαστηριακό κομμάτι, όπου οι φοιτητές καλούνται να επιλύσουν αλγοριθμικά προβλήματα με βέλτιστο τρόπο, σχεδιάζοντας και υλοποιώντας τους αλγορίθμους τους. Κεντρικός στόχος του μαθήματος είναι να αποκτήσουν οι φοιτητές επαρκές γνωστικό υπόβαθρο και ευχέρεια στη εφαρμογή όλων των παραπάνω εννοιών, ιδεών και τεχνικών στην περιοχή των Αλγορίθμων και της Υπολογιστικής Πολυπλοκότητας για την μοντελοποίηση και την αποδοτική επίλυση αλγοριθμικών προβλημάτων.