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

Σωτήριος Νικολετσέας

Περιγραφή

Το μάθημα "ΠΙΘΑΝΟΤΙΚΕΣ ΤΕΧΝΙΚΕΣ" διδάσκεται στο Δ' έτος Σπουδών του Τμήματος, ως μάθημα επιλογής.

 

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

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

Ενότητες

The Method of Positive Probability
  • The Basic Method
  • Characteristics
  • Van der Waerden property
  • Ramsey Numbers
  • Coloring Hypergraphs
  • Tournaments

  • The Sk Property

Linearity of Expectation
  • Markov Inequality
  • Random Graph
  • Linearity of Expectation Method
  • Tournament with many Hamiltonian Cycles
  • Bipartite Subgraphs
The Deletion Method
  • Satisiability problem
  • Νon-existence proofs
  • Dominating sets in arbitrary graphs
  • The Deletion Method
  • Independent set in arbitrary graphs
The Second Moment Method
  • Variance
  • Chebyshev Inequality
  • The Second Moment Method
  • Covariance
  • The Basic Theorem
The Local Lemma
  • Importance of Stochastic Independence
  • Dependency Graph
  • The Lova?sz Local Lemma
  • Diagonal Ramsey Number
The Janson Inequality
  • The Janson Inequality
  • Triangle-free sparse Random Graphs
  • Paths of length 3 in Gn,p
Martingales
  • Martingales
  • Properties of martingales
  • Doob Martingale
  • The Edge Exposure Martingale
  • The Vertex Exposure Martingale
  • Azuma's inequality
  • Lipschitz condition
  • Chromatic number of a random graph

Ανοικτό Ακαδ. Μάθημα

Ανοικτά Ακαδημαϊκά Μαθήματα
Επίπεδο: A-

Αρ. Επισκέψεων :  8633
Αρ. Προβολών :  57214

Μεταδεδομένα μαθήματος

Ημερολόγιο

Προθεσμία
Γεγονός μαθήματος
Γεγονός συστήματος
Προσωπικό γεγονός

Ανακοινώσεις

περισσότερα…