Μάθημα : Πιθανοτικές Τεχνικές και Τυχαιοκρατικοί Αλγόριθμοι

Η διδασκαλία του μαθήματος έχει ολοκληρωθεί και επομένως αύριο Δευτέρα 12/1/2026 δεν θα γίνει διάλεξη.

Στην ύλη της εξέτασης περιλαμβάνονται όλα τα slides των διαλέξεων και των φροντιστηρίων, ΕΚΤΟΣ από τα εξής slides τα οποία ΔΕΝ θα εξεταστούν:

- Lecture 1: slides 13-19
- όλο το Lecture 2
- Lecture 3: slides 8-11, 17-18
- Lecture 4: slides 4-9, 14-15

- όλο το Lecture 6
- Lecture 7: slides 10-14

- όλο το Lecture 8
- Lecture 10: slides 4-7, 28-32

- Lecture 11:  όλα είναι εκτός από μια συνοπτική περιγραφή του αλγόριθμου και των ιδιοτήτων του

- Lecture 12: η απόδειξη στα slides 8-12, η απόδειξη στα slides 15-16

Παρατηρήσεις:

• Πρέπει να μπορείτε να περιγράψετε συνοπτικά την βασική ιδέα κάθε πιθανοτικής τεχνικής και πώς χρησιμοποιείται (π.χ. «να περιγράψετε συνοπτικά την μέθοδο της γραμμικότητας της μέσης τιμής»)
• Δεν χρειάζεται να έχετε αποστηθίσει την ύλη, αλλά να έχετε καταλάβει τις αποδείξεις και να μπορείτε να εξηγήσετε ένα τμήμα της απόδειξης που θα σας δίνεται στην εκφώνηση.
• Θα ζητηθεί η λύση απλών ασκήσεων που ουσιαστικά έχουν διδαχθεί π.χ. τα σημεία του Gnp, ο βαθμός μιας κορυφής του, ο υπολογισμός μιας απλής συνάρτησης κατωφλίου, ο χρόνος σε κάποιο απλό random walk, η ευσταθής κατανομή μιας απλής μαρκοβιανής αλυσίδας.

Ο διδάσκων,

Σ. Νικολετσέας