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

Στόχοι Μαθήματος

Η Πιθανοτική Μέθοδος (The Probabilistic Method) έχει πρόσφατα αναπτυχθεί ραγδαία και αποτελεί ήδη ένα από τα πλέον ισχυρά εργαλεία της Συνδυαστικής. Ο μείζων λόγος αυτής της ταχείας ανάπτυξης της μεθόδου είναι ο σημαντικότατος ρόλος τον οποίο διαδραματίζει η χρήση της τυχαιότητας (randomness) στις Θεμελιώσεις της Επιστήμης του Υπολογισμού. Η βασική ιδέα της Μεθόδου είναι η εξής: Για να αποδείξουμε την ύπαρξη μιας συνδυαστικής δομής που ικανοποιεί ορισμένες επιθυμητές ιδιότητες, κατασκευάζουμε έναν κατάλληλο πιθανοτικό δειγματοχώρο και αποδεικνύουμε ότι ένα τυχαία επιλεγόμενο μέλος αυτού του δειγματοχώρου ικανοποιεί αυτές τις επιθυμητές ιδιότητες με θετική (μη μηδενική) πιθανότητα.

Προαπαιτούμενες Γνώσεις

Πιθανότητες, Αλγόριθμοι

Περιεχόμενα

Η μέθοδος της θετικής πιθανότητας. Η γραμμικότητα της μέσης τιμής. Παραλλαγές των βασικών μεθόδων. Η μέθοδος της δεύτερης ροπής. Το Τοπικό Θεώρημα. Η ανισότητα του Janson. Η μέθοδος των ακολουθιών διατήρησης. Τυχαίοι περίπατοι και μαρκοβιανές αλυσίδες. Φράγματα Chernoff.