Preview

(CEID1082) -  Σωτήριος Νικολετσέας

Description du cours

Το μάθημα "Πιθανοτικές Τεχνικές και Τυχαιοκρατικοί Αλγόριθμοι" αποτελεί μάθημα επιλογής. Ανήκει στα μαθήματα Ομάδας Α ("βασικά επιλογής") για την κατεύθυνση Κ1: "Αλγοριθμικές Θεμελιώσεις και Ευφυής Υπολογιστική" .

 

Το μάθημα αποσκοπεί στην διδασκαλία επιλεγμένων πιθανοτικών τεχνικών, που αποτελούν ισχυρό εργαλείο για την μελέτη τυχαίων γραφημάτων (random graphs) ως i) μοντέλων δικτύων (networks) και ii) εισόδων (inputs) για την ανάλυση μέσης τιμής αλγορίθμων (average case analysis). Επίσης, το μάθημα περιλαμβάνει τον σχεδιασμό και την ανάλυση πιθανοτικών αλγορίθμων  (randomized algorithms).

 

Από το έτος 2025-2026 θα υπάρχει μεγαλύτερη έμφαση σε πιθανοτικούς αλγόριθμους. Επίσης, θα διδαχθούν στοιχεία πολύπλοκων δικτύων (complex networks), τα οποία θεωρούνται ακόμη πιο ρεαλιστικά μοντέλα πολλών σύγχρονων δικτύων (υπολογιστικών, κοινωνικών, βιολογικών κ.λπ.).

 

Η ύλη του μαθήματος περιλαμβάνει:

• Η μέθοδος της θετικής πιθανότητας.
• Η γραμμικότητα της μέσης τιμής.
• Η μέθοδος της δεύτερης ροπής.
• Το τοπικό θεώρημα.
• Η ανισότητα του Janson.
• Μαρκοβιανές αλυσίδες.
• Τυχαίοι περίπατοι σε γραφήματα
• Πιθανοτικοί αλγόριθμοι - Minimum Cut
• Πιθανοτικοί αλγόριθμοι - Lazy Select
• Πολύπλοκα δίκτυα (ιδιότητες power law, small words, scale-free)

Creation Date

lundi 8 décembre 2014