Algorithmen Projektarbeit: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(8 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 53: Zeile 53:
Als Ideengeber eignet sich u.a. die Seite '''[https://www-i1.informatik.rwth-aachen.de/~algorithmus/liste.php Algorithmus der Woche (RWTH Aachen)]'''.<br/>Einige der Algorithmen werden unten auch genannt.
Als Ideengeber eignet sich u.a. die Seite '''[https://www-i1.informatik.rwth-aachen.de/~algorithmus/liste.php Algorithmus der Woche (RWTH Aachen)]'''.<br/>Einige der Algorithmen werden unten auch genannt.


# '''Scratch:'''<br/>Die folgenden Probleme lassen sich mit Scratch bearbeiten.<br/>''Den ersten Zugriff auf diese Probleme haben SchülerInnen, die in der Q1 nicht mehr Informatik haben.''
# '''Scratch:'''<br/>Die folgenden Probleme lassen sich am besten mit Scratch bearbeiten, weil man eine grafische Oberfläche braucht.
## '''Planetenbahnen zeichnen:'''<br/>''Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann.'' <br/>''[https://de.wikipedia.org/wiki/Newtonsches_Gravitationsgesetz Gravitationsgesetz(Wikipedia)]''
## '''Planetenbahnen zeichnen:'''<br/>''Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann.'' <br/>''[https://de.wikipedia.org/wiki/Newtonsches_Gravitationsgesetz Gravitationsgesetz(Wikipedia)]''
## '''(SEHR SCHWER:) Eine Doppelfeder simulieren:''' <br/>''Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.''
## '''(SEHR SCHWER:) Eine Doppelfeder simulieren:''' <br/>''Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.''
## '''Integrale näherungsweise berechnen mit der Trapezregel:'''<br/>Abschätzung der Genauigkeit mit mathematischen Mitteln.
## '''Pi berechnen mit einem rekursiven Algorithmus:''' <br/>Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit
## '''Ausweg aus einem Labyrinth mit dem Pledge-Algorithmus.<br/>Vergleiche "6. Algorithmus der Woche."
## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]
# '''Simulationen:'''<br/>''Bei Simulationen gehört zur Projektarbeit auch die Abschätzung der Güte der Simulation, das heißt z.B.: Wie groß ist das Konfidenzintervall (von 99%) für das tatsächliche Verhalten des simulierten Ereignisses? Oder: wie oft muss man simulieren, damit die Abweichung vom tatsächlichen Ergebnis (mit einer Wahrscheinlichkeit von 99%) maximal 0,1% beträgt?''<br/>''Dafür braucht man etwas Statistik, die in aller Kürze hier erklärt wird: [[Algorithmen:_Mathematik]].''
# '''Simulationen:'''<br/>''Bei Simulationen gehört zur Projektarbeit auch die Abschätzung der Güte der Simulation, das heißt z.B.: Wie groß ist das Konfidenzintervall (von 99%) für das tatsächliche Verhalten des simulierten Ereignisses? Oder: wie oft muss man simulieren, damit die Abweichung vom tatsächlichen Ergebnis (mit einer Wahrscheinlichkeit von 99%) maximal 0,1% beträgt?''<br/>''Dafür braucht man etwas Statistik, die in aller Kürze hier erklärt wird: [[Algorithmen:_Mathematik]].''
## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''
## '''Kniffel-Berater:'''<br/>''Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?''
## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''
## '''Poker-Berater:'''<br/>''Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?''
## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?'''
## '''Risiko-Berater:'''<br/>''Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?''
## '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)*x<sup>2</sup> + (1/50)*x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
## '''Stau an der Tankstelle:'''<br/>''Es gibt 4 Zapfsäulen, 1x Tanken dauert 5min. Es gibt n Autos. Jedes Auto muss im Schnitt alle 100 Stunden tanken (mal schneller, mal weniger schnell.)''<br/>''Wie viele Autos kann die Tankstelle bedienen, ohne dass es zu Stau kommt?''<br/>''Das kann man am elegantesten mit Multithreading lösen.''
## '''Stau auf der Autobahn:'''<br/>''Zwei Spuren werden an einer Baustelle auf eine Spur zusammengeführt.''<br/>''Welche Auswirkungen hat das Fahrverhalten (insbesondere Geschwindigkeit und Abstand halten) auf die Staubildung?<br/>''Das kann man am elegantesten mit Multithreading lösen.''
## '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
## ''VIELE andere Simulationen sind denkbar!!!'''
## ''VIELE andere Simulationen sind denkbar!!!'''
# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Neighbor-Heuristik zum Lösen des TSP für n>18<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
# '''Divide-And-Conquer Algorithmen'''
## Nullstellenbestimmung der Funktion f(x) = sin(x) mit Divide-And-Conquer
# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]
# '''Fehler-Erkennungs-Algorithmen:'''<br/>zwei ausgewählte darstellen und an Beispielen testen.<br/>[https://de.wikipedia.org/wiki/Fehlerkorrekturverfahren Fehlerkorrekturverfahren(Wikipedia)]
# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.
# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.
# '''Backtracking:'''<br/>Backtracking ist eine Form des systematischen Ausprobierens. Vergleiche [[Backtracking]]
# '''Backtracking:'''<br/>Backtracking ist eine Form des systematischen Ausprobierens. Vergleiche [[Backtracking]]
## '''Rucksackproblem:''' <br>Pareto-optimale Punkte nutzen<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php Algorithmus der Woche]
## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]
## '''Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?'''<br/>[https://en.wikipedia.org/wiki/Graph_coloring Wikipedia (en): Graph Coloring]
## '''Magische 4x4 Quadrate berechnen:'''<br/>Systematisches Probieren z.B. mit Backtracking
## '''Springerproblem:'''<br/>Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. [https://de.wikipedia.org/wiki/Springerproblem Springerproblem (Wikipedia)]
## '''Rucksackproblem:'''<br/>Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy-Algorithmus]
## '''Travelling-Salesman-Problem:'''<br/>Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines [https://en.wikipedia.org/wiki/Greedy_algorithm Greedy-Algorithmus]
# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]
# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche]
Zeile 81: Zeile 76:
# '''Ein Stromnetz optimal planen (Kruskal):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Algorithmus-von-Kruskal-(Wikipedia)]
# '''Ein Stromnetz optimal planen (Kruskal):'''<br/>'''Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal'''<br/>[https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal Algorithmus-von-Kruskal-(Wikipedia)]
# '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche]
# '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche]
# '''Projektwoche: Wie verteilt man die Schüler auf Projekte?'''<br/>1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte und 3 "geht-so"-Projekte angegeben.<br/>Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?<br/>Wie gewährleistet man, dass die Verteilung fair ist?<br/>Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist?
# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
## '''Welche Funktion erfüllt die Differentialgleichung f'(x) = x * f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]
## '''Integrale näherungsweise berechnen mit Trapezen bzw. mit Rechtecken:'''<br/>Vergleich der Konvergenzgeschwindigkeit.
## '''Pi (oder die Eulersche Zahl e) berechnen mit einem geeigneten Algorithmus:''' <br/>Zwei geeignete Algorithmen recherchieren, programmieren und auf Genauigkeit vergleichen.
## '''Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.'''<br/>[https://en.wikipedia.org/wiki/Ternary_search Wikipedia (en): Ternary search]
## '''Welche Funktion erfüllt die Differentialgleichung f''(x) = - f(x) bzw. f'(x) = x + f(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]<br>''Man kann das auch mit Excel angehen!''
## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
## '''Ein Gleichungssystem mit 100 Variablen numerisch lösen.'''
# '''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]
## '''Die Fläche unter der Gaußschen Glockenkurve <math>f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}</math> näherungsweise bestimmen.'''<br/>''Auch Excel ist möglich''
# '''Sortieren mit AVL-Bäumen'''
# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]
# '''Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:'''<br/>[https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus Wikipedia: Bellman-Ford-Algorithmus]
# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]
# '''Maximum Subarray Problem''': Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.'''<br/>[https://en.wikipedia.org/wiki/Maximum_subarray_problem Wikipedia (en): Maximum subarray problem]
# '''Longest common subsequence: Gegeben sind zwei Listen von Wörtern. Finde die längste Teilliste, die in beiden Listen (in der entsprechenden Reihenfolge enthalten ist!'''<br/>[https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example Wikipedia (en): longest common subsequence problem]
# '''Longest common subsequence:'''<br/>Gegeben sind zwei Listen von Wörtern. Finde die längste Teilliste, die in beiden Listen (in der entsprechenden Reihenfolge enthalten ist!'''<br/>[https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example Wikipedia (en): longest common subsequence problem]
# '''Zuordnungsproblem: 90 Taxis sind über eine Stadt verteilt. Jetzt bestellen 90 Kunden ein Taxi. Welches Taxi fährt zu welchem Kunden, so dass die Kunden insgesamt am kürzesten warten müssen?<br/>[https://de.wikipedia.org/wiki/Zuordnungsproblem Wikipedia: Zuordnungsproblem]
# '''Zuordnungsproblem:'''<br/>90 Taxis sind über eine Stadt verteilt. Jetzt bestellen 90 Kunden ein Taxi. Welches Taxi fährt zu welchem Kunden, so dass die Kunden insgesamt am kürzesten warten müssen?<br/>[https://de.wikipedia.org/wiki/Zuordnungsproblem Wikipedia: Zuordnungsproblem]
# '''Vergleichbasiertes Ranking:<br>''' Gegeben sind z.B. 100 Marken. Die Nutzer sollen immer 2 von ihnen vergleichen. Wie kann daraus eine Bewertung der Marken erstellen?<br/>Man braucht dafür den Algorithmus der ELO-Punkte im Schach.<br/>Marc Zuckerberg verwendete diesen Algorithmus für seine (skandalträchtige) Software ''Facemash''.
# '''Vergleichbasiertes Ranking:'''<br> Gegeben sind z.B. 100 Marken. Die Nutzer sollen immer 2 von ihnen vergleichen. Wie kann daraus eine Bewertung der Marken erstellen?<br/>Man braucht dafür den Algorithmus der ELO-Punkte im Schach.<br/>Marc Zuckerberg verwendete diesen Algorithmus für seine (skandalträchtige) Software ''Facemash''.
# '''Monte-Carlo- und Las-Vegas-Algorithmen:'''<br/>Das sind Algorithmen, die Zufall nutzen, um eine beste oder näherungsweise beste Lösung zu finden.
# '''Monte-Carlo- und Las-Vegas-Algorithmen:'''<br/>Das sind Algorithmen, die Zufall nutzen, um eine beste oder näherungsweise beste Lösung zu finden.
## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.
## '''Der Miller-Rabin-Test'''<br/>findet Primzahlen mit mehr als 500 Stellen.
## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''
## '''Das Hubschrauber-Problem:'''<br/>Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?<br/>''"Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".''
# '''Wie schwimmt man am schnellsten quer durch den Rhein?'''<br/>''Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).<br/>Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)*x<sup>2</sup> + (1/50)*x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.''
# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit]
# ''(Das folgende Problem ist ein rein theoretisches, d.h. hier wird gar nicht programmiert!)''<br/>'''P-NP-Problem am Beispiel: ''Lässt sich eine Landkarte mit 3 Farben einfärben?'''''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]

Aktuelle Version vom 1. März 2022, 07:34 Uhr

Auf dieser Seite wird alles Wichtige für die Projektarbeit im Projektkurs Algorithmen im Schuljahr 18/19 zusammengefasst.

Anforderungen an die Projektarbeit

mögliche Gliederung

In der Regel umfasst die Projektarbeit die folgenden Teile:

  1. Abstract
    Im Abstract wird die Arbeit in ca. 1/2 Seite zusammengefasst, d.h.: es werden in aller Kürze die Fragestellung der Arbeit, die Ergebnisse und ihre Relevanz dargestellt.
    Das Abstract dient dazu, dass man als Leser schnell erkennen kann, ob es sich - im Hinblick auf eigene Forschungsinteressen - lohnt, die ganze Arbeit zu lesen.
    Das Abstract steht immer am Anfang der Arbeit, aber geschrieben wird es als Letztes!.
  2. Einleitung
    Die Einleitung führt zum Thema hin, z.B. indem die Bedeutung des Algorithmus aufgezeigt wird.
  3. Beschreibung des Algorithmus
    1. Zweck
    2. Funktionsweise
    3. Vorteile / Nachteile
  4. Laufzeitabschätzung / Genauigkeitsabschätzung für n Elemente
    1. Average Case
    2. Worst Case
  5. Quelltext des Algorithmus, gut erläutert
    Hier wird nicht die ganze Programmierung aufgeführt, sondern nur die für den Algorithmus zentralen Teile der Programmierung!
    Die restliche Programmierung kommt in den Anhang.
  6. Praxistest
    Dokumentation von Beispielläufen des Algorithmus
    1. Average Case
    2. (wenn möglich:) Worst Case
    3. (für Simulationen:) Genauigkeit der Simulation statistisch abschätzen.
  7. Vergleich Theorie - Praxis
    1. ggf.: welche Probleme ergaben sich?
    2. ggf.: Warum ist der Algorithmus in der Praxis langsamer/schneller als in der Theorie?
  8. Resümee
    1. z.B.: Verbesserungsvorschläge
    2. Bedeutung in der Praxis
    3. andere Optionen für das Problem
  9. Anhang
    1. Programmquelltext

formale Anforderungen

Für die Projektarbeit gelten dieselben formalen Anforderungen wie für eine Facharbeit.

Die formalen Anforderungen finden sich hier: SIBI-Homepage: Oberstufe

Außerdem gibt es auf dieser Seite auch Vorlagen für die Formatierung einer Arbeit! (Sowohl MS-Word als auch LibreOffice-Writer.) Am einfachsten lädt man sich die Vorlage runter und schreibt darin seine Arbeit - dann ist die Formatierung "automatisch" richtig.

Teamarbeit?!

  • Man kann - nach Absprache mit Herrn Kaibel - auch zu zweit ein Projekt bearbeiten und abgeben.
  • Voraussetzung dafür ist aber, dass das Team halbwegs "balanciert" ist; es darf nicht so sein, dass eine(r) die ganze Programmierarbeit macht.
  • Die Projektarbeit soll ausführlicher (d.h. mindestens 1,5mal so lang) sein.
  • In der Projektarbeit kennzeichnet dann jeweils einer für bestimmte Teile verantwortlich.

Themen für die Projektarbeit

Hier werden einige Themen vorgeschlagen. Nach Absprache sind natürlich auch ganz andere Themen möglich!

Als Ideengeber eignet sich u.a. die Seite Algorithmus der Woche (RWTH Aachen).
Einige der Algorithmen werden unten auch genannt.

  1. Scratch:
    Die folgenden Probleme lassen sich am besten mit Scratch bearbeiten, weil man eine grafische Oberfläche braucht.
    1. Planetenbahnen zeichnen:
      Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann.
      Gravitationsgesetz(Wikipedia)
    2. (SEHR SCHWER:) Eine Doppelfeder simulieren:
      Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.
  2. Simulationen:
    Bei Simulationen gehört zur Projektarbeit auch die Abschätzung der Güte der Simulation, das heißt z.B.: Wie groß ist das Konfidenzintervall (von 99%) für das tatsächliche Verhalten des simulierten Ereignisses? Oder: wie oft muss man simulieren, damit die Abweichung vom tatsächlichen Ergebnis (mit einer Wahrscheinlichkeit von 99%) maximal 0,1% beträgt?
    Dafür braucht man etwas Statistik, die in aller Kürze hier erklärt wird: Algorithmen:_Mathematik.
    1. Kniffel-Berater:
      Was ist eine optimale Strategie, wenn man nur den oberen Bereich (1-6) füllen will? Wie viele Punkte kann man im Schnitt erwarten?
    2. Poker-Berater:
      Welche Chancen hat man mit einem gegebenen Blatt, das Spiel gegen 3 weitere Spieler zu gewinnen?
    3. Risiko-Berater:
      Wie viele Armeen bleiben übrig, wenn man z.B. mit 23 Armeen 20 Armeen des Gegners angreift?
    4. VIELE andere Simulationen sind denkbar!!!'
  3. Divide-And-Conquer Algorithmen
    1. Nullstellenbestimmung der Funktion f(x) = sin(x) mit Divide-And-Conquer
  4. Travelling Salesman Problem (TSP)
    z.B. Nearest-Insertion-Heuristik und Farthest-Insertion-Heuristik zum Lösen des TSP für viele (d.h. mehr als 20) Städte
    Wikipedia: Problem des Handlungsreisenden
    Wikipedia: Nearest-Neighbor-Heuristik
  5. Fehler-Erkennungs-Algorithmen:
    zwei ausgewählte darstellen und an Beispielen testen.
    Fehlerkorrekturverfahren(Wikipedia)
  6. Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.
    Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.
  7. Backtracking:
    Backtracking ist eine Form des systematischen Ausprobierens. Vergleiche Backtracking
    1. Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?
      Wikipedia (en): Graph Coloring
    2. Springerproblem:
      Der Springer soll auf einem Schachbrett alle Felder ab-"springen", ohne dabei 2x auf dasselbe Feld zu kommen. Springerproblem (Wikipedia)
    3. Rucksackproblem:
      Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines Greedy-Algorithmus
    4. Travelling-Salesman-Problem:
      Vergleich der Laufzeit und der Genauigkeit eines Backtracking- und eines Greedy-Algorithmus
  8. Konvexe Hülle:
    Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
  9. Optimale Verkehrsplanung:
    Maximale Flüsse
    Algorithmus der Woche
  10. Ein Stromnetz optimal planen (Prim):
    Minimale Spannbäume berechnen mit dem Algorithmus von Prim
    Algorithmus-von-Prim-(Wikipedia)
  11. Ein Stromnetz optimal planen (Kruskal):
    Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal
    Algorithmus-von-Kruskal-(Wikipedia)
  12. Suchen in O(1):
    Hashing
    Wikipedia: Hash-Funktion
    Algorithmus der Woche
  13. Numerische Verfahren:
    Ziel der Numerik ist es "das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."
    Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen
    Wikipedia: Liste numerischer Verfahren
    1. Integrale näherungsweise berechnen mit Trapezen bzw. mit Rechtecken:
      Vergleich der Konvergenzgeschwindigkeit.
    2. Pi (oder die Eulersche Zahl e) berechnen mit einem geeigneten Algorithmus:
      Zwei geeignete Algorithmen recherchieren, programmieren und auf Genauigkeit vergleichen.
    3. Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.
      Wikipedia (en): Ternary search
    4. Welche Funktion erfüllt die Differentialgleichung f(x) = - f(x) bzw. f'(x) = x + f(x) ?
      Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.
      Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen
      Man kann das auch mit Excel angehen!
    5. Ein Gleichungssystem mit 100 Variablen numerisch lösen.
    6. Die Fläche unter der Gaußschen Glockenkurve [math]\displaystyle{ f(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2} }[/math] näherungsweise bestimmen.
      Auch Excel ist möglich
  14. Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:
    Wikipedia: Bellman-Ford-Algorithmus
  15. Maximum Subarray Problem: Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.
    Wikipedia (en): Maximum subarray problem
  16. Longest common subsequence:
    Gegeben sind zwei Listen von Wörtern. Finde die längste Teilliste, die in beiden Listen (in der entsprechenden Reihenfolge enthalten ist!
    Wikipedia (en): longest common subsequence problem
  17. Zuordnungsproblem:
    90 Taxis sind über eine Stadt verteilt. Jetzt bestellen 90 Kunden ein Taxi. Welches Taxi fährt zu welchem Kunden, so dass die Kunden insgesamt am kürzesten warten müssen?
    Wikipedia: Zuordnungsproblem
  18. Vergleichbasiertes Ranking:
    Gegeben sind z.B. 100 Marken. Die Nutzer sollen immer 2 von ihnen vergleichen. Wie kann daraus eine Bewertung der Marken erstellen?
    Man braucht dafür den Algorithmus der ELO-Punkte im Schach.
    Marc Zuckerberg verwendete diesen Algorithmus für seine (skandalträchtige) Software Facemash.
  19. Monte-Carlo- und Las-Vegas-Algorithmen:
    Das sind Algorithmen, die Zufall nutzen, um eine beste oder näherungsweise beste Lösung zu finden.
    1. Der Miller-Rabin-Test
      findet Primzahlen mit mehr als 500 Stellen.
    2. Das Hubschrauber-Problem:
      Es gibt 500 weit verstreute Häuser. Wo sollte der Standort für einen Hubschrauber sein, damit jedes Haus möglichst schnell erreicht werden kann?
      "Kleinster umschließender Kreis", vgl. "42. Algorithmus der Woche".
  20. Wie schwimmt man am schnellsten quer durch den Rhein?
    Das Problem ist, dass die Strömung in der Mitte stärker wird, d.h. ab wann sollte man einfach "quer" schwimmen (und dann am Strand wieder zurücklaufen).
    Folgende Grundannahmen: Der Rhein ist 400m breit. Die Strömungsgeschwindigkeit (in m/s) wird durch folgende Funktion gegeben: f(x) = -(1/20000)*x2 + (1/50)*x (D.h. in der Rheinmitte ist die Strömung dann 2m/s.) Der Schwimmer hat eine Geschwindigkeit von 1,5m/s (das schafft ein Leistungssportler auf 400m). Wenn er am Ufer zurücklaufen muss, ist seine Geschwindigkeit auch 1,5m/s.
  21. Wie macht man die beste Ausbeute an Glücksspielautomaten?
    Das Multi-Armed-Bandit Problem:
    Wikipedia (en): Multi-Armed-Bandit
  22. (Das folgende Problem ist ein rein theoretisches, d.h. hier wird gar nicht programmiert!)
    P-NP-Problem am Beispiel: Lässt sich eine Landkarte mit 3 Farben einfärben?
    Zur Klasse P gehören alle Entscheidungsprobleme, die in polynomieller Zeit gelöst werden können.
    Zur Klasse NP gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit verifiziert werden kann.

    Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört.
    Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.
    Das ist eine rein theoretische Arbeit!
    Wikipedia: Färbung eines Graphen
    Erläuterung von P und NP
    Wikipedia: 21 NP-vollständige Probleme