Αλγόριθμοι και Πολυπλοκότητα
Νικόλαος Μισυρλής
Βασικές αρχές σχεδίασης αλγορίθμων : Διαίρει και Βασίλευε, Αλγόριθμοι Γραφημάτων, Άπληστοι Αλγόριθμοι, Δυναμικός Προγραμματισμός.
ΛιγότεραΒασικές αρχές σχεδίασης αλγορίθμων : Διαίρει και Βασίλευε, Αλγόριθμοι Γραφημάτων, Άπληστοι Αλγόριθμοι, Δυναμικός Προγραμματισμός.
Βασικές αρχές σχεδίασης αλγορίθμων : Διαίρει και Βασίλευε, Αλγόριθμοι Γραφημάτων, Άπληστοι Αλγόριθμοι, Δυναμικός Προγραμματισμός.
Περίγραμμα
Περιεχόμενο μαθήματος
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Πολυπλοκότητα κατά μέσο όρο και πολυπλοκότητα στη χείριστη περίπτωση. Σωροί, Heapsort. Τεχνικές σχεδίασης αλγορίθμων. Διαίρει και Βασίλευε: Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις, αλγόριθμοι ταξινόμησης, δυαδική αναζήτηση, το θεώρημα κυριαρχίας (master theorem), αναδρομικοί αριθμητικοί αλγόριθμοι, Στατιστικές κλίμακας, Πλησιέστερο ζεύγος σημείων. Union and find. Βασικοί αλγόριθμοι γραφημάτων: Οριζόντια διερεύνηση (BFS), καθοδική διερεύνηση (DFS), συνδεδεμένες συνιστώσες. Ομοαφετηριακές ελαφρύτατες διαδρομές (Dijkstra, Bellman-Ford). Τοπολογική Ταξινόμηση. Ελαφρύτατα συνδετικά δέντρα (Prim, Kruskal). Άπληστοι αλγόριθμοι: Γενική μορφή ενός άπληστου αλγορίθμου. Χρονοπρογραμματισμός διαστημάτων, το συνεχές πρόβλημα του σακιδίου (knapsack problem), κώδικες Huffman. Δυναμικός προγραμματισμός: Χρονοπρογραμματισμός γραμμής παραγωγής, πολλαπλασιασμός αλληλουχίας πινάκων, μέγιστη κοινή υπακολουθία, το διακριτό πρόβλημα του σακιδίου, τμηματοποιημένα ελάχιστα τετράγωνα.
Μαθησιακοί στόχοι
Αναλύοντας τους αλγόριθμους στόχος μας είναι να διερευνήσουμε πως οι απαιτούμενοι για την εκτέλεσή τους πόροι, δηλαδή ο χρόνος και η μνήμη που χρησιμοποιούν, διακυμαίνονται με την αυξανόμενη διάσταση της εισόδου. Έτσι μπορούμε να αποτιμήσουμε την επίδοση ενός αλγορίθμου, να συγκρίνουμε δυο αλγόριθμους που επιλύουν το ίδιο πρόβλημα και να αναπτύξουμε έναν αποδοτικό αλγόριθμο για ένα πρόβλημα. Το ενδιαφέρον εστιάζεται στη κατανόηση ορισμένων βασικών τεχνικών σχεδίασης αλγορίθμων και στη διάκριση των προβλημάτων σε αυτά που θεωρούνται πρακτικώς επιλύσιμα και σε αυτά που θεωρούνται πρακτικώς δυσεπίλυτα.
Προτεινόμενα συγγράμματα
- Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001.
- Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006.
- Dasgupta, C. H. Papadimitriou and U. V. Vazirani, Algorithms, MacGraw Hill, 2008.
Προαπαιτούμενα
Διακριτά Μαθηματικά
Δομές Δεδομένων
Βιβλιογραφία
[1] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001.
[2] S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008.
[3] Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006.
[4] R. Sedgewick, Algorithms in C, Addison-Wesley, 2nd ed., 1998.
Διδάσκοντες
Νικόλαος Μισυρλής
Βαθμίδα: Καθηγητής
Τομέας: Θεωρητικής Πληροφορικής
Τμήμα: Πληροφορικής και Τηλεπικοινωνιών
Περισσότερες πληροφορίες
Η έννοια του αλγορίθμου και της πολυπλοκότητας. Πολυπλοκότητα κατά μέσο όρο και πολυπλοκότητα στη χείριστη περίπτωση. Σωροί, Heapsort. Τεχνικές σχεδίασης αλγορίθμων. Διαίρει και Βασίλευε: Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις, αλγόριθμοι ταξινόμησης, δυαδική αναζήτηση, το θεώρημα κυριαρχίας (master theorem), αναδρομικοί αριθμητικοί αλγόριθμοι, Στατιστικές κλίμακας, Πλησιέστερο ζεύγος σημείων. Union and find. Βασικοί αλγόριθμοι γραφημάτων: Οριζόντια διερεύνηση (BFS), καθοδική διερεύνηση (DFS), συνδεδεμένες συνιστώσες. Ομοαφετηριακές ελαφρύτατες διαδρομές (Dijkstra, Bellman-Ford). Τοπολογική Ταξινόμηση. Ελαφρύτατα συνδετικά δέντρα (Prim, Kruskal). Άπληστοι αλγόριθμοι: Γενική μορφή ενός άπληστου αλγορίθμου. Χρονοπρογραμματισμός διαστημάτων, το συνεχές πρόβλημα του σακιδίου (knapsack problem), κώδικες Huffman. Δυναμικός προγραμματισμός: Χρονοπρογραμματισμός γραμμής παραγωγής, πολλαπλασιασμός αλληλουχίας πινάκων, μέγιστη κοινή υπακολουθία, το διακριτό πρόβλημα του σακιδίου, τμηματοποιημένα ελάχιστα τετράγωνα.
Αναλύοντας τους αλγόριθμους στόχος μας είναι να διερευνήσουμε πως οι απαιτούμενοι για την εκτέλεσή τους πόροι, δηλαδή ο χρόνος και η μνήμη που χρησιμοποιούν, διακυμαίνονται με την αυξανόμενη διάσταση της εισόδου. Έτσι μπορούμε να αποτιμήσουμε την επίδοση ενός αλγορίθμου, να συγκρίνουμε δυο αλγόριθμους που επιλύουν το ίδιο πρόβλημα και να αναπτύξουμε έναν αποδοτικό αλγόριθμο για ένα πρόβλημα. Το ενδιαφέρον εστιάζεται στη κατανόηση ορισμένων βασικών τεχνικών σχεδίασης αλγορίθμων και στη διάκριση των προβλημάτων σε αυτά που θεωρούνται πρακτικώς επιλύσιμα και σε αυτά που θεωρούνται πρακτικώς δυσεπίλυτα.
- Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001.
- Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006.
- Dasgupta, C. H. Papadimitriou and U. V. Vazirani, Algorithms, MacGraw Hill, 2008.
Διακριτά Μαθηματικά
Δομές Δεδομένων
[1] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT-Press, 2001.
[2] S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008.
[3] Jon Kleinberg, Eva Tardos, Algorithm Design, Addison-Wesley, 2006.
[4] R. Sedgewick, Algorithms in C, Addison-Wesley, 2nd ed., 1998.
Νικόλαος Μισυρλής
Βαθμίδα: Καθηγητής
Τομέας: Θεωρητικής Πληροφορικής
Τμήμα: Πληροφορικής και Τηλεπικοινωνιών
Περισσότερες πληροφορίες
Ανάλυση αλγορίθμων, ασυμπτωτική πολυπλοκότητα, επαναληπτικοί αλγόριθμοι ταξινόμησης.
Λέξεις κλειδιά: Αλγόριθμος, πολυπλοκότητα, ασυμπτωτικός συμβολισμός, ταξινόμηση
Αναδρομικοί αλγόριθμοι ταξινόμησης, δυαδική αναζήτηση, οι πύργοι του Hanoi, εύρεση μεγίστου και ελαχίστου στοιχείου, αναδρομικοί αριθμητικοί αλγόριθμοι, στατιστικές κλίμακας, πλησιέστερο ζεύγος σημείων.
Λέξεις κλειδιά: Αναδρομικός αλγόριθμος, αναδρομικές εξισώσεις, ταξινόμηση, μικρότερο στοιχείο, Fibonacci, πολλαπλασιασμός ακεραίων, πολλαπλασιασμός πινάκων, Hanoi.
Στοιχειώδεις αλγόριθμοι γραφημάτων, ομοαφετηριακές ελαφρύτατες διαδρομές, ελαφρύτατα συνδετικά δέντρα.
Λέξεις κλειδιά: Οριζόντια διερεύνηση, καθοδική διερεύνηση, τοπολογική ταξινόμηση, συνδεδεμένες συνιστώσες, Dijkstra, Bellman-Ford, Kruskal, Prim.
Γενική μορφή ενός άπληστου αλγόριθμου, χρονοπρογραμματισμός διαστημάτων, το διακριτό πρόβλημα του Σακιδίου, το συνεχές πρόβλημα του Σακιδίου, κώδικες Huffman.
Λέξεις κλειδιά: Απληστία, άπληστη επιλογή, βέλτιστη υποδομή, αναδρομικός αλγόριθμος, σακίδιο, Huffman.
Χρονοπρογραμματισμός γραμμής παραγωγής, πολλαπλασιασμός αλληλουχίας πινάκων, μέγιστη κοινή υπακολουθία, το πρόβλημα του σακιδίου, τμηματοποιημένα ελάχιστα τετράγωνα.
Λέξεις κλειδιά: Βέλτιστη υποδομή, αναδρομικός αλγόριθμος, ανεξαρτησία υποπροβλημάτων, επικάλυψη υποπροβλημάτων, υπομνηματισμός, παρενθετική ομαδοποίηση, ελάχιστο πλήθος πολλαπλασιασμών, κοινή υπακολουθία, σακίδιο.
Επαναληπτικές ασκήσεις
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 0
Αρ. Προβολών : 0
Ημερολόγιο
Ανακοινώσεις
- - Δεν υπάρχουν ανακοινώσεις -
