Aktuelles

• [19. Februar] Die Folien (ad_v*) sind korrigiert online. Überwiegend wurden Rechtschreibfehler korrigiert. Fehler, die zu Verständnisproblemen führen könnten, sind unten noch explizit aufgeführt.
• [16. Februar] Die Klausuren sind korrigiert. Ergebnisse findet ihr in STiNE und einen Notenspiegel im FB18-Forum hier.
• [4. Februar] Der Foliensatz der heutigen, letzten Vorlesung ist online.
• [3. Februar] Der Foliensatz der Vorlesung vom 28. Januar (Greedy-Verfahren und Ausblick) ist online ebenso wie der Foliensatz vom 21. Januar (Zusammenfassung des Foliensatzes zu P und NP). - Sorry, das ist im Klausur-Orga-Wirr-Warr untergegangen! Bisher hat aber keiner von euch was gesagt, also hat die wohl bisher niemand allzu sehr vermisst ;-)
• [26. Januar] Die Musterlösung zum sechsten und letzten Aufgabenblatt ist online.
• [15. Januar] Da wir gestern nicht weit genug gekommen sind, um die letzte Aufgabe des letzten Aufgabenzettels gut lösen zu können, hier ein Tipp: Probiert die Reduktion von Clique aus.
• [15. Januar] Die Folien der letzten beiden Vorlesungen und der kommenden Vorlesung sind online. Ebenso die Musterlösung zu Blatt 5. Gestern waren wir bis Folie 46 des 17. Foliensatzes gekommen, wir werden nächstes Mal aber diesen Foliensatz noch einmal ganz von vorne beginnen. Ferner werde ich ihn bis Freitag noch um eins, zwei Folien anreichern, um einige Dinge noch einmal auf den Punkt zu bringen, zu denen es gestern Fragen von euch gab.
• [8. Januar] Die Folien der gestrigen Vorlesung und der neue - und letzte - Aufgabenzettel sind online. Die erste Aufgabe solltet ihr schon bearbeiten können. Den Stoff für die zweite Aufgabe machen wir am kommenden Donnerstag und Freitag.
• [17. Dezember] Die Folien der heutigen Vorlesung sind online. Euch allen schöne, erholsame Ferien, ein ruhiges Weihnachtsfest und einen guten Rutsch ins neue Jahr! Die nächste Vorlesung ist dann am 7. Januar 2011.
• [16. Dezember] Die Folien der heutigen Vorlesung sind online (angepasst darauf, was wir heute geschaft haben), sowie die Musterlösung zu Blatt 4.
• [12. Dezember] Der fünfte Aufgabenzettel ist online.
• [10. Dezember] Die Folien von heute sind online.
• [4. Dezember] Die Termine für das erste Repetitorium stehen fest. Bitte meldet euch an, wenn ihr teilnehmen wollt, da die Plätze aufgrund der zur Verfügung stehenden Räume begrenzt sind! Mehr Informationen sind hier zu finden.
• [4. Dezember] Die Folien der gestrigen Vorlesung (VL 11) sind noch einmal korrigiert und um einige Folien mit Anmerkungen zur Nachbereitung ergänzt worden (insb. jeweils vor den Beispielen).
• [3. Dezember] Die Folien der gestrigen und der heutigen Vorlesung sind online. (Die fehlerhaften Bilder sind korrigiert!) Ferner wurde in den Folien von Vorlesung 6 und 7 der kleine Fehler beim BubbleSort korrigiert (dort stand swap(A[i],A[idx]) statt swap(A[i],A[i+1])).
• [2. Dezember] Die Musterlösung zu Blatt 3 ist online.
• [28. November] Die Folien von Freitag und der neue Aufgabenzettel sind jetzt online. Endlich! ;-)
• [19. November] Die Folien von heute sind online.
• [18. November] Die Folien von heute sind online. Achtet beim Drucken darauf, ob ihr die ganzen Beispiele wirklich mitdrucken wollt/müsst. (Ihr wisst ja, den Wald retten... ;-) ) Im Handout reichen sonst die Seiten 30-33 zum Schluß. Dort steht alles wichtige nochmal zusammengefasst.
• [17. November] Die Musterlösung zu Blatt 2 ist online.
• [12. November] Die Folien von heute sowie der neue Aufgabenzettel sind jetzt online.
• [4. November] Folien von heute und für morgen sind online.
• [3. November] Die Musterlösung zu Blatt 1 ist online.
• [31. Oktober] Unter 'Sonstige Materialien und Links' unten ist ein kleiner Text zum Lösen von Rekurrenzgleichungen mittels der Substitutionsmethode zu finden. Dort wird auch beschrieben wie der in der Vorlesung übersprungene Induktionsbeweis zu führen ist und warum dieser benöntigt wird.
• [30. Oktober] Unter 'Sonstige Materialien und Links' unten ist eine kleine Formelsammlung zu finden.
• [29. Oktober] Der neue Aufgabenzettel ist unten zu finden!
• [29. Oktober] Die Folien der heutigen Veranstaltung sind unten zu finden. Dort gibt es sie nun auch im praktischen 'Handout'-Format (schöner zum Drucken).
• [27. Oktober] Die AD-Skripte sind da! Zu finden sind sie in Raum C-209 (direkt gegenüber dem Sekretariat von TGI).
• [22. Oktober] Die Folien der heutigen Veranstaltung gibt es hier.
• [21. Oktober] Die Abgabe der Lösungen soll immer bis Donnerstag 10 Uhr geschehen! Dafür wird es die Aufgabenzettel früher geben.
  (Abgabe alle zwei Wochen, erstmalige Abgabe am 28.10.)
