Προηγμένα Θέματα Αλγορίθμων

Εξάμηνο:
6ο
Τύπος Μαθήματος:
Προαιρετικό Μάθημα (ΠΜ)
Κατεύθυνση:
Α
Κωδικός:
ΘΠ12
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (Ε1):
(E) Επιλογής
Διαχείριση Δεδομένων και Γνώσης (Ε2):
-
Λογισμικό (Ε3):
-
Υλικό και Αρχιτεκτονική (Ε4):
-
Επικοινωνίες και Δικτύωση (Ε5):
-
Επεξεργασία Σήματος και Πληροφορίας (Ε6):
-
Σχετικά Μαθήματα
Περιγραφή Μαθήματος

Προσεγγιστικοί αλγόριθμοι: Άπληστοι αλγόριθμοι, Η μέθοδος της τιμολόγησης, Η μέθοδος γραμμικού προγραμματισμού και στρογγυλοποίησης, Προσεγγιστικά σχήματα πολυωνυμικού χρόνου. Τυχαιοποιημένοι αλγόριθμοι: Αλγόριθμοι Monte Carlo, Αλγόριθμοι Las Vegas, Τυχαιοποιημένο διαίρει και βασίλευε. Παραμετρικοί αλγόριθμοι: Φραγμένα δέντρα αναζήτησης, Πυρηνοποίηση, Επαναληπτική συμπίεση. Άμεσοι αλγόριθμοι: Εισαγωγικά προβλήματα, Αλγόριθμοι σήμανσης

Βιβλιογραφία
  • Kleinberg Jon, Tardos Eva: Σχεδιασμός Αλγορίθμων, Εκδόσεις Κλειδάριθμος 2008
  • Cormen Thomas H., Leiserson Charles E., Rivest Ronald, Stein Clifford: Εισαγωγή στους Αλγορίθμους, Πανεπιστημιακές Εκδόσεις Κρήτης 2016
  • Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh: Parameterized Algorithms, Springer 2015
  • Vijay V. Vazirani: Approximation Algorithms, Springer 2001
  • David P. Williamson, David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press 2011
  • Michael Mitzenmacher, Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press 2005
  • Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press 2006
  • Allan Borodin, Ran El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press 1998
  • Christos H. Papadimitriou: Computational Complexity, Addison-Wesley 1993