Vorlesung "Randomisierte Algorithmen", Wintersemester 2005/06

Eberhard Karls Universität Tübingen
Wilhelm-Schickard-Institut für Informatik (WSI)
Arbeitsbereich für Theoretische Informatik/Formale Sprachen

Impressum | Intern

Home | Lehre | Wintersemester 05/06 | Vorlesung Randomisierte Algorithmen | Java Applets

Java Applets "Randomisierte Algorithmen"

Im Rahmen der Übungen zur Vorlesung "Randomisierte Algorithmen" von Michael Kaufmann und Bernd Borchert im Wintersemester 2005/06 wurden von den Studenten Java-Applets zur Demonstration der in der Vorlesung besprochenen Algorithmen geschrieben.

Die Applets sollen dazu dienen, Studenten und Interessierten die randomisierten Algorithmen zu verdeutlichen. Der Anspruch der Applets ist, daß der Benutzer durch Lesen des Textes und Klicken im Applet das zu lösende Berechnungsproblem und das Prinzip des dazugehörigen randomisierten Algorithmus in kurzer Zeit versteht. Die Variationsmöglichkeiten für die Eingaben sind daher sehr eingeschränkt, sozusagen auf Spielzeug-Fälle. Auftretende Fehler (Rechtschreibfehler, unklare Formulierungen, inhaltliche und mathematische Fehler, Unklarheiten und Fehler in den Programmen) bitte per email an Bernd Borchert schicken, ebenso Verbesserungsvorschläge. Die probabilistische Analyse ist meistens schwieriger als der Algorithmus selber, deshalb wurden für einige Algorithmen von den Studenten - basierend auf der Vorlesungsmitschrift - jeweils probabilistische Abschätzungen geschrieben, in dem Fall sind sie unter dem Applet verlinkt. Geleitet wurden die Programmier-Übungen von Bernd Borchert. Besir Kadrioski stand den Studenten in Fragen zur Java Applet Programmierung zur Seite.

Thema	Beschreibung	Erfinder des Algorithmus	Autor des Applets	Vorlesung WS 05/06	Motwani/ Raghavan	Skript Niedermeier
von-Neumann Konstruktion	Gewichtete/ungewichtete 0/1-Zufallsfolge	von Neumann, 1946	Monika Kochanowski	21.10.05 Ü	25	--
Quicksort	Quicksort Sortier-Algorithmus	Hoare, 1962	A.Kullik, G. Arndt	21.10.05	3-7	11-13
MinCut	Randomisierter MinCut Algorithmus für Multigraphen	Karger, 1993	Geoffray Bonnin	10.11.05	7-9	--
Independent Set in Listen	Unabhängige Menge in Ring-Graphen		Anja Küster	3.11.05	--	--
Spielbaum-Auswertung	Auswertung von binären Spielbäumen	Saks & Wigderson, 1986	Stephan Kottler	4.11.05	36-37	14-15
Miller/Rabin Primzahltest	Implementierung des Miller/Rabin Primzahltests	Rabin & Miller, 1979	Christian Bender	10.11.05	425	23-27
Derandomisierung	Derandomisierung eines randomisierten Schaltkreises	Adleman,1978	Viola Brunner	10.11.05	38-40	--
Pattern Matching	Karp/Rabin Pattern-Matching Algorithmus	Karp & Rabin, 1987	Tim Frießinger	11.11.05	170-172	27-30
Rank-k-Selection	Suche nach dem k-größten Element einer Menge	Floyd & Rivest, 1975	Michael Betz	17.11.05	47-51	--
Set Balancing	Balancierte Aufteilung der Spalten einer 0/1-Matrix		Philip Effinger	18.11.05	73	--
Mesh Routing	Permutations-Routing im 2-dimensionalen Gitter		Bernd Schaffeld	24.11.05	--	--
Hypercube Routing	Permutations-Routing im 4-dimensionalen Hypercube	Valiant, 1982	Roland Minner	25.11.05	74-79	55-64
Global Wiring	Verdrahtungs-Problem, randomisiertes Runden	Raghavan & Thompson, 1987	Jonas Behr	2.12.05	79-83	--
Matrix Multiplikation	Überprüfung einer Matrix-Multiplikation	Freivalds, 1979	Philip Effinger	15.12.05	162-163	10-11
2-SAT	Randomisierter Algorithmus für 2-SAT	Papadimitriou, 1991	Bernd Lutz	22.12.05	128-129	16-17
Skip Lists	Randomisierte Datenstruktur Skip List	Pugh, 1990	Thomas Löffler	26.1.06	209-213	--

Die Angabe unter "Vorlesung WS05/06" stellt ca. den Termin dar, an dem der Algorithmus in der Vorlesung oder Übung behandelt wurde. Die Angaben unter "Motwani/Raghavan" und "Skript Niedermeier" stellen jeweils Seitenzahlen in dem Buch "Randomized Algorithms" von Motwani & Raghavan, 1995, bzw. in dem Skript von Rolf Niedermeier, 1997, dar.

Hier stehen alle 17 Applets auf einer Seite.

Für folgende in der Vorlesung besprochenen randomisierten Algorithmen wurden keine Applets geschrieben: Binäre planare Partitionen (31.10.2005), Stable Matching (18.11.05), MaxSAT (12.1.2006), k-SAT (19.1.2006), Independent Set (19.1.2006 Ü), Minimal Spanning Tree (26.1.2006), MaxCut (26.1.2006 Ü), Konvexe Hülle (2.2.2006), MiniDisk (2.2.2006), Lineare Programmierung (9.2.2006).

Letzte Änderung: 16. Aug. ‘06 | Bei Fragen und Anregungen E-Mail an: Bernd Borchert