AuK
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Algorithmen und Komplexität ==
Die Lehrveranstaltung "Algorithmen und Kompexität" (AuK) im SS 12 verlangt von Ihnen, Vorlesungen und zugehörige Computerübungen auszuarbeiten. Hierfür verwenden Sie das [[Startseite|Programming Wiki]], kurz: ''PW''.
<div style="padding:10px;background-color:#EEE;text-align:center"><big> Wenn Sie noch nie mit einem Wiki gearbeitet haben lesen sie bitte zunächst die [[Wiki_Anleitung|Wiki Anleitung]], bevor Sie hier weitergehen. </big></div>
<div style="padding:10px;background-color:#EEE;text-align:center"><big> Bevor Sie Bilder in Wiki-Seiten integrieren, beachten Sie bitte die zugehörigen [[Bildrechte im Internet]]. </big></div>
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 usw. Auf der [[Startseite]] erfahren Sie, wie das gemacht wird.
Beachten Sie bitte auch die angebenen Interpreter: Racket steht hier nicht zur Verfügung, wohl aber [http://sisc-scheme.org 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 <tt>x</tt>, 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 "[http://www.mpi-inf.mpg.de/~mehlhorn/Toolbox.html Data Structures and Algorithms: The Basic Toolbox]" von Mehlhorn und Sanders. Lesen Sie den entsprechenden Abschnitt und schauen Sie sich parallel dazu die passenden Inhalte in "[http://www.inf.hs-zigr.de/~wagenkn/AuK-Buch/ Algorithmen und Komplexität]" von Wagenknecht an. Zu letzterem gibt es fertiges PW-Material, das Sie in der unten angegebenen Tabelle (linker Teil) finden und bei Bedarf in Ihrer PW-Seite verlinken (referenzieren) können. Leihen Sie [http://www.inf.hs-zigr.de/~wagenkn/TI/AuK/materialien.html 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 kennen! Deshalb ist eine weitere Registrierung notwendig. Natürlich können Sie die Anmeldedaten wie beim anderen Wiki wählen, um Ihr Gedächtnis zu entlasten.
Tragen Sie sich bitte bis '''Do., 09.02.2012,''' 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 09.02.2012.<br/>
Syntax: NACHNAME, VORNAME; NACHNAME, VORNAME
{|
|-
|
{| border="1" cellpadding="5" cellspacing="0"
!Thema
!SS 09
!SS 10
!SS 11
!Thema
!SS 12
!Bearbeiter
{{GruppenEintragAuK|Einführung|Motivation | Wagenknecht, Christian}}
{{GruppenEintragAuK|Effizienz von Algorithmen|Einführung | Wagenknecht, Christian}}
{{GruppenEintragAuK|Hilfsmittel Mathematik 1|Felder und Listen | Kloß, Robert }}
{{GruppenEintragAuK|Hilfsmittel Mathematik 2|Hash Tables und Assoziative Listen | Riemer, Nico }}
{{GruppenEintragAuK|Teile und Herrsche 1|Sortieren und Suchen | Schmidt, Harald; Kutsche, Michael }}
{{GruppenEintragAuK|Teile und Herrsche 2|Prioritätswarteschlangen | Döring, Marcus; Zoeke, Robert }}
{{GruppenEintragAuK|Systematische Suche|Sortierte Folgen | Leuschner, Jens; Wollstein, Romano }}
{{GruppenEintragAuK|Verzweigen und beschränken |Graphrepräsentationen | Förster, Nico; Heidelberger, Ronny }}
{{GruppenEintragAuK|Dynamisches Programmieren|Durchläufe durch Graphen | Riedel, Robert; Sprenger, Bettina }}
{{GruppenEintragAuK|Greedy-Algorithmen|Kürzeste Wege | Oliynyk, Yevgeniy; Kiese, Maximilian }}
{{GruppenEintragAuK|Probabilistische Algorithmen|Minimaler Spannbaum | Voigt, Christopher; Müssig, Daniel }}
{{GruppenEintragAuK|P-NP-Problem|Algorithmische Entwurfsmuster | Töpfer, Kevin; Schmidt, Maik }}
{{GruppenEintragAuK|Näherungsverfahren 1 | Näherungsverfahren 1 | Dvorak, Philipp // Fiedler, Paul}}
{{GruppenEintragAuK|Näherungsverfahren 2 | Näherungsverfahren 2 | Napierala, Gino // Fiedler, Paul }}
{{GruppenEintragAuK|Vertiefungsaufgabe|Präsentation zur Vertiefungsaufgabe| alle Gruppen, je 10 Min. }}
|}
[http://www.inf.hs-zigr.de/~wagenkn/TI/Komplexitaet/Referatesammlung.html 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:
# Lesen Sie das entsprechende Kapitel im englischen Text.
# Greifen Sie die inhaltlichen Schwerpunkte heraus und sichten Sie passende Inhalte aus dem AuK-Buch (von CW) sowie ggf. weiterer Quellen.
# Entwerfen Sie die Gliederung Ihres PW-Beitrags und planen Sie die Programmbeispiele.
# Füllen Sie die entworfene Struktur mit Inhalten und ergänzen Sie Übungsaufgaben an den Stellen, wo sie gelöst werden sollten.
# 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 Vorträge (s. obige Liste), die Sie gehalten haben. Es wird erwartet, dass jede Gruppe individuell arbeitet. Im '''Beleg''' sind die Anteile der beiden Bearbeiter/innen auszuweisen.
'''Aufgabenstellung''':
Eine PKW-''Rundreise'' soll durch die folgenden Städte führen und dabei jeden dieser 16 Orte genau einmal besuchen:
Dresden, Berlin, Spröda, Lüneburg, Löbau, Limbach-Oberfrohna, Blankenheim, Dohna, Eisenach, Dürrhennersdorf, Callenberg, Eisenhüttenstadt, Pirna, Riesa, Coswig und Seerhausen. Ausnahme: Die Stadt, in der die Rundreise beginnt und endet, ist die einzige zweimal besuchte Stadt.
Gesucht ist die kürzeste Rundreise.
Kleine Anleitung: Nachdem Sie die Orte gewählt haben, ermitteln Sie die zugehörige Entfernungsmatrix. Routenplaner, die Sie im Web finden, unterstützen Sie dabei. Gehen Sie von einem ungerichteten Graphen aus, d.h. die Länge des Weges von A nach B soll genauso lang sein, wie von B nach A. Dadurch haben Sie lediglich (16*16-16)/2=120 Entfernungen zu bestimmen (untere Dreiecksmatrix).
Am Ende der LV-Reihe präsentiert jede Gruppe ihre Ergebnisse in einem jeweils '''10-min.-Vortrag'''.
Der '''Beleg''' soll genau 6 Seiten umfassen und folgendermaßen gegliedert sein:
# Seite (Titelseite): Thema, Name der Bearbeiter/innen; Aufgabenstellung
# Seite: Bild von den Rundreisepositionen und ggf. einer Rundreise, die von irgendeinem Programm ermittelt wurde; Entfernungsmatrix
# Seite: Intuitiver Lösungsversuch und dessen Bewertung
# Seite: Lösung mit einem algorithmischen Entwurfsmuster (Dynamisches Programmieren, ...), das Sie selbst für Ihren Vortrag (s. Liste) oben ''nicht'' ausgearbeitet haben; Empirische Effizienzbewertung
# Seite: Näherungslösung mit einem geeigneten Verfahren Ihrer Wahl; Effizienzbewertung
# 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.
Der Beleg, inkl. CD mit den entwickelten Programmen, ist unmittelbar nach dem Vortrag zur Bewertung abzugeben.
<!--
Vertiefungsthemen betreffen spezielle Inhalte, die (auf der Basis von Grundkenntnissen aus AuK) eine besondere Aufmerksamkeit verdienen.
Aus dem folgenden Themenangebot können bis zu 4 Studis je ein Thema auswählen und zu einem Referat (nur Vortrag, keine CÜ) ausarbeiten. Hierfür stehen der Gruppe '''20 min.''' zur Verfügung. Die '''Referate''' werden am Ende des Semsters (nach den V-CÜ-Themen aus obiger Tabelle) gehalten. Es werden '''Folien''' (z.B. Powerpoint, Latex-Beamer, OpenOffice, ...) - ''keine'' Belege - erwartet. Im sich anschließenden persönlichen Gespräch mit dem Dozenten werden die Anteile der einzelnen Gruppenmitglieder festgestellt, sodass eine individuelle Bewertung sichergestellt ist. Diese geht zu '''40%''' in die Gesamtbewertung ein, d.h., dass die V-CÜ-Beiträge (60%) zu einem der obigen Themen bei der Notenbildung dominieren.
* Thema 1: [http://de.wikipedia.org/wiki/AKS-Primzahltest AKS-Primzahltest]
* Thema 2: [http://de.wikipedia.org/wiki/Ameisenalgorithmus Selbstorganisation und Metaheuristiken]
* Thema 3: Zufallszahlen und Monte-Carlo-Methode - Eine theoretische Untersuchung (Material wird bereitgestellt)
* Thema 4: [http://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Kapitel_2/ExtraDix Sortieralgorithmus ExtraDix]
* Thema 5: ...
* Thema 6: ...
Bitte warten Sie mit der Auswahl, bis die Themenliste komplett ist. Dann schreiben Sie einfach Ihre Familiennamen hinter die Themen.
-->
== Evaluation der Lehrveranstaltung ==
Am Ende des Semesters bewerten Sie in gewohnter Weise die LV mit dem Ziel, gemeinsam an didaktischen Verbesserungen zu arbeiten, die den nachfolgenden Studierenden-Gruppen zugute kommen sollen. Vielen Dank!
[[Evaluation-AuK]] </br>
Bisherige Evaluationen: <document>SS 2012</document>