Αλγόριθμοι - Ανοιχτό Ψηφιακό Μάθημα
Παναγιώτης Μποζάνης
Το μάθημα αποτελεί μία εισαγωγή στις τεχνικές σχεδιασμού και μαθηματικής αναλύσεως των ιδιοτήτων των αλγορίθμων, με σκοπό την εύρεση της χρονικής και χωρικής υπολογιστικής πολυπλοκότητας στην μέση, την χειρότερη και την καλύτερη περίπτωση. Τα καλυπτόμενα θέματα περιλαμβάνουν: Γενικές τεχνικές σχεδιασμού αλγορίθμων, όπως διαίρει-και-βασίλευε, δυναμικός προγραμματισμός και άπληστοι αλγόριθμοι. Βασικές έννοιες της ανάλυσης αλγορίθμων, π.χ. μέση, χειρότερη και κατανεμημένη συμπεριφορά. Εισαγωγή στους αλγορίθμους γραφημάτων (αναπαράσταση και διέλευση γραφημάτων, συνεκτικές συνιστώσες, ισχυρώς συνεκτικές συνιστώσες και δισυνεκτικότητα, ελάχιστα επικαλύπτοντα δένδρα, συντομότερα μονοπάτια, ροές και ταιριάσματα). Βασικοί αλγόριθμοι συμβολοσειρών. Ανταγωνιστική ανάλυση και ‘on-line’ Αλγόριθμοι. Αριθμητικοί Αλγόριθμοι και RSA. Εισαγωγή στην πληρότητα NP και τις τάξεις της, Προσεγγιστικοί Αλγόριθμοι, Σχεδιασμός αλγορίθμων για προβλήματα NPC
ΛιγότεραΤο μάθημα αποτελεί μία εισαγωγή στις τεχνικές σχεδιασμού και μαθηματικής αναλύσεως των ιδιοτήτων των αλγορίθμων, με σκοπό την εύρεση της χρονικής και χωρικής υπολογιστικής πολυπλοκότητας στην μέση, την χειρότερη και την καλύτερη περίπτωση. Τα καλυπτόμενα θέματα περιλαμβάνουν: Γενικές τεχνικές σχεδιασμού αλγορίθμων, όπως διαίρει-και-βασίλευε, δυναμικός προγραμματισμός και άπληστοι αλγόριθμοι. Βασικές έννοιες της ανάλυσης αλγορίθμων, π.χ. μέση, χειρότερη και κατανεμημένη συμπεριφορά. Εισαγωγή στους αλγορίθμους γραφημάτων (αναπαράσταση και διέλευση γραφημάτων, συνεκτικές συνιστώσες, ισχυρώς συνεκτικές συνιστώσες και δισυνεκτικότητα, ελάχιστα επικαλύπτοντα δένδρα, συντομότερα μονοπάτια, ροές και ταιριάσματα). Βασικοί αλγόριθμοι συμβολοσειρών. Ανταγωνιστική ανάλυση και ‘on-line’ Αλγόριθμοι. Αριθμητικοί Αλγόριθμοι και RSA. Εισαγωγή στην πληρότητα NP και τις τάξεις της, Προσεγγιστικοί Αλγόριθμοι, Σχεδιασμός αλγορίθμων για προβλήματα NPC
Το μάθημα αποτελεί μία εισαγωγή στις τεχνικές σχεδιασμού και μαθηματικής αναλύσεως των ιδιοτήτων των αλγορίθμων, με σκοπό την εύρεση της χρονικής και χωρικής υπολογιστικής πολυπλοκότητας στην μέση, την χειρότερη και την καλύτερη περίπτωση. Τα καλυπτόμενα θέματα περιλαμβάνουν: Γενικές τεχνικές σχεδιασμού αλγορίθμων, όπως διαίρει-και-βασίλευε, δυναμικός προγραμματισμός και άπληστοι αλγόριθμοι. Βασικές έννοιες της ανάλυσης αλγορίθμων, π.χ. μέση, χειρότερη και κατανεμημένη συμπεριφορά. Εισαγωγή στους αλγορίθμους γραφημάτων (αναπαράσταση και διέλευση γραφημάτων, συνεκτικές συνιστώσες, ισχυρώς συνεκτικές συνιστώσες και δισυνεκτικότητα, ελάχιστα επικαλύπτοντα δένδρα, συντομότερα μονοπάτια, ροές και ταιριάσματα). Βασικοί αλγόριθμοι συμβολοσειρών. Ανταγωνιστική ανάλυση και ‘on-line’ Αλγόριθμοι. Αριθμητικοί Αλγόριθμοι και RSA. Εισαγωγή στην πληρότητα NP και τις τάξεις της, Προσεγγιστικοί Αλγόριθμοι, Σχεδιασμός αλγορίθμων για προβλήματα NPC
Κατηγορία: Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών » Προπτυχιακό
CC - Αναφορά - Μη Εμπορική Χρήση - Όχι Παράγωγα Έργα
Θεματικές Ενότητες
Διαίρει και Βασίλευε, Δυναμικός Προγραμματισμός, Απληστία
Εισαγωγή στα Γραφήματα
Εφαρμογές ΑσΒ
Εφαρμογές ΑσΒ, Αναζήτηση κατα Πλάτος (ΑκΠ), Δένδρο ΑκΠ, Κατευθυνόμενα Γραφήματα
Μεταβατική Κλειστότητα, Ισχυρές Συνιστώσες (Kosaraju)
Εφαρμογές: Ισχυρές Συνιστώσες(Tarjan, Gabow)
Prim, Kruskal, Baruvka
Dijkstra, Bellman-Ford, ΚΑΓ
Floyd, Johnson, Ροές
Ροές
Τροποποίηση 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
