Παρουσίαση/Προβολή

Περιεχόμενο μαθήματος

Η έννοια του αλγορίθμου και της πολυπλοκότητας. Πολυπλοκότητα κατά μέσο όρο και πολυπλοκότητα στη χείριστη περίπτωση. Σωροί, 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.

Διδάσκοντες

Νικόλαος Μισυρλής

Βαθμίδα: Καθηγητής
Τομέας: Θεωρητικής Πληροφορικής
Τμήμα: Πληροφορικής και Τηλεπικοινωνιών

Περισσότερες πληροφορίες