Παραμετρική Πολυπλοκότητα και Αλγόριθμοι (ΠΜΣ Πληροφορικής και ΔΠΜΣ Α.Λ.ΜΑ.) (M223)

Αρχοντία Γιαννοπούλου

Περιγραφή

 Η έναρξη των μαθημάτων θα γίνει την Παρασκευή 28 Φεβρουαρίου 2018 (καθώς η 21/2 είναι επίσημη αργία του ΕΚΠΑ).

 

Οι διαλέξεις θα γίνονται Παρασκευή 12:00-15:00 στην αίθουσα Β του Τμήματος Πληροφορικής και Τηλεπικοινωνιών του ΕΚΠΑ (και θα ξεκινάνε αυστηρά στις 12:00).

 

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

  • Τεχνικές Σχεδιασμού Παραμετρικά Βατών Αλγορίθμων
  • Πυρηνοποίηση (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)

 

Για την επιτυχή παρακολούθηση του μαθήματος συνιστάται οι φοιτητές να είναι

Περισσότερα  

Ημερολόγιο

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