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

• Κ17 - Αλγόριθμοι και Πολυπλοκότητα

Στο μάθημα αυτό μελετώνται προβλήματα και αλγόριθμοι με σκοπό την εμπέδωση των βασικών αλλά και των πιο προχωρημένων τεχνικών σχεδίασης και ανάλυσης αλγορίθμων. Τα θέματα περιλαμβάνουν βασικούς αλγόριθμους για προβλήματα γράφων (graph problems) όπως προβλήματα χρωματισμού, το πρόβλημα του Χάμιλτον, το πρόβλημα του πλανόδιου πωλητή, και άλλα; προβλήματα ροών σε δίκτυα (network flows), προβλήματα ταιριάσματος (matching), προβλήματα αριθμητικής όπως ο Ταχύς Μετασχηματισμός Fourier (Fast Fourier Transform), γεωμετρικά προβλήματα. Μελετώνται ντετερμινιστικοί, πιθανοτικοί, προσεγγιστικοί αλγόριθμοι και οι κλάσεις πολυπλοκότητας P, NP, PSPACE. Το μάθημα απευθύνεται σε φοιτητές/ριες που έχουν βασικές γνώσεις ανάλυσης αλγορίθμων, για παράδειγμα από το μάθημα Αλγόριθμοι και Πολυπλοκότητα, και το κατάλληλο μαθηματικό υπόβαθρο.