VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-0467-00L 4 Credits

Pseudozufälligkeit und Derandomisierung

Lecturers: Prof. Dr. Markus Bläser
VVZ CR n/a

Last Updated: 2026-02-05 14:55:11

Abstract

Heranfuehrung an den aktuellen Stand der Wissenschaft im Bereich Pseudozufaelligkeit undDerandomisierung durch das Studium aktueller wissenschaftlicher Originalarbeiten

Objective

Heranfuehrung an den aktuellen Stand der Wissenschaft im Bereich Pseudozufaelligkeit und Derandomisierung

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

Lecture Notes

---

Literature

Diverse Originalarbeiten

General Information

Language
German
Frequency
Yearly recurring

Examination

Type
session examination
Mode
oral 30 minutes

Course Components

Type Title Time & Place Hours
seminar Pseudozufälligket und Derandomisierung
  • Mon 14:15-16:00 (IFW E 42)
2 h weekly

Offered In