Randomized Algorithms - Interactive curriculae of TU Ilmenau
The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.
Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).
You can find all details on planned lectures and classes in the course catalogue.
Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.
| module properties module number 200079 - common information | ||
|---|---|---|
| module number | 200079 | |
| department | Department of Computer Science and Automation | |
| ID of group | 2242 (Algorithms) | |
| module leader | Prof. Dr. Martin Dietzfelbinger | |
| language | Deutsch | |
| term | Sommersemester | |
| previous knowledge and experience | Algorithmen und Datenstrukturen Effiziente Algorithmen Wahrscheinlichkeitsrechnung (Stochastik) für Informatiker | |
| learning outcome | Die Studierenden verstehen das Konzept eines randomisierten Algorithmus, seine präzise technische Interpretation und seine praktische Relevanz. Sie können Algorithmen nach ihren Grundeigenschaften klassifizieren und können die jeweiligen Wahrscheinlichkeitsverbesserungstechniken anwenden. Die Studierenden kennen wesentliche wahrscheinlichkeitstheoretische Techniken und können sie bei der Analyse randomisierter Algorithmen einsetzen. Die Studierenden kennen das Konzept "sparsame Verwendung von Zufallsbits" und kennen Techniken zur Erzeugung von analysierbaren Pseudozufallszahlen-Folgen. Die Studierenden verstehen die zahlentheoretischen Hintergründe des randomisierten Primzahltests nach Miller/Rabin, seine Funktionsweise und den Zeitbedarf. Sie wissen, wie Primzahltests bei der Erzeugung zufälliger Primzahlen einzusetzen sind. Schließlich kennen sie die Technik des Satzes von Schwartz und Zippel bei Identitätstests von algebraisch definierten Objekten und können diese Technik in verschiedenen Situationen anwenden. Sozialkompetenz: Selbst in der Vorlesung ist Interaktion stets möglich, ja erwünscht, darin sind die Studierenden geübt.
Die Studierenden konnten die Erfahrung machen, dass Fragen unmittelbar geklärt
werden, dass Diskussionen auf Augenhöhe stattfinden und Beiträge
wertschätzend aufgenommen werden. In der Übung waren die Studierenden zu
Präsentationen aufgerufen. Sie konnten wertvolle Erfahrung in der Rolle
des Präsentierenden sammeln. | |
| content |
Algorithmen, die Zufallsexperimente durchführen
Wahrscheinlichkeitstheoretische Grundlagen
Modellierung randomisierter Algorithmen, Typen, Wahrscheinlichkeitsverbesserung
Randomisierte Suchverfahren
Randomisierte Algorithmen für zahlentheoretische Probleme
Randomisierte Algorithmen für algebraische Probleme mit Anwendungen
| |
| media of instruction and technical requirements for education and examination in case of online participation | Folien, Tafel, schriftliche Ausarbeitung (Download auf Webseite), Übungsblätter | |
| literature / references |
| |
| evaluation of teaching | ||
| Details reference subject | |
|---|---|
| module name | Randomized Algorithms |
| examination number | 2200733 |
| credit points | 5 |
| SWS | 4 (3 V, 1 Ü, 0 P) |
| on-campus program (h) | 45 |
| self-study (h) | 105 |
| obligation | obligatory module |
| exam | oral examination performance, 30 minutes |
| details of the certificate | |
| link to Moodle course | |
| teacher | |
| signup details for alternative examinations | |
| maximum number of participants | |
| Details in degree program Bachelor Informatik 2013 | |
|---|---|
| module name | Randomized Algorithms |
| examination number | 2200733 |
| credit points | 5 |
| on-campus program (h) | 45 |
| self-study (h) | 105 |
| obligation | elective module |
| exam | oral examination performance, 30 minutes |
| details of the certificate | |
| link to Moodle course | |
| signup details for alternative examinations | |
| maximum number of participants | |