Technische Universität Ilmenau

Randomisierte Algorithmen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Randomisierte Algorithmen im Studiengang Bachelor Informatik 2013
Modulnummer200079
Prüfungsnummer2200733
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusSommersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

Algorithmen und Datenstrukturen

Effiziente Algorithmen

Wahrscheinlichkeitsrechnung (Stochastik) für Informatiker

Lernergebnisse und erworbene Kompetenzen

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.

Inhalt

 

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

 

Medienformen

Folien, Tafel, schriftliche Ausarbeitung (Download auf Webseite), Übungsblätter

Literatur
  • Hromkovic, Randomisierte Algorithmen, Teubner

  • Motwani, Raghavan, Randomized Algorithms, Cambridge University Press

  • Mitzenmacher, Upfal, Probability and Computing, Cambridge University Press

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press (auch auf deutsch)

  • U. Schöning, "Algorithmik", Spektrum Akademischer Verlag, 2001 (Kapitel 12)

  • M. Dietzfelbinger, "Primality Testing in Polynomial Time", LNCS 3000, Springer-Verlag, 2004 (freier Zugang zur E-Version von Rechnern der Universität/Bibliothek)


Lehrevaluation