• [21. Oktober] Die Freitagsvorlesung findet wöchentlich von 14-16 Uhr in ESA B statt (erstmalig am 22.10).

Zum Inhalt

Vorlesungsfolien

Errata zu den Folien:

• Kapitel 7, Folie 9 (7): v steht hier für 'value', also ist v(p) der Wert, der im Knoten p gespeichert ist.
• Kapitel 9, Folie 18 (10): 'Teilbaum von n' -> 'Teilbaum von p'.
• Kapitel 15, Folie 33 (18): - f(Y,X) (das Minus fehlt beim Ergebnis).
• Kapitel 18, Folie 63 (30): 'Sei T der vo', vo -> vom.
• Kapitel 19, Folie 54 (34) und 61 (41): Korrekturen wie oben bzgl. Heaps (Kapitel 7 oben) und Suchbäumen (Kapitel 9 oben).

Folien zu den einzelnen Vorlesungen:

• Folien der 21. Vorlesung am 4. Februar: PDF, Handout
• Folien der 20. Vorlesung am 28. Januar: PDF, Handout
• Die folgenden beiden Foliensätze (der 16., 17., 18. und 19. Vorlesung am 13., 14., 21. und 27. Januar) behandeln die Komplexitätsklassen P und NP und das Thema NP-Vollständigkeit.
  • P und NP: PDF, Handout
    • Zusammenfassung des vorherigen Foliensatzes: PDF, Handout
  • NP-Vollstädigkeit: PDF, Handout
  Thematisch entspricht dies dem Stoff in Kapitel 34 im [Cormen], wobei wir nicht alle NP-Vollständigkeitsbeweise geführt haben, die dort geführt werden.
• Folien der 15. Vorlesung am 7. Januar: PDF, Handout
• Folien der 14. Vorlesung am 17. Dezember: PDF, Handout
• Folien der 13. Vorlesung am 16. Dezember: PDF, Handout
• Folien der 12. Vorlesung am 10. Dezember: PDF, Handout
• Folien der 11. Vorlesung am 3. Dezember: PDF, Handout
• Folien der 10. Vorlesung am 2. Dezember: PDF, Handout
• Folien der 9. Vorlesung am 26. November: PDF, Handout
• Folien der 8. Vorlesung am 19. November: PDF, Handout
• Folien der 7. Vorlesung am 18. November: PDF, Handout
• Folien der 6. Vorlesung am 12. November: PDF, Handout
• Zusammenfassung der 5. Vorlesung am 5. November: PDF, Handout
• Folien der 5. Vorlesung am 5. November: PDF1 (Folien 11 bis 30) und PDF2 (Folien 6 bis 22) - oder als ZIP1 und ZIP2 (stimmt mit Vorlesung 04 und 05 unten überein)
• Folien der 4. Vorlesung am 4. November: PDF, Handout
• Folien der 3. Vorlesung am 29. Oktober: PDF, Handout
• Folien der 2. Vorlesung am 22. Oktober: PDF, Handout
• Folien der 1. Vorlesung am 21. Oktober: PDF, ZIP (stimmt mit Vorlesung 01 unten überein)

