This course will be held in English.
We will study Markovian models and Queueing Systems to analyse the performance and reliability of computing systems. Examples can be many technical, real-life systems.
Material of this course is the book:
William Stewart. Probability, Markov Chains, Queues and Simulation. Princeton University Press 2009. The pdf file is in the resources of this course.
Dieser Kurs wird auf englisch gehalten.
Wir beschäftigen uns mit den grundlegenden stochastischen Modellen, die zur Untersuchung der Leistung von Computersystemen häufig benutzt werden. Markov modelle und Warteschlangen werden gerne für die Untersuchung dynamischer Systeme verwendet, z.B. Computer Hardware, Kommunicationsprotokolle, biologische Systeme, Epidemien, Verkehr und digitale Währungen. Wir werden uns einen raschen Überblick verschaffen. Betrachtete Themen sind der Geburts- und Todesprozess, der Poissonprozess, verallgemeinerte Markov und semi-Markov prozesse sowie deren Lösungsmethoden. Soweit die Zeit es erlaubt werden wir auch die Hintergründe der diskreten Ereignissimulation ansehen.
Literatur
William Stewart. Probability, Markov Chains, Queues and Simulation. Princeton University Press 2009.
Organisation
There will be discussion sessions (flipped classroom) every Tuesday, the first will be on Tuesday, 13.04.2021 at 10:15 at this meeting link:
https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=mf0d1b65761c19633fd65250e1add8729
Meeting number: 121 106 0043
Password: PRtCimMX637
On Thursday, 15.4.2021 from 12:15-13:45 there will be an extra Q&A session: https://fu-berlin.webex.com/meet/k.wolter
The tutorials will start on Thursday, 22.04.2021 and the meeting link is here: https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m385d511acbce32de94f647431aec932d
Meeting number: 121 165 7605
Password: jP7eSRR75pM
Lecture Materials:
All videos can be found in the nextcloud: https://nextcloud.imp.fu-berlin.de/index.php/s/6iao5DXJj87yXTn and in the vbrick server https://fu-berlin.eu.vbrickrev.com/#/ (search for Markov Chains). The following plan may still slightly change.
Week 1: (12.04.-16.04.2021) Introduction (slides in resources),
Lecture 1: Probability theory primer part 1 (video: https://fu-berlin.eu.vbrickrev.com/sharevideo/605ffac7-3de7-484f-a5dc-7500fd4cf58d or https://nextcloud.imp.fu-berlin.de/index.php/s/WFtGDZEgQYDxcPj, lecture notes in resources).
Lecture 2: Probability theory primer part 2, Moments, Generating Functions, Minimum and Maximum of RV (video1: https://fu-berlin.eu.vbrickrev.com/sharevideo/0e089345-ba47-400e-8ac5-f3e35662941a or https://nextcloud.imp.fu-berlin.de/index.php/s/MsMGYQeo2jyHQos , video2: https://fu-berlin.eu.vbrickrev.com/sharevideo/2493e910-cb71-4ef4-b765-fd7df2c527f3 or https://nextcloud.imp.fu-berlin.de/index.php/s/WbY5kHzEkXrZocR.
Week 2 (19.04.-23.04.2021):
Lecture 3: Discrete probability distributions https://fu-berlin.eu.vbrickrev.com/sharevideo/1d2133bb-ca5d-42c7-8427-c9e52dde7508 or https://nextcloud.imp.fu-berlin.de/index.php/s/64sgW86tXtft5pM
Lecture 4: Continuous probability distributions, reliability https://fu-berlin.eu.vbrickrev.com/sharevideo/76842793-36f8-46b1-a1a3-ac5cb5211056 or https://nextcloud.imp.fu-berlin.de/index.php/s/Nt27eKeZTTHWfZY
Part b: Phase-type distributions https://fu-berlin.eu.vbrickrev.com/sharevideo/7654dbd2-25a8-4d61-b9d3-7afc4b361ea7 or https://nextcloud.imp.fu-berlin.de/index.php/s/d5g78B96Qp5No9R
Week 3 (26.04.-30.04.2021):
Lecture 5: Bounds and limit theorems: https://fu-berlin.eu.vbrickrev.com/sharevideo/8b37bbfd-993c-4d6d-90a7-31d5cd534583 or https://nextcloud.imp.fu-berlin.de/index.php/s/ofyrtwTQ7g6MLn4
Lecture 6: Discrete time Markov chains https://fu-berlin.eu.vbrickrev.com/sharevideo/491d7c88-4eb9-43ce-ac5a-0c465bc67cc5 or https://nextcloud.imp.fu-berlin.de/index.php/s/27LR85BS29A32tJ
Week 4 (03.05.-07.05.2021):
Lecture 7: DTMCs, Sojourn times and embedded MCs https://fu-berlin.eu.vbrickrev.com/sharevideo/305636f9-7698-4994-b91e-cf5b238d9331 or https://nextcloud.imp.fu-berlin.de/index.php/s/w4k7dTT3qgzfczg
Lecture 8: DTMCs Classification of states https://fu-berlin.eu.vbrickrev.com/sharevideo/a74301da-bb72-4781-8bd7-076b60987e0f or https://nextcloud.imp.fu-berlin.de/index.php/s/EK8S8ySTB4P8twi
Week 5 (10.05-14.052021):
Lecture 9: DTMCs, Irreducibility, Potential and Fundamental matrix https://fu-berlin.eu.vbrickrev.com/sharevideo/fafba7ad-2061-4794-a743-387568f8620f or https://nextcloud.imp.fu-berlin.de/index.php/s/sDd7xzxHMAPoWQp
Lecture 10: Random Walk https://fu-berlin.eu.vbrickrev.com/sharevideo/080d549b-5b74-449a-90a6-a7aa4c9a1a23 or https://nextcloud.imp.fu-berlin.de/index.php/s/MEDn5Xa7zB9ZSkJ
Week 6 (17.05.-21.05.2021):
Lecture 11: Limiting and stationary distributions https://fu-berlin.eu.vbrickrev.com/sharevideo/4ca5c416-0719-4f42-b03a-280b0bdc9f03 or https://nextcloud.imp.fu-berlin.de/index.php/s/9nqJ8PdEQKr7mwi
Lecture 12: Reversibility https://fu-berlin.eu.vbrickrev.com/sharevideo/b81bcc98-97ad-4b8e-bc3f-d4d124e55603 or https://nextcloud.imp.fu-berlin.de/index.php/s/KjE5LQRsLb62fF3
Lecture 13: Page rank https://fu-berlin.eu.vbrickrev.com/sharevideo/e65fb743-fcfd-4f27-9098-f2624556993f or https://nextcloud.imp.fu-berlin.de/index.php/s/5FrkEn7WbsyG5BK
Week 7 (24.05.-28.05.2021):
Lecture 14: CTMCs https://fu-berlin.eu.vbrickrev.com/sharevideo/f4e314ae-26fe-47e0-b841-69c97b2ad23f or https://nextcloud.imp.fu-berlin.de/index.php/s/TJWyDYm64SeMsTf
Lecture 15: Renewal processes, PP, uniformisation, stochastic Petri nets https://fu-berlin.eu.vbrickrev.com/sharevideo/6d1cbc1b-9c6c-4791-a6e8-f91454b4e4e0 or https://nextcloud.imp.fu-berlin.de/index.php/s/n83bq9jyXcFAkcK
Week 8 (31.5.-04.06.2021):
Lecture 16:
Petri net tool PIPE2: https://fu-berlin.eu.vbrickrev.com/sharevideo/6ee2f5c1-4714-4bce-be27-2fe798cb5e03 or https://nextcloud.imp.fu-berlin.de/index.php/s/Ri7wFbiEsF5Fedm
Lecture 17: Basic queueing theory https://fu-berlin.eu.vbrickrev.com/sharevideo/bb1a2e24-6f6a-4497-82be-28a3d5d101ed or https://nextcloud.imp.fu-berlin.de/index.php/s/KWAKz62miegR5m4
Week 9 (07.06.- 11.06.2021):
Lecture 18: Basic queueing theory (Part 2) https://fu-berlin.eu.vbrickrev.com/sharevideo/dacb3026-0717-40e6-96e3-12c6f7aa4e37 https://nextcloud.imp.fu-berlin.de/index.php/s/RqNi3kjSqBb9BN5
Lecture 19: The M/M/1 queue https://fu-berlin.eu.vbrickrev.com/sharevideo/0a5911f9-0358-41e1-976b-d74e46a99525 or https://nextcloud.imp.fu-berlin.de/index.php/s/8ZgN3NHRjHRnf9k
Week 10 (14.06.-18.06.2021):
Lecture 20: The M/M/m queue https://fu-berlin.eu.vbrickrev.com/sharevideo/a0b7ef7b-19ec-4997-a8d3-5e5a06ce114c or https://nextcloud.imp.fu-berlin.de/index.php/s/NSCAF924786HH8L
Lecture 21: The M/M/m/K queue https://fu-berlin.eu.vbrickrev.com/sharevideo/c7495d8e-6c26-4c81-823c-08cc8aa8f799 or https://nextcloud.imp.fu-berlin.de/index.php/s/fpMwgD7qYnQQjcW
Week 11 (21.06.-25.06.2021):
Lecture 22: The M/G/1 queue https://fu-berlin.eu.vbrickrev.com/sharevideo/4a625125-ec14-40a2-9c59-b216c06b0e39 or https://nextcloud.imp.fu-berlin.de/index.php/s/qGPo3NYj3Gj6rTJ
Lecture 23: Open queueing networks https://fu-berlin.eu.vbrickrev.com/sharevideo/c0722e9e-6cef-43e4-8021-e9dd1fd50cc8 or https://nextcloud.imp.fu-berlin.de/index.php/s/q2gWwE9PAbZFYig
Week 12 (28.06.-02.07.2021):
Lecture 24 Closed Queueing Networks https://fu-berlin.eu.vbrickrev.com/sharevideo/0ce476d9-e232-46aa-ae72-ab444bd6a876 or https://nextcloud.imp.fu-berlin.de/index.php/s/EZay9cz9AP4NR4q
Week 13 (05.07.-09.07.2021):
Lecture 25 Mean Value Analysis https://fu-berlin.eu.vbrickrev.com/sharevideo/85154b64-1e4d-4f24-b63e-2a108ac3948c or https://nextcloud.imp.fu-berlin.de/index.php/s/e9MR6ft4HTMa692
Week 14 (12.07.-16.07.2021):
Exam