Randomisierte Algorithmen (RAND)7.5 ECTS
(englische Bezeichnung: Randomized Algorithms)
(Prüfungsordnungsmodul: Vertiefungsmodul Theoretische Informatik)

Lehrveranstaltungen:

• • Randomisierte Algorithmen
    (Vorlesung, 2 SWS, Rolf Wanka, Do, 10:15 - 11:45, E 1.11)
  • Übungen zu Randomisierte Algorithmen
    (Übung, 2 SWS, Alexander Raß, Di, 14:15 - 15:45, E 1.11)

Inhalt:

Bei der Lösung kombinatorischer oder zahlentheoretischer Probleme ist es oft möglich, durch Würfeln schnell und einfach mit hoher Wahrscheinklichkeit oder im Durchschnitt zu hervorragenden Lösungen zu kommen. In diesem Modul lernen wir Konzepte wie die Probabilistische Methode, Irrläufe (Random Walks) und Varianzanalysen von Zufallsprozessen kennen und wenden sie auf graphentheoretische Probleme und effiziente Datenstrukturen an. Zu den vorgestellten Inhalten gehören:

• Schnelle Wiederholung wahrscheinlichkeitstheoretischer Begriffe und Resultate

• Die Probabilistische Methode und ihre Anwendung auf die Berechnung maximaler Schnitte und unabhängiger Mengen

• Random Walks und ihre Anwendung auf das Erfüllbarkeitsproblem
  

Neueste Ergebnisse dieses Forschungsgebietes werden inhaltlich in das Modul eingebunden.

Lernziele und Kompetenzen:

Wissen

Lernende können Wissen abrufen und wiedergeben. Sie kennen konkrete Einzelheiten wie Begriffe, Definitionen, Regeln, Gesetzmäßigkeiten, Theorien.

Verstehen

Lernende können Beispiele anführen, Aufgabenstellungen interpretieren oder ein Problem in eigenen Worten wiedergeben.

Anwenden

Lernende können ein neues Problem durch Transfer des Wissens lösen.

Analysieren

Lernende können ein Problem in einzelne Teile zerlegen und so die Struktur des Problems verstehen; sie können Zusammenhänge erkennen und Folgerungen ableiten

Weitere Informationen:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Mathematik (Bachelor of Science)
   (Po-Vers. 2015w | Bachelorprüfung | Nebenfach Informatik | Vertiefungsmodule | Vertiefungsmodul Theoretische Informatik)

Studien-/Prüfungsleistungen:

Randomisierte Algorithmen (Vorlesung mit Übung) (Prüfungsnummer: 164985)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: SS 2015, 1. Wdh.: WS 2015/2016, 2. Wdh.: keine Wiederholung

1. Prüfer:

Rolf Wanka