Γενικές Πληροφορίες

Ώρες Μαθήματος:

Δευτέρα
Τετάρτη
13:00-15:00, ΡΑ 105
13:00-15:00, ΡΑ 103

Διδάσκων:

Μενέλαος Καραβέλας
Γραφείο: Θ-308Γ
Τηλέφωνο: 2810 393 706
email: mkaravel at tem uoc gr

Διδακτικό Υλικό:

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, McGraw Hill, 2nd edition, 2001.
  • M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.

Αντικείμενο Μαθήματος:

Χρονική και χωρική πολυπλοκότητα αλγορίθμων. Δυναμικός προγραμματισμός. Τεχνική του «διαίρει και βασίλευε». «Άπληστοι» αλγόριθμοι. Παραδείγματα. Αλγόριθμοι και πολυπλοκότητα των παρακάτω: Αλγόριθμοι αναζήτησης και ταξινόμησης (Δυαδική αναζήτηση, Bubble Sort, Merge Sort). Αλγόριθμοι σε γραφήματα (Ελάχιστα μονοπάτια, Ελάχιστο δένδρο κάλυψης). Αριθμοθεωρητικοί αλγόριθμοι (Ευκλείδιος αλγόριθμος, αλγόριθμος κινέζικου θεωρήματος, αλγόριθμοι γρήγορης αριθμητικής).
Οι κλάσεις προβλημάτων P και NP. Αναγωγές πολυωνυμικού χρόνου. Πληρότητα ως προς μια κλάση. Βασικά NP-πλήρη προβλήματα (SAT, Clique, Hamilton Path, knapsack, subset sum).

Σχετική Βιβλιογραφία:

  • A. Levitin. The Design and Analysis of Algorithms, Addison-Wesley, 2003
  • A. V. Aho, J. D. Ullman and J. E. Hopcroft. Data Structures and Algorithms, Addison-Wesley, 1983.
  • C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Dover, 1998.
  • R. Motwani and P. Raghavan. Randomized Algorithms, Cambridge University Press, 1995.
  • M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 2nd Edition, 1997.
  • R. Sedgewick. Algorithms in C++, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, Addison-Wesley, 3rd edition, 2001.
  • V. V. Vazirani. Approximation Algorithms, Springer, 2004.