Sam /

Herbstakademie 2006 in Beinrode

Vom 29.9.2006 (Freitag abend) bis 3.10.2006 (Dienstag nachmittag) fand im Schullandheim "Gut Beinrode" bei Leinefelde erstmalig eine dritte Schülerakademie statt. Diese Veranstaltung war nicht nur in Bezug auf die Zeit (Herbst) sondern vor allem konzeptionell eine Neuerung.

Die Schüler konnten eines von 4 Themen wählen, mit welchem sie sich dann in intensiver Gruppenarbeit beschäftigten. Die Seminare bestanden aus Vorträgen der betreuenden Studenten, Eigenarbeit und einer abschließenden Präsentation. Hierbei stellten die Schüler ihr eigenes Thema und die Ergebnisse der ganzen Gruppe vor.

Inhalt

Themen

1. Approximative Algorithmen der Graphentheorie

Im Allgemeinen ist es sehr schwer optimale Lösungen für Graph-Probleme (Färbung mit möglichst wenig Farben, kürzeste Wege, Rundreiseproblem etc.) zu finden. Wir werden uns einerseits mit der Kategorisierung solcher Probleme beschäftigen und andererseite Algorithmen behandeln, die mit deutlich weniger Suchaufwand gute Näherungslösungen liefern.

  • Was ist ein Optimierungs-/Entscheidungsproblem?
  • Komplexitätsklassen (subpolynomiale, polynomiale (P), NP und NP-vollständige Probleme)
  • Spezielle Problem und Algorithmen, Laufzeitanalyse
  • Approximative Algorithmen: Wirkungsgrad, obere und untere Schranken, Zusammenhang zur P≠NP-Frage.

2. Zufällige Irrfahrten

Man stelle sich folgende Situation vor: Ein "Teilchen" startet zur Zeit 0 auf der Höhe 0 und bewegt sich dann auf der Zeitachse fort, in dem es von Zeitpunkt n zu Zeitpunkt n+1 seine Höhe entweder um 1 erhöht oder um 1 erniedrigt, wobei beide Ereignisse gleichwahrscheinlich sind. Führt man n solche Zeitschritte durch, so versucht man nun (in Abhängigkeit von n), Aussagen über die Wahrscheinlichkeit von bestimmten vorgegeben Ereignissen zu treffen. Wie hoch ist die Wahrscheinlichkeit, dass die Endhöhe kleiner 6 ist, dass das Maximum auf dem Weg größer als 4 ist, dass sich das Teilchen nur in der positiven Teilebene bewegt, dass es genau 5 mal die Höhe 0 erreicht und wie kann man gute Näherungen für die gefundenen Terme angeben? Und was passiert, wenn n gegen unendlich geht?

Zuerst werden wir die grundlegenden Begriffe und Bezeichnungen einführen, kurz das Bernoulli-Schema wiederholen und die verschiedenen Aufgabenstellungen erklären. Mit den uns dann gegebenen Mitteln versuchen wir dann, einige grundlegene Lemmata wie das Spiegelungsprinzip zu beweisen, um uns dann an die Berechnung der Wahrscheinlichkeiten einiger obengenannter Ereignisse zu machen. Dabei werden wir dann einige Zusammenhänge zwischen scheinbar völlig verschiedenen Aufgabenstellungen finden, indem wir den Begriff des dualen Graphen einführen. Letztendlich kommen wir zu dem, was das ganze Thema so interessant macht: Einigen Anwendungen aus der "Glücksspieltheorie" und einem Ausblick auf die Möglichkeiten.

Als Voraussetzungen für das Thema braucht man eigentlich nicht mehr als das Bernoulli-Schema, Grundlagen aus der Kombinatorik und ein bisschen "Mut zum Rechnen". Natürlich werden wir die Bewegung auch am PC veranschaulichen, denn es überrascht schon, welch "verrückte" Richtungen die Teilchen teilweise einschlagen.

3. Gödelscher Unvollständigkeitssatz

Hier möchten wir uns mit dem formalen Beweisen beschäftigen. Was ist eigentlich ein Beweis und was kann man überhaupt beweisen? Um einem sehr wichtigen Resultat auf diesem Gebiet näher zu kommen, werden wir uns mit Logik und auch ein wenig theoretischer Informatik beschäftigen. Stichworte aus dem Programm des Kurses sind dann z. B. die Prädikatenlogik, formale Zahlentheorie, primitv-rekursive Funktionen und zum krönenden Abschluss der Beweis des Unvollständigkeitssatzes.

