Parameterized Complexity and Algorithms

Type
Elective
Course Description

Εισαγωγή στην παραμετρική πολυπλοκότητα, ισοδυναμίες μέτρων πολυπλοκότητας. Αλγοριθμικές τεχνικές: φραγμένα δέντρα αναζήτησης, επαναληπτική συμπίεση, άπληστος εντοπισμός, αναδρομική κατανόηση, σημαντικοί διαχωριστές, κανόνες αναγωγής, η τεχνική της ασήμαντης κορυφής. Πιθανοτικές μέθοδοι, πυρηνοποίηση, πυρηνοποίηση  Turing. Δεντροπλάτος, το θεώρημα του Courcelle, δυναμικός προγραμματισμός, διδιαστατότητα, εναλλακτικές παράμετροι πλάτους, παραμετρικές αναγωγές, μετααλγοριθμικά θεωρήματα. Οι κλάσεις para-NP και XP, η W-ιεραρχία: FPT, W[1],W[2],...,W[SAT], W[P] και ορισμοί της μέσω κυκλωμάτων, λογικών τύπων και μοντέλων μηχανών Turing. Κάτω φράγματα και υπόθεση εκθετικού χρόνου, ισχυρή υπόθεση εκθετικού χρόνου, παραμετρική πολυπλοκότητα πολυωνυμικά επιλύσιμων προβλημάτων.

Name Year Semester Taught by
Parameterized Complexity and Algorithms 2023-2024 Spring Giannos Stamoulis
Parameterized Complexity and Algorithms 2021-2022 Spring Archontia C. Giannopoulou
Parameterized Complexity and Algorithms 2020-2021 Spring Archontia C. Giannopoulou, Dimitris Zoros
Parameterized Complexity and Algorithms 2019-2020 Spring Archontia C. Giannopoulou
Parameterized Complexity and Algorithms 2017-2018 Spring Dimitris Zoros