Παραμετρική Πολυπλοκότητα και Αλγόριθμοι

Δημήτρης Ζώρος

Περιγραφή

 Η έναρξη των μαθημάτων θα γίνει την Δευτέρα 26 Φεβρουαρίου 2018.

 

Οι διαλέξεις θα γίνονται Δευτέρα 11:00-14:00 στην αίθουσα Α11 του Τμήματος Μαθηματικών του ΕΚΠΑ

 

Η ύλη του μαθήματος περιλαμβάνει τα παρακάτω:

  • Τεχνικές Σχεδιασμού Παραμετρικά Βατών Αλγορίθμων
  • Πυρηνοποίηση (Kernelization)
  • Φραγμένη Αναζήτηση σε Δέντρα (Bounded Search Tree)
  • Επαναλαμβανόμενη Συμπίεση (Iterative Compression)
  • Μέθοδοι Τυχαιοποίησης (Randomized Methods)
  • Δυναμικός Προγραμματισμός σε Γραφήματα Φραγμένου Δεντροπλάτους (Dynamic Programming on Graphs of Bounded Treewidth)
  • Σημαντικοί Διαχωριστές (Important Separators)
  • Πολυπλοκότητα και Κάτω Φράγματα
  • Αναγωγές (Reductions)
  • W-ιεραρχία (W-hierarchy)
  • W[1]-πλήρη και W[2]-πλήρη προβλήματα (W[1]-complete and W[2]-complete problems)
  • Υπόθεση Εκθετικού Χρόνου (Exponential Time Hypothesis)

  

Προτεινόμενη βιβλιογραφία

  1. Parameterized Algorithms, των Cygan et al.
  2. Fundamentals of Parameterized Complexity, των Downey και Fellows
  3. Invitation to Fixed-Parameter Algorithms, του Niederm
Περισσότερα  
Κωδικός: Μ.Π. Α.Λ.ΜΑ.
Σχολή - Τμήμα: Πληροφορικής και Τηλεπικοινωνιών » Μεταπτυχιακά Προγράμματα Σπουδών » ΔΠΜΣ Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά » 1 - Αλγόριθμοι και Υπολογιστική Πολυπλοκότητα

Ημερολόγιο

Ανακοινώσεις