Nachfolgend die Foliensätze, die mit den gedruckten Folien übereinstimmen. Die Nummerierung der Foliensätze entspricht der letztjährigen Veranstaltung. Dieses Jahr werden gelegentlich zusätzliche Folien zur Verfügung gestellt werden. Oben sind stets die Folien zu den Vorlesungen zu finden.

Folien wie im gedruckten Skript

Vorlesung 01 (PDF)(zip)	Vorlesung 02 (PDF)(zip)	Vorlesung 03 (PDF)(zip)	Vorlesung 04 (PDF)(zip)	Vorlesung 05 (PDF)(zip)
Vorlesung 06 (PDF)(zip)	Vorlesung 07 (PDF)(zip)	Vorlesung 08 (PDF)(zip)	Vorlesung 09 (PDF)(zip)	Vorlesung 10 (PDF)(zip)
Vorlesung 11 (PDF)(zip)	Vorlesung 12 (PDF)(zip)	Vorlesung 13 (PDF)(zip)	Vorlesung 14 (PDF)(zip)	Vorlesung 15 (PDF)(zip)
Vorlesung 16 (PDF)(zip)	Vorlesung 17 (PDF)(zip)	Vorlesung 18 (PDF)(zip)	Vorlesung 19 (PDF)(zip)	Alle Folien (PDF) (zip)

Aufgaben

• Aufgabenblatt 1: (PDF) (zip) Lösung zu Blatt 1: (PDF) (zip)
• Aufgabenblatt 2: (PDF) (zip) Lösung zu Blatt 2: (PDF) (zip)
• Aufgabenblatt 3: (PDF) (zip) Lösung zu Blatt 3: (PDF) (zip)
• Aufgabenblatt 4: (PDF) (zip) Lösung zu Blatt 4: (PDF) (zip)
• Aufgabenblatt 5: (PDF) (zip) Lösung zu Blatt 5: (PDF) (zip)
• Aufgabenblatt 6: (PDF) (zip) Lösung zu Blatt 6: (PDF) (zip)

Literatur

Sonstige Materialien und Links

• Ein Text zum Lösen von Rekurrenzgleichungen mittels der Substitutionsmethode.
• Eine kleine Formelsammlung.
• Hinweise eines Mathematikers zum Lernen von mathematischen Inhalten.

Kriterien für den Übungsschein

• Die Übungsgruppen finden im 14 tägigem Rhythmus statt, beginnend ab dem 18.10! An 6 der 7 Termine (abzüglich Krankmeldungen mit Attest eines Arztes) muss man anwesend sein. Eine aktive Beteiligung ist nötig. Ferner müssen mindestens 50% der insgesamt vergebenen Punkte erreicht werden und in mindestens 4 der 6 Aufgabenblätter mindestens 40% der Punkte des Aufgabenblattes erreicht werden.
• Es wird 6 Aufgabenzettel mit leicht variierender Punktezahl (etwa 20) geben.
• Die Ausgabe der Aufgaben erfolgt erstmalig am 18.10. und dann im 14 tägigen Rhythmus jeden zweiten Montag. Die Aufgabenzettel werden auf dieser Webseite und in STiNE veröffentlicht werden.
• Die Aufgaben sollen in Kleingruppen von bis zu drei Studierenden bearbeitet werden. Jedes Mitglied einer Gruppe muss jede der abgegebenen Aufgaben vorrechnen können.
• Die Lösungen zu den Aufgaben sind 10 Tage nach ihrer Bekanntgabe bis Donnerstag, 10 Uhr abzugegeben. Die Abgabe kann via Email erfolgen oder via Einwurf in den AD-Kasten in Haus C, 1.Stock, vor Raum C-201.
• Das Kopieren oder Abschreiben fremder Lösungen führt zu Punktabzügen bei allen Beteiligten und gilt als Täuschungsversuch

Klausurtermine

• Die erste Klausur ist am 15.02.2011, 11.00-13.00 Uhr in ESA A.
• Die zweite Klausur ist am 25.03.2011, 10.00-12.00 in ESA B.

Klausurvorbereitung

• Die Folien der letzten Vorlesung (am 4.2.2010) des letzten Wintersemesters sind hier zu finden. Sie geben einen stichpunktartigen Überblick über die Veranstaltung.
• Die Aufgaben zur Klausurvorbereitung von 2009/10 finden Sie hier, die zugehörigen Lösungen hier.

Repetitorium

[Lehre] [TGI] [Informatik]