Effiziente Algorithmen
Grundstudium
SS 2006
Vorlesung: Di, 9-11, Do, 13-15, Prof. Martin Hofmann
Übung: Mo, 14-16, Mi, 14-16, 16-18, Do 11-13, Andreas Abel, Stefan Schimanski und Team
Schein: ja
SWS: 4 Vorlesung + 2 Übung
Klausur: 25.7.2006, 11-13, B051+B052 Theresienstraße
Aktuelles
- Scheine und Klausurrckgabe ebenfalls in der �ung und in der Vorlesung
- Die Klausur wird Donnerstag in der �ung vorgerechnet!
- Es wird keine Wiederholungsklausur geben, aber folgende Härtefallregelung:
Solchen Kandidaten, die aus triftigen Gründen nicht in der Lage sind, im nächsten Sommersemester die Vorlesung nochmal zu machen und die außerdem auf den Schein angewiesen sind, wird eine mündliche Nachprüfung angeboten. Diese besteht dann aus zwei bis drei Aufgaben in der Art und Schwierigkeit der Klausuraufgaben. Sie wird voraussichtlich am 12.9.06 ab 14:00 stattfinden. Jede/r, die/der meint, diese Regelung trifft auf ihn/sie zu, melde sich bitte per Email oder persönlich.
- Folgende Studenten haben die Klausur bestanden (ohne Gew�r!)
128301381
2221482
2231408
2231893
2241679
2246988
2252955
2253426
2256706
2264882
2267720
2269706
2271208
2286684
2289076
2556732
38300962
87906911
97907464
- Der aktuelle Foliensatz zur Vorlesung ist nunmehr zum Zwecke der Klausurvorbereitung online vorhanden.
- Folgende Studenten sind fr die Klausur zugelassen. Falls jemand seine Matrikelnummer vermisst, aber zugelassen sein sollte, bitte melden.
128301381
2221482
2228763
2231408
2231501
2231893
2232294
2238356
2241378
2241679
2246988
2251878
2252955
2253426
2256706
2261174
2264882
2266267
2267720
2268328
2268737
2269706
2270614
2271208
2286684
2289076
2556732
38106516
38300962
67806979
87906911
88006639
88204571
97907464
98104645
- Beweise und Hilfssaetze zur Tiefensuche.
- Blatt 5 muss erst am Mittwoch, 7. Juni abgegeben werden. (Pfingstmontag ist Feiertag.)
- Nicolas Rachinsky wies auf eine inzwischen behobene Sicherheitsluecke (DoS) bei Linux hin, die auf unsachgemaesse Verwendung von Hashtabellen zurueckzufuehren war.
- Ein Java-Applet zum interaktiven Bauen von Rot-Schwarz-B�men gibt es hier.
- Eine Zusammenfassung von Rot-Schwarzb�men ist online.
Organisatorisches
|
| Tag
| Zeit
| Ort
| Beginn
| Dozent
|
|---|
| Vorlesung
| Di
| 11:15 - 12:45
| E27 (Theresienstr. 39)
| 25.04.06
| Martin Hofmann
|
|---|
|
| Do
| 13.15 - 14:45
| 138 (Theresienstr. 39)
| 27.04.06
|
|
|---|
| Übung
| Mo
| 14.15 - 16.00
| .23 (Oettingenstr. 67)
| 08.05.06
| Nicolas Rachinsky (email: rachinsk cip ifi lmu de)
|
|---|
|
| Mi
| 14.00 - 15.30
| .23 (Oettingenstr. 67)
| 03.05.06
| Jan Hoffmann (email: hoffmann cip ifi lmu de)
|
|---|
|
| Mi
| 16.15 - 18.00
| 0.33 (Oettingenstr. 67)
| 03.05.06
| Andreas Abel
|
|---|
|
| Do
| 11.00 - 12.30
| 1.43 (Oettingenstr. 67)
| 11.05.06
| Stefan Schimanski
|
|---|
| Klausur
| 25.7.
| 11.00 - 13.00
| B051+B052 (Theresienstr. 39)
|
|
|
|---|
| Für
| Studierende der Informatik im Grundstudium
|
|---|
| Vorkenntnisse
| Grundkenntnisse in Informatik |
|
|---|
| Schein
| gilt für Diplomvorprüfung im Haupt- oder Nebenfach Informatik |
|
|---|
| Scheinerwerb
| mind. 50% der �ungspunkte. Weiteres wird noch bekanntgegeben.
|
|---|
|
|
|
|
|---|
Inhalt
Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen
ein, welche in fast allen Gebieten der Informatik und verwandten
Disziplinen Anwendung finden.
Wir lehnen uns eng an das Lehrbuch von Cormen
et al. an, das in mehreren Präsenzexemplaren in der Bibliothek
vorhanden ist.
- Einführung
- Sortier- und Suchverfahren
- HeapSort
- QuickSort
- Sortieren in Linearzeit
- Selektion
- Datenstrukturen
- Hashtabellen
- Binäre Suchbäume
- Disjunkte Mengen
- Graphalgorithmen
- Minimale Spannbäume
- Kürzeste Wege
- Flüsse in Netzwerken
- Entwurfsprinzipien
- Dynamische Programmierung
- Greedy Algorithmen
- Amortisierungs-Analyse
- Schnelle Fouriertransformation
- Geometrische Algorithmen
- Repräsentation geometrischer Daten
- "sweep line"-Verfahren
- Konvexe Hülle
- Mustersuche in Zeichenketten
Literatur
siehe bitte hier
|
Andreas Abel
Last modified: Tue Jul 18 14:31:24 CEST 2006
|
|
|