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

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

Κωδικός:
Εξάμηνο:
Κατηγορία:
Ροή:

ICE-3001
3ο
Υποχρεωτικό (Y)

Ώρες:
Διδάσκοντες:
Σύνδεσμοι:

2 Θ – 2 ΑΠ/Φ
Δημήτριος Μάγος (ΔΕΠ)

Περιγραφή

Προβλήματα και στιγμιότυπα. Μοντέλο υπολογισμού RAM και υπολογιστικοί πόροι – ιδιότητες αλγορίθμων και συγκριτική ανάλυση. Αλγόριθμοι και συναρτήσεις: κλάσεις συναρτήσεων και ιεραρχίες – διάταξη συναρτήσεων. Αναδρομικές συναρτήσεις και επίλυση τους – μέθοδος αντικατάστασης, δένδρου αναδρομής και μαθηματικής επαγωγής, κεντρικό θεώρημα (master theorem). Εφαρμογές της ανάλυσης αναδρομικών συναρτήσεων σε αλγόριθμους τύπου «διαίρει-και-βασίλευε». Δυναμικός προγραμματισμός- αρχή του Bellman, η τεχνική memoization. Εφαρμογές δυναμικού προγραμματισμού και ανάπτυξη και ανάλυση αλγορίθμων τέτοιου τύπου., ομοιότητες και διαφορές με απλά αναδρομικά σχήματα. Γραφήματα: βασικές έννοιες και θεωρήματα. Αναπαραστάσεις γραφημάτων σε Η/Υ. Προβλήματα σε γραφήματα, αλγόριθμοι και η ανάλυση τους.  

Μοντέλα υπολογισμού: αυτόματα, η μηχανή Turing και προβλήματα απόφασης. Ντετερμινιστικός και μη-ντετερμινιστικός  υπολογισμός. Βασικές κλάσεις προβλημάτων – ιεραρχίες πολυπλοκότητας: μη-επιλύσιμα προβλήματα, P, NP, NP-πλήρες, NP-hard, co-NP.  Συναρτησιακή και πολυωνυμική αναγωγή και εφαρμογές της: πρόβλημα SAT και παραλλαγές του, πρόβλημα Clique, ανεξαρτήτου συνόλου, κάλυψης κόμβων, πρόβλημα Χαμιλτονιανού μονοπατιού, κλπ. Προβλήματα βελτιστοποίησης και εισαγωγή σε αλγόριθμους εγγυημένης απόδοσης.