Randomisierte Algorithmen (RAND)7.5 ECTS
(englische Bezeichnung: Randomized Algorithms)

Lehrveranstaltungen:

• • Randomisierte Algorithmen
    (Vorlesung, 2 SWS, Rolf Wanka, Di, 14:15 - 15:45, 01.150-128)
  • Übungen zu Randomisierte Algorithmen
    (Übung, 2 SWS, Alexander Raß, Fr, 12:15 - 13:45, 02.133-113)

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:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Informatik (Bachelor of Arts (2 Fächer))
   (Po-Vers. 2010 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | Vertiefung Informatik I und II | Vertiefungsmodul Theoretische Informatik | Randomisierte Algorithmen)
2. Informatik (Bachelor of Arts (2 Fächer))
   (Po-Vers. 2013 | TechFak | Informatik (Bachelor of Arts (2 Fächer)) | Vertiefung Informatik I und II | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
3. Informatik (Bachelor of Science)
   (Po-Vers. 2009s | TechFak | Informatik (Bachelor of Science) | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
4. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
5. Informatik (Master of Science)
   (Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Gesamtkonto | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
6. Mathematik (Bachelor of Science)
   (Po-Vers. | NatFak | Mathematik (Bachelor of Science) | Module des Nebenfachs | Nebenfach Informatik | Vertiefungsmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
7. Mathematik (Bachelor of Science)
   (Po-Vers. 2019w | NatFak | Mathematik (Bachelor of Science) | weitere Module der Bachelorprüfung | Module des Nebenfachs | Nebenfach Informatik | Vertiefungsmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)

Studien-/Prüfungsleistungen:

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

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

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:
gemäß Corona-Satzung wird als alternative Prüfungsform festgelegt: digitale mündliche Distanzprüfung mit 30 Minuten Dauer

Erstablegung: SS 2020, 1. Wdh.: WS 2020/2021, 2. Wdh.: keine Wiederholung

1. Prüfer:

Rolf Wanka

Ort: Seminarraum 02.112-128, Cauerstr. 11, 91058 Erlangen