VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Pseudozufälligkeit und Derandomisierung
Last Updated: 2026-02-05 14:57:22
Content
Randomisierung spielt eine wichtige Rolle im Entwurf von Algorithmen. Die Attraktivität von randomisierten Algorithmen basiert typischerweise auf zwei Eigenschaften: einfache Implementierung sowie gute Laufzeiten. Die meisten randomisierten Algorithmen machen Gebrauch von perfekten Zufallsbits, die in der Praxis meist nicht zur Verfügung stehen. Dennoch funktionieren randomisierte Algorithmen auch in der Praxis gut. Gibt es hierfür eine Erklärung? Kann man aus "schlechten" Zufallsbits "gute" Zufallsbits gewinnen? Oder ganz auf den Zufall verzichten? Die Vorlesung zielt nicht darauf ab, einzelne Algorithmen zu derandomisieren. Im Vordergrund stehen vielmehr komplexitäts-theoretische Aspekte, also die Derandomisierung ganzer Problemklassen. Wichtige Werkzeuge dabei sind Pseudozufallsgeneratoren, Extraktoren, Expandergraphen und fehlerkorrigierende Codes.
Resources
Literature
Wird noch bekannt gegeben.
General Information
- Language
- German
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 30 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Pseudozufälligkeit und Derandomisierung |
|
2 h weekly |
| exercise | Pseudozufälligkeit und Derandomisierung |
|
1 h weekly |