Αλγόριθμοι - Ανοιχτό Ψηφιακό Μάθημα

Το μάθημα αποτελεί μία εισαγωγή στις τεχνικές σχεδιασμού και μαθηματικής αναλύσεως των ιδιοτήτων των αλγορίθμων, με σκοπό την εύρεση της χρονικής και χωρικής υπολογιστικής πολυπλοκότητας στην μέση, την χειρότερη και την καλύτερη περίπτωση. Τα καλυπτόμενα θέματα περιλαμβάνουν: Γενικές τεχνικές σχεδιασμού αλγορίθμων, όπως διαίρει-και-βασίλευε, δυναμικός προγραμματισμός και άπληστοι αλγόριθμοι. Βασικές έννοιες της ανάλυσης αλγορίθμων, π.χ. μέση, χειρότερη και κατανεμημένη συμπεριφορά. Εισαγωγή στους αλγορίθμους γραφημάτων (αναπαράσταση και διέλευση γραφημάτων, συνεκτικές συνιστώσες, ισχυρώς συνεκτικές συνιστώσες και δισυνεκτικότητα, ελάχιστα επικαλύπτοντα δένδρα, συντομότερα μονοπάτια, ροές και ταιριάσματα). Βασικοί αλγόριθμοι συμβολοσειρών. Ανταγωνιστική ανάλυση και ‘on-line’ Αλγόριθμοι. Αριθμητικοί Αλγόριθμοι και RSA. Εισαγωγή στην πληρότητα NP και τις τάξεις της, Προσεγγιστικοί Αλγόριθμοι, Σχεδιασμός αλγορίθμων για προβλήματα NPC

Βιβλία:

[1] Αλγόριθμοι, Π.Δ. Μποζανης

[2] Προβλήματα και Ασκήσεις στους Αλγορίθμους, Π.Δ. Μποζανης

[3] Εισαγωγή στην Σχεδίαση και Ανάλυση Αλγορίθμων,  A. Levitin

[4] Σχεδιάση και Ανάλυση Αλγορίθμων,  Κ. Παπαριζοσ

Βιβλία Βιβλιοθήκης: 

Το μάθημα καλύπτει τις βασικές αρχές του σχεδιασμού και ανάλυσης αλγορίθμων ενώ εμφαίνεται η κρισιμότητα της επιλογής κατάλληλων δομών δεδομένων για την αποδοτικότητα των λύσεων.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής / τρια θα είναι σε θέση να:

• γνωρίζει,κατανοεί και εφαρμόζει τις θεμελιώδεις τεχνικές σχεδίασης αλγορίθμων (διαίρει και βασίλευε, δυναμικός προγραμματισμός, απληστία)
• γνωρίζει να αναλύει αλγορίθμους και να εκτιμά την συμπεριφορά τους στην χειρότερη, την μέση και την επιμερισμένη περίπτωση, εκφράζοντας τους σε μία ψευδογλώσσα
• κατανοεί πώς η εφαρμογή κατάλληλων δομών δεδομένων επηρεάζει τις επιδόσεις των αλγορίθμων
• γνωρίζει πώς να εφαρμόζει βασικούς αλγορίθμους που αφορούν τα γραφήματακαι τις συμβολοσειρές
• διακρίνει τις κλάσεις πολυπλοκότητας και να γνωρίζει τις ευρετικές τεχνικές επίλυσης προβλημάτων NPC

Μποζάνης Παναγιώτης

Τεχνικές Σχεδιασμού Αλγορίθμων
Εισαγωγή στα Γραφήματα
Διαπέραση Γραφημάτων
Διαπεράσεις Γραφημάτων - Κατευθυνόμενα Άκυκλα Γραφήματα
Εφαρμογές: Μεταβατική Κλειστότητα, Ισχυρές Συνιστώσες (Kosaraju)
Εφαρμογές: Ισχυρές Συνιστώσες(Tarjan, Gabow)
Ελάχιστα Επικαλύπτοντα Δένδρα (Prim, Kruskal, Baruvka)
Συντομότερα Μονοπάτια (Dijkstra, Bellman-Ford, ΚΑΓ)
Συντομότερα Μονοπάτια (Floyd, Johnson), Ροές
Ροές
Συμβολοσειρές
Εισαγωγή στις Συμβολοσειρές, Συμβολοσειρές: KMP
Συμβολοσειρές: ΒΜ
Συμβολοσειρές: Δυναμικός Προγραμματισμός, Huffman, Κρυπτογραφία
Κρυπτοσύστημα RSA, Ανταγωνιστική Ανάλυση: Αναζήτηση τιμής
Ανταγωνιστική Ανάλυση: Αναζήτηση τιμής, Διαχείριση Κρυφής Μνήμης
Θεωρία πολυπλοκότητας
Προσεγγιστικοί Αλγοριθμοι

Διακριτά Μαθηματικά, Δομές Δεδομένων