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

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

Εισαγωγικές έννοιες: Αλγόριθμος, Στιγμιότυπο, Ανάλυση Αλγορίθμων.  Αναδρομή και μελέτη αναδρομικών αλγορίθμων.  Αλγόριθμοι ταξινόμησης,(Insertion-Sort, Merge-Sort, Quick-Sort, Heap-Sort και  οι πολυπλοκότητά τους). Εισαγωγή στην τεχνική σχεδίαση αλγορίθμων "διαίρει και κυρίευε". Αναδρομικές σχέσεις.   Σύγκριση αλγορίθμων ταξινόμησης.Ασυμπτωτικός συμβολισμός, Θ(.), Ο(.), Ω(.) ο(.) ω(.). 

Στοιχειώδεις αλγόριθμοι Γραφημάτων: Αναπαραστάσεις γράφων. Οι αλγόριθμοι BFS, DFS, Τοπολογική ταξινόμηση, Συνεκτικές  συνιστώσες, και Ισχυρά συνεκτικές συνστώσες.

Συντομότερες διαδρομές. Ο Αλγόριθμος του  Dijkstra, O Αλγόριθμος των   Bellman-Ford. 

Ελάχιστα συνδετικά δένδρα.  Οι Αλγόριθμοι  των Kruskal και Prim.

Βασικές Τεχνικές Σχεδίασης Αλγορίθμων: Διαίρει και κυρίευε, Απληστοι αλγόριθμοι, Δυναμικός προγραμματισμός.

Διαίρει και κυρίευε.  Πολλαπλασιασμός ακεραίων αριθμών. Το πρόβλημα της επιλογής

Απληστοι αλγόριθμοι. Εισαγωγή στους άπληστους αλγορίθμους. Το πρόβλημα της επιλογής δραστηριοτήτων. Κώδικας Huffman. 

Δυναμικός Προγραμματισμός,  Στοιχεία του δυναμικού προγραμματισμού.  Συντομότερες διαδρομές  σε Κατευθυνόμενα Ακυκλικά Γραφήματα. Μέγιστες αύξουσες υπακολουθίες, Το πρόβλημα του Σακιδίου. Πολλαπλασιασμός αλυσίδας πινάκων. Αλγόριμθμος του Floyd-Warshall.

Στοιχεία Υπολογιστικής Πολυπλοκότητας: Οι κλάσεις P, NP,  NP-πλήρη, NP-Δύσκολα.  NP-πλήρη προβλήματα και αναγωγές πολυωνυμικού χρόνου.

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

Πιθανοτικοί Αλγόριθμοι:Βασικές έννοιες πιθανοτικών αλγορίθμων και κλάσεις πολυπλοκότητας (RP, ...). Πιθανοτική εκδοχή της Γρήγορης Ταξινόμησης. 

Μέθοδοι αξιολόγησης

Τρόποι αξιολόγησης / εξέτασης:  Γραπτή εξέταση στο τέλος του εξαμήνου και εργασίες κατά  τη διάρκεια.

Ο Τελικός Bαθμός (ΤΒ) θα είναι ΤΒ = 70%ΒΓ + 30% ΒΑ  αν ΒΓ >= 5 , διαφορετικά ΤΒ = 70%ΒΓ,

όπου ΒΓ=Βαθμός Γραπτού, ΒΑ=Βαθμός Ασκήσεων(μέσος όρος των εργασιών).

Προτεινόμενα συγγράμματα

A1) Εισαγωγή στους Αλγορίθμους, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
A2) Αλγόριθμοι, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
A3) Σχεδιασμός Αλγορίθμων, , Jon Kleinberg, Eva Tardos
A4) Αλγόριθμοι Σχεδίαση και Εφαρμογές, Michael T. Goodrich, Roberto Tamassia

Περισσότερα

1) S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, McCraw-Hill, 2008.

2) G. J. E. Rawlings, Αλγόριθμοι: Ανάλυση και Σύγκριση. Εκδόσεις Κριτική, 2004.

3) T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press, 2001.

4) D. Kozen. The Design and Analysis of Algorithms. Springer, 1991.

6) A. Levitin. Ανάλυση και Σχεδίαση Αλγορίθμων. Εκδόσεις Τζιόλα, 2007.

7) Π. Μποζάνης, Αλγόριθμοι, Εκδόσεις Τζιόλα, Θεσσαλονίκη 2005.

Μαθησιακοί στόχοι

Ώρες γραφείου

Ώρες γραφείου κάθε Πέμπτη   και ώρες  12:00 - 14:00,  μετά από συνεννόηση μέσω email.