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

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

Περιγραφή

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

Κωδικός: MHX109
Κατηγορία: Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών » Προπτυχιακό
CC - Αναφορά - Μη Εμπορική Χρήση - Όχι Παράγωγα Έργα
CC - Αναφορά - Μη Εμπορική Χρήση - Όχι Παράγωγα Έργα

Θεματικές Ενότητες

Διαίρει και Βασίλευε, Δυναμικός Προγραμματισμός, Απληστία

Εισαγωγή στα Γραφήματα

Εφαρμογές ΑσΒ

Εφαρμογές ΑσΒ, Αναζήτηση κατα Πλάτος (ΑκΠ), Δένδρο ΑκΠ, Κατευθυνόμενα Γραφήματα

Μεταβατική Κλειστότητα, Ισχυρές Συνιστώσες (Kosaraju)

Εφαρμογές: Ισχυρές Συνιστώσες(Tarjan, Gabow)

Dijkstra, Bellman-Ford, ΚΑΓ

Ροές

Τροποποίηση Goldberg-Tarjan, Ροές Ελάχιστου Κόστους, Ορισμοί Συμβολοσειρών, Knuth-Morris-Pratt

Χρήση του f, Boyer-Moore, Ευρετικό Εμφανίσεως, Ευρετικό Ταιριάσματος,

Συμβολοσειρές: ΒΜ

Συμβολοσειρές: Δυναμικός Προγραμματισμός, Huffman, Κρυπτογραφία

Δημόσιο Κλειδί RSA, Ντετερμινιστικός Αλγόριθμος, Πιθανοτικός Αλγόριθμος

Κρυφή Μνήμη (Caching), LRU, LiFo, Πολιτική Μαρκαδόρου

Θεωρία Υπολογισμού, Κλάση, P / co-P / NP / NPC

Περιοδεύων Πωλητής (TSP), Κάλυμμα Συνόλου, First Fit, Best Fit, First Fit decreasing, K-κέντρο, Απεικονίσεις Προβλημάτων NPC

Ανοικτό Ακαδ. Μάθημα

Ανοικτά Ακαδημαϊκά Μαθήματα
Επίπεδο: A+

Αρ. Επισκέψεων :  2490
Αρ. Προβολών :  12728

Ημερολόγιο

Ανακοινώσεις

  • Σάββατο, 19 Ιανουαρίου 2013