|
Randomisierte Algorithmen (RAND)7.5 ECTS (englische Bezeichnung: Randomized Algorithms)
Modulverantwortliche/r: Rolf Wanka Lehrende:
Rolf Wanka
Start semester: |
SS 2021 | Duration: |
1 semester | Cycle: |
jährlich (SS) |
Präsenzzeit: |
60 Std. | Eigenstudium: |
165 Std. | Language: |
Deutsch oder Englisch |
Lectures:
-
-
Randomisierte Algorithmen
(Vorlesung, 2 SWS, Rolf Wanka, Tue, 08:15 - 09:45, 01.150-128)
-
Übungen zu Randomisierte Algorithmen
(Übung, 2 SWS, Matthias Kergaßner, Wed, 14:15 - 15:45, 01.150-128)
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:
www: https://www.cs12.tf.fau.de/lehre/lehrveranstaltungen/vorlesungen/randomisierte-algorithmen/
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- 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)
- 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)
- Informatik (Bachelor of Science)
(Po-Vers. 2009s | TechFak | Informatik (Bachelor of Science) | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
- Informatik (Bachelor of Science)
(Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
- 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)
- Mathematik (Bachelor of Science)
(Po-Vers. | NatFak | Mathematik (Bachelor of Science) | Module des Nebenfachs | Nebenfach Informatik | Vertiefungsmodule | Vertiefungsrichtung Theoretische Informatik | Randomisierte Algorithmen)
- 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:
Die Prüfungssprache ist abhängig von der Wahl der Studierenden.
- Prüfungssprache: Deutsch oder Englisch
- Erstablegung: SS 2021, 1. Wdh.: WS 2021/2022, 2. Wdh.: keine Wiederholung
- Ort: Seminarraum 02.112-128, Cauerstr. 11, 91058 Erlangen
|
|
|