AuK
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Algorithmen und Komplexität ==
Die Lehrveranstaltung "Algorithmen und Kompexität" (AuK) verlangt von Ihnen, Vorlesungen und zugehörige Computerübungen auszuarbeiten. Hierfür verwenden Sie ein (dafür speziell vorbereitetes) Wiki: Das Programming Wiki, kurz PWiki.
<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 weiter lesen. </big></div>
<div style="padding:10px;background-color:#EEE;text-align:center"><big> Thema: [[Bildrechte im Internet]], bevor Sie Bilder einstellen lesen Sie bitte zunächst diese Seite aufmerksam durch. </big></div>
Das PWiki ist in der Lage, eingebaute Programme (in Scheme, Java, ...) auszuführen, berechnete Ergebnisse auf der betrachteten PWiki-Seite anzuzeigen, Daten zu visualisieren (Gnuplot), Bilder, Audioclips etc. hochzuladen usw. Auf der [[Startseite]] erfahren Sie, wie das gemacht wird. Als Scheme-Dialekt wurde [http://sisc-scheme.org SISC Scheme] verwendet.
=== Beispiel: Fibonacci ===
<code id="4b960fdc15037" rows="20" cols="90">(define fib
(lambda (n)
(if (< n 2)
1
(+ (fib (- n 1)) (fib (- n 2))))))</code>
<run id="4b960fdc15804">
(fib 5)
</run>
Jeder Nutzer kann den Quelltext unmittelbar in diesem Textfeld frei editieren. Bitte nicht mit 'Bearbeiten' als gewöhnliche Wiki-Aktion verwechseln!
Wenn Sie nicht am Wiki angemeldet sind, gehen Ihre Arbeiten am Programmtext mit dem nächsten Seitenaufruf verloren. Ganz anders ist das bei einem angemeldeten Nutzer: Modifizierte Quelltexte, die abschließend per Knopfdruck (unter dem Textfeld) gespeichert wurden, werden nutzerbezogen gespeichert. Meldet sich der betrachtete Nutzer später wieder beim PWiki an, enthält die PWiki-Seite genau die Programmtexte, die dieser Nutzer beim letzten Bearbeitungsvorgang hinterlassen hat.
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.
== Themen ==
Jedes Thema soll von genau ''zwei'' Studierenden bearbeitet werden, im Ausnahmefall von einem.
'''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 in die folgende Tabelle ein, nachdem Sie dazu aufgefordert wurden. <br/>
Syntax: NACHNAME, VORNAME; NACHNAME, VORNAME
{|
|-
|
{| border="1" cellpadding="5" cellspacing="0"
!Woche
!AuK, SS 11, IIb10
!SS 10
!Bearbeiter
{{GruppenEintragAuK|SS11|SS10| 1|Einführung | Wagenknecht, Christian}}
{{GruppenEintragAuK|SS11|SS10| 2|Effizienz von Algorithmen | Wagenknecht, Christian}}
{{GruppenEintragAuK|SS11|SS10| 3|Hilfsmittel Mathematik 1 | }}
{{GruppenEintragAuK|SS11|SS10| 4|Hilfsmittel Mathematik 2 | }}
{{GruppenEintragAuK|SS11|SS10| 5|Teile und Herrsche 1 | }}
{{GruppenEintragAuK|SS11|SS10| 6|Teile und Herrsche 2 | }}
{{GruppenEintragAuK|SS11|SS10| 7|Systematische Suche | }}
{{GruppenEintragAuK|SS11|SS10| 8|Verzweigen und beschränken | }}
{{GruppenEintragAuK|SS11|SS10| 9|Dynamisches Programmieren | }}
{{GruppenEintragAuK|SS11|SS10|10|Greedy-Algorithmen | }}
{{GruppenEintragAuK|SS11|SS10|11|Probabilistische Algorithmen | }}
{{GruppenEintragAuK|SS11|SS10|12|P-NP-Problem | }}
{{GruppenEintragAuK|SS11|SS10|13|Näherungsverfahren 1 | }}
{{GruppenEintragAuK|SS11|SS10|14|Näherungsverfahren 2 | }}
{{GruppenEintragAuK|SS11|SS10|15|Präsentation der Bearbeitung der Vertiefungsaufgabe | alle Gruppen, je 10 Min. }}
|}
[[AuK/Archiv|Archiv mit älteren Arbeiten früherer Semester]]
== 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 eine zu präsentierende Vorlesung und eine zugehörige CÜ. Letztere soll Aufgaben steigenden Schwierigkeitsgrades enthalten und in direktem Bezug zur Vorlesung stehen. Konsultationsmöglichkeiten werden individuell abgesprochen.
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.
==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''':
Wählen Sie 10 Sehenswürdigkeiten in Südostsachsen aus. Diese sollen zu einer PKW-Rundreise, die jeden dieser Orte genau einmal besucht, zusammengeschlossen werden. 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 10*10/2-10=40 Entfernungen zu bestimmen (untere Dreiecksmatrix).
Am Ende der LV-Reihe präsentiert jede Gruppe ihre Ergebnisse in einem jeweils '''10-min.-Vortrag'''. Die Gruppe mit der besten Präsentation erhält die Möglichkeit, ihre Arbeit auf dem Dies academicus im nächsten Jahr einem breiten Publikum vorzustellen.
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: Kurzes Fazit
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 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-SS10]]