AuK

Aus ProgrammingWiki
Archivierte Version vom 2013-09-02T14:33:51+00:00. Aktuelle Version

Inhaltsverzeichnis

Algorithmen und Komplexität

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, kurz: PW. Es sollen also KEINE Folien angefertigt werden.

Wenn Sie noch nie mit einem Wiki gearbeitet haben, lesen Sie bitte zunächst die Wiki Anleitung.
Bevor Sie Bilder in Wiki-Seiten integrieren, beachten Sie bitte die zugehörigen Bildrechte im Internet.

Das PW ist in der Lage, eingebaute Programme (in Scheme, Java, ...) auszuführen, berechnete Ergebnisse auf der betrachteten PW-Seite anzuzeigen, Daten zu visualisieren (Gnuplot), Bilder, Audioclips etc. anzuzeigen, mathematische Formeln adäquat darzustellen (LaTeX) usw. Auf der Startseite erfahren Sie, wie man das macht.

Beachten Sie bitte auch die angebenen Interpreter: Racket steht hier nicht zur Verfügung, wohl aber SISC-Scheme.

Um sämtliche Möglichkeiten eines PW auszuschöpfen ist es notwendig, dass sich sowohl Wiki-Nutzer als auch Wiki-Autoren am System anmelden, um zu arbeiten. Während Wiki-Autoren mittels 'Bearbeiten' den Inhalt von PW-Seiten verändern können, sollen Wiki-Nutzer (meist Lernende) den Text einfach nur lesen und die vorgesehenen Interaktionsstellen aktiv verwenden. Ebenso wie das Starten eines Videos werden Evaluationen vorbereiteter Programmaufrufe per Knopfdruck ausgelöst.

Die Inhalte der Textfelder, die Aufrufe oder Programmtexte enthalten, können - ohne Zusatzmaßnahmen - modifiziert werden. Diese Veränderungen werden automatisch gespeichert, wenn Sie als Nutzer angemeldet sind. In der nächsten Sitzung stehen Ihre Einträge erneut zur Verfügung, sodass Sie dort weiterarbeiten können, wo Sie beim letzten Mal aufhören mussten.

Zusätzlich hat der Administrator die Möglichkeit, auf die individuellen Versionen zuzugreifen und diese mit Hinweisen oder Korrekturen zu versehen. Solche Anmerkungen des Administrators sieht der betreffende Nutzer beim nächsten (angemeldeten) Seitenbesuch und kann daraus lernen bzw. geeignet darauf reagieren.

Klickt man auf das kleine x, das sich nach solchen Veränderungen rot einfärbt, wird der ursprüngliche Inhalt wieder hergestellt. Das alles geschieht ohne 'Bearbeiten' auszuwählen; das ist - wie oben gesagt - den Wiki-Autoren vorbehalten.

Themen


Jedes Thema soll von genau zwei Studierenden bearbeitet werden. Die Themenauswahl entspricht dem Text "Algorithmen und Komplexität" von Chr. Wagenknecht. Lesen Sie den entsprechenden Abschnitt und schauen Sie sich parallel dazu die passenden Inhalte in anderen Quellen an. Leihen Sie weitere Bücher in der Bibliothek aus.

Bitte registrieren Sie sich beim PWiki. Es ist ein anderes Wiki, als das, welches Sie von Ihrer Prüfungseinschreibung her kennen! Deshalb ist eine weitere Registrierung notwendig. Natürlich können Sie die gleichen Anmeldedaten wie beim anderen Wiki wählen, um Ihr Gedächtnis zu entlasten.

Tragen Sie sich bitte bis Mi., 02.10.2013, 08:00 Uhr, in die folgende Tabelle ein, indem Sie die Fragezeichen (und nur diese!) ersetzen. Sollten Sie keinen Platz finden, senden Sie mir ein Email bis zum 02.10.2013.

Syntax: NACHNAME, VORNAME; NACHNAME, VORNAME
ThemaSS 09SS 10SS 11ThemaSS 12WS 13/14
EinführungXXXX??MotivationXX{{{4}}}
Effizienz von AlgorithmenXXXX??EinführungXX{{{4}}}
Hilfsmittel Mathematik 1XXXX??Felder und ListenXX{{{4}}}
Hilfsmittel Mathematik 2XXXX??Hash Tables und Assoziative ListenXX{{{4}}}
Teile und Herrsche 1XXXX??Sortieren und SuchenXX{{{4}}}
Teile und Herrsche 2XXXX??PrioritätswarteschlangenXX{{{4}}}
Systematische SucheXXXX??Sortierte FolgenXX{{{4}}}
Verzweigen und beschränkenXXXX??GraphrepräsentationenXX{{{4}}}
Dynamisches ProgrammierenXXXX??Durchläufe durch GraphenXX{{{4}}}
Greedy-AlgorithmenXXXX??Kürzeste WegeXX{{{4}}}
Probabilistische AlgorithmenXXXX??Minimaler SpannbaumXX{{{4}}}
P-NP-ProblemXXXX??Algorithmische EntwurfsmusterXX{{{4}}}
Näherungsverfahren 1XXXX??Näherungsverfahren 1XX{{{4}}}
Näherungsverfahren 2XXXX??Näherungsverfahren 2XX{{{4}}}
VertiefungsaufgabeXXXXalle Gruppen, je 10 Min. -- noch unsicher!Präsentation zur VertiefungsaufgabeXX{{{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

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.

Die Dokumentation soll genau 6 Seiten umfassen und folgendermaßen gegliedert sein:

  1. Seite (Titelseite): Thema, Name der Bearbeiter/innen; Aufgabenstellung
  2. Seite: Bild von den Rundreisepositionen und ggf. einer Rundreise, die von irgendeinem Programm ermittelt wurde; Entfernungsmatrix
  3. Seite: Intuitiver Lösungsversuch und dessen Bewertung
  4. Seite: Lösung mit einem algorithmischen Entwurfsmuster (Dynamisches Programmieren, ...), das Sie selbst für Ihren Vortrag (s. Liste) oben nicht ausgearbeitet haben; Empirische Effizienzbewertung
  5. Seite: Näherungslösung mit einem geeigneten Verfahren Ihrer Wahl; Effizienzbewertung
  6. Seite: Zusammenfassung und abschließende Bewertung, inkl. Literaturverzeichnis

Die einzelnen Seiten müssen nicht vollständig beschrieben sein: "Weniger" ist manchmal "Mehr"! Auch grafische Darstellungen, Tabellen, Berechnungen, ... sollten in den Text eingefügt werden.

Aufgabenstellung: Navigation - mal ganz anders

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

Das Web-Interface, dem wir unseren Reisewunsch mitteilen, soll möglichst rasch nach Wunsch 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, 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. Hierfür 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 ab, die die XML-basierten Repräsenationen und Technologien in der konkreten Anwendung beschreibt.


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