AuK

Aus ProgrammingWiki
Archivierte Version vom 2013-09-04T06:58:39+00:00. Aktuelle Version

Inhaltsverzeichnis

Algorithmen und Komplexität

Leistungsnachweise

  • Prüfungsform: PR = Referat, d.h. 2 Studis präsentieren neuen Stoff in 2 Std. Vorlesung + 2 Std. Computerübung
  • Vertiefungsaufgabe: Das jeweilige Studi-Paar bearbeitet eine (kreative) Komplexaufgabe. Dabei wird Wissen aus anderen Vorträgen und Gebieten, insbes. "Datenrepräsentation mit XML" benötigt.

Arbeitsanleitung


Die Lehrveranstaltung "Algorithmen und Kompexität" (AuK) verlangt von Ihnen die Präsentation neuen Stoffs in Vorlesungen und zugehörigen Computerübungen. Zur Ausarbeitung der entsprechenden Materialien verwenden Sie das Programming Wiki. Es sollen also KEINE Folien angefertigt werden.

Bitte registrieren Sie sich unbedingt als ProgrammingWiki-Nutzer.

Hinweise


Themen und Bearbeitungsplan

  • Die Themen (s. folgende Tabelle, Spalte für WS 13/14) korrespondieren mit den Kapiteln des Buches "Algorithmen und Komplexität" von Chr. Wagenknecht. Lesen Sie den entsprechenden Abschnitt und schauen Sie sich parallel dazu die jeweiligen Inhalte in anderen Quellen an. Bibliothek nutzen!!
  • Die Einschreibung nimmt der Dozent in der ersten Veranstaltungswoche vor. Je nach dem Umfang eines Themas bearbeitet ein Studierendenpaar genau ein oder zwei Themen in ein und derselben Zeit, nämlich in 2 VL + 2 CÜ (= 1 Woche). Die Tabelle reicht also für mind. 16 Studis, die die ausgewiesenen Inhalte innerhalb von 8 Wochen bearbeiten. Die ersten beiden Wochen sind dem Dozenten vorbehalten, so dass sich für den Referateteil insgesamt 10 Wochen (= 2/3 des Semesters) ergeben.
Thema (SS 09-11; WS 13/14)SS 09SS 10SS 11WS 13/14Verantwortlich (WS 13/14)Thema (SS 12)SS 12WS 13/14Verantwortlich (WS 13/14)
EinführungXXXXWoche 1: 2 StudisMotivationXX
Effizienz von AlgorithmenXXXX- " -EinführungXX
Hilfsmittel Mathematik 1XXXXWoche 2: 2 StudisFelder und ListenXX
Hilfsmittel Mathematik 2XXXX- " -Hash Tables und Assoziative ListenXX?
Teile und Herrsche 1XXXXWoche 3: 2 StudisSortieren und SuchenXX
Teile und Herrsche 2XXXX- " -PrioritätswarteschlangenXX?
Systematische SucheXXXXWoche 4: 2 StudisSortierte FolgenXX
Verzweigen und beschränkenXXXX- " -GraphrepräsentationenXX?
Dynamisches ProgrammierenXXXXWoche 5: 2 StudisDurchläufe durch GraphenXX?
Greedy-AlgorithmenXXXX- " -Kürzeste WegeXX
Probabilistische AlgorithmenXXXXWoche 6: 2 StudisMinimaler SpannbaumXX
P-NP-ProblemXXXXWoche 7: 2 StudisAlgorithmische EntwurfsmusterXX
Näherungsverfahren 1XXXXWoche 8: 2 StudisNäherungsverfahren 1XX
Näherungsverfahren 2XXXX- " - (oder 2 weitere Studis)Näherungsverfahren 2XX{{{4}}}


Referatesammlung

Ablauf

Von allen Studierenden wird erwartet, dass sie vor der betreffenden Veranstaltung (V+CÜ) den zum jeweiligen Thema gehörenden Lehrbuchtext gelesen haben.

Die beiden Themenverantwortlichen gestalten und präsentieren eine Vorlesung und eine zugehörige CÜ. Letztere soll Aufgaben steigenden Schwierigkeitsgrades enthalten und in direktem Bezug zur Vorlesung stehen. Konsultationsmöglichkeiten gibt es stets in der dieser Veranstaltung vorausgehenden Woche.

Alle Studis sind zur (aufgeforderten, rückfragenden bzw. korrigierenden) Wortmeldungen in der Vorlesungen, zur Aktivität bei der Bearbeitung der ÜA und zur Einschätzung der Vorträge und Materialien aufgerufen.

Bei der Erarbeitung der Materialien für die Veranstaltungen gehen die jeweils Verantwortlichen bitte folgendermaßen vor:

  1. Lesen Sie das entsprechende Kapitel im AuK-Buch (von CW).
  2. Greifen Sie die inhaltlichen Schwerpunkte heraus und sichten Sie passende Inhalte in diverser Zusatzliteratur und ggf. im Web.
  3. Entwerfen Sie die Gliederung Ihres PW-Beitrags und planen Sie die Programmbeispiele.
  4. Füllen Sie die entworfene Struktur mit Inhalten und ergänzen Sie Übungsaufgaben an den Stellen, wo sie gelöst werden sollten.
  5. Gehen Sie das erarbeitete PW noch einmal komplett durch.

Zur Vorlesung soll nur das PW verwendet werden, also keine Powerpoint-Folien usw. Gestalten Sie die Vorlesung interaktiv, indem die Zuhörer in Diskussionen und durch das Lösen von kleineren Übungsaufgaben einbezogen werden.

Vertiefungsaufgabe

Wichtiger Hinweis: Die Vertiefungsaufgabe wird als Modulübergreifender Beleg bearbeitet - AuK + XML. Damit werden bei reduziertem Arbeitsaufwand Synergien befördert.

Mit der erfolgreichen Bearbeitung der Vertiefungsaufgabe sollen Sie nachweisen, dass Sie in der Lage sind, passende algorithmische Lösungsverfahren anzuwenden, deren Effizienz zu bewerten und alternative Näherungslösungen zu suchen.

Die gestellte Aufgabe ist für alle gleich. Sie wird in den gleichen Zweiergruppen bearbeitet, wie die Referate (s. obige Liste), die Sie gehalten haben. Es wird erwartet, dass jede Gruppe individuell arbeitet. Im schriftlichen Dokumentation (Erläuterungen, welche Verfahren ausgewählt und wie sie in den Lösungskontext eingebunden wurden) sind die Anteile der beiden Bearbeiter/innen auszuweisen.


Aufgabenstellung: Navigation - mal etwas anders (Modulübergreifender Beleg)

Wir planen eine PKW-Fahrt von Ort A nach Ort B (Streckennetz Sachsen; GPS-Daten!).

Das Web-Interface, dem wir unseren Reisewunsch mitteilen, soll möglichst rasch nach Wunscheingabe wahlweise entweder die schnellste oder die kürzeste Route als Liste ausgeben (zusätzlich auch gern in grafischer Form). Der Nutzer dieses Web-Angebots soll außerdem die Möglichkeit haben, Pflichtpunkte (= unbedingt zu besuchende Zwischenstationen), Pflichtstreckenabschnitte (= Streckenabschnitte, die unbedingt auf der Route liegen müssen) und Sperrbereiche (= Orte bzw. Streckenabschnitte, die keinesfalls auf der Route liegen dürfen) anzugeben.

Die interne Repräsentation dieser Daten soll in XML (ggf. JSON) geschehen. Deren Verarbeitung geschieht mit selbstgewählten XML-Technologien. Die Effizienz der Verfahren ist zu bewerten und führt ggf. zum Ersatz eines Verfahrens durch ein anderes (auch Näherungsverfahren). Diese Aspekt gehört zu Ihrem Referat und geht folglich in die Bewertung (AuK) ein. Für die Bearbeitung der Aufgabenlösung steht ein zeitliches Volumen aus dem Lehrgebiet Datenrepr. mit XML zur Verfügung (Modulübergreifender Beleg). Im Fach Datenrepr. mit XML geben Sie eine entsprechende Entwicklerdokumentation als Beleg zur Bewertung ab, die die XML-basierten Repräsenationen und Technologien in der konkreten Anwendung beschreibt.


Der Beleg, inkl. CD mit den entwickelten Programmen und Nutzerdoku, ist in der LV Datenrepr. mit XML abzugeben.