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

() -  

Περιγραφή Μαθήματος

Οι διαλέξεις του μαθήματος θα γίνονται κάθε Τρίτη και Πέμπτη 18:00 - 20:00. Οι πρώτες διαλέξεις θα γίνουν δια ζώσης στην Αίθουσα Α11 του Τμήματος Μαθηματικών. Έπειτα οι διαλέξεις θα συνεχιστούν διαδικτυακά μέσω zoom (κατόπιν συνεννόησης/σχετικής ανακοίνωσης).

Η έναρξη των μαθημάτων θα γίνει την Τρίτη 18 Φεβρουαρίου 2025.

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

• Τεχνικές Σχεδίασης Παραμετρικά Βατών Αλγορίθμων

• Πυρηνοποίηση (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, του Niedermeier
4. Parameterized Complexity Theory, των Flum και Grohe
5. Kernelization,  των Fomin, Lokshtanov, Saurabh και Zehavi
6. Exact Exponential Algorithms, των Fomin και Kratsch

Ημερομηνία δημιουργίας

Κυριακή 21 Μαρτίου 2010