4. Simulation von Vielteilchensystemen

Mit der heutzutage vorhanden Rechentechnik ist es möglich, viele physikalische, chemische und technische Prozesse sehr genau zu simulieren. Betrachtet man das zu untersuchende System als Verbund vieler kleiner Teile (entweder als kleine gedachte Einheiten oder wirklich auf molekularer Ebene), muss man die Wechselwirkungen dieser Teilchen berechnen. Das folgende Kursprogramm ist dabei vorgesehen:

  • Kurze Einführung in die mathematischen Grundlagen: Differentiation, Taylor-Entwicklung und gewöhnliche Differentialgleichungen
  • Physikalische Grundlagen: Newtonsche Bewegungsgleichung, verschiedene Wechelwirkungspotentiale
  • Entwicklung numerischer Lösungsverfahren
  • Implementation der Verfahren an einfachen Beispielen (z.B. Simulation von Himmelskörpern)
  • Verbesserung der Algorithmen (vor allem Effizienzsteigerung)
  • Simulation komplexer Systeme (z.B. Kollisionsprozesse von Körpern, granulare Strömungen, Moleküldynamik)
  • Visualisierung der Ergebnisse

Vorkenntnisse in Differentialrechnung sind nicht erforderlich. Programmiererfahrung ist von Vorteil, aber nicht unbedingt notwendig, da die Programme in Teamarbeit geschrieben werden sollen.

Nachlese/Präsentation

Die Kurse Graphentheorie und Gödel:

Der Kurs Vielteilchensysteme hat auch einigen Output gehabt, hier sind die Vorlagen , die Dateien von Daniel , von Sebastian&Benjamin und von Anja&Josef .

Außerdem gibt es hier die leicht gepatchte Version des Visualisierungstools gdpc einschließlich Binary (Linux). Das Original stammt von Jonas Frantz. Die Fortran 90 Kurzeinführung und den verwendeten Compiler g95 gibt es ebenfalls zum Herunterladen. Man kann auch den Fortran-Compiler der GNU-Serie (gfortran) verwenden.

Das folgende Bild zeigt die Kristallisation einer Substanz bei Abkühlung (programmiert von Anja und Josef).

Chronik (Wurzel 11/2006)

Rot Hälfte?

So hörte man am Freitag, dem 29.9.2006, im Zug von Jena über Erfurt nach Leinefelde einige Jugendliche fragen, die mit ihrem Lieblingskartenspiel Marja-Pussi die Fahrt zu überbrücken versuchten.

Etwa ein Konzert, Fußballspiel oder Volksfest in Leinefelde?

Nichts dergleichen - etwa 20 Schüler aus ganz Thüringen und sechs betreuende Mathestudenten der Universität Jena kamen zur mathematischen Herbsttagung der Schülerakademie Mathematik (SAM) des Wurzel-Vereins über das Wochenende zum 3. Oktober auf dem "Gut Beinrode" zusammen. Anders als bei den vorangegangenen, allseits beliebten Oster- bzw. Sommermathelagern hatten Schüler der Oberstufe die Möglichkeit, sich in eines von drei interessanten Themen (Approximative Algorithmen der Graphentheorie, Gödelscher Unvollständigkeitssatz, Simulation von Vielteilchensystemen) einzuwählen und insgesamt 18 Stunden intensiv damit auseinander zu setzen. Die Ergebnisse der harten Arbeit wurden am Dienstag von den Teilnehmern der jeweiligen Kurse den anderen vorgestellt.

Neben Konzentration und geistiger Anstrengung wurde der sportliche Ausgleich nicht außen vor gelassen, den wir am Sonntagnachmittag bei einer GNW (Ganznachmittagswanderung) in der Beinroder Umgebung fanden. Außerdem wurde die Tagung durch Freizeitaktivitäten wie Spieleabend, Knobelaufgaben, jede Menge Pussi sowie Pussiturnier und Abschlussfest bereichert, so dass niemand über Eintönigkeit oder Langeweile klagen konnte.

Insgesamt fünf gelungene Tage - von Schülerseite aus wird jetzt schon der Wunsch nach einer Wiederholung des Mathelagers, gern auch nach dem neuen Konzept, laut.

Zufriedene Gesichter auf der Heimfahrt.

"Ja" - "Rot ist Trumpf!"

Sophie, Anja und Julia

Gruppenfotos