Πιθανοτικοί Αλγόριθμοι (Μ173)

Θα σχεδιάσουμε και μελετήσουμε αλγορίθμους οι οποίοι χρησιμοποιούν τυχαιότητα, όπως για παράδειγμα όταν κουνάμε ένα κόσκινο προκειμένου να υπολογίσουμε το κατηγόρημα "χωράει να περάσει από καποια τρύπα του κόσκινου" για ένα σύνολο από αντικείμενα, γνωρίζοντας πως ο αλγόριθμος μας κάνει λάθος μόνο προς τη μία κατεύθυνση (για κάποια αντικείμενα για τα οποία η απάντηση είναι "ναι" υπολογίζουμε "όχι", αλλά ποτέ το αντίθετο).

Πέρα από το αλγοριθμικό κομμάτι θα υπάρχουν και στοιχεία ανάλυσης αλυσίδων Markov και κάποια στοιχεία ανάλυσης τυχαιών δομών, π.χ. τυχαίων γραφημάτων. 

Το μάθημα δεν προϋποθέτει γνώσεις πιθανοτήτων (ότι χρειάζεται θα διδαχτεί).

Η τελική αξιολόγηση θα γίνει μέσα από κάποια εργασία ή/και παρουσίαση (όχι εξέταση).