Algorithmen Projektarbeit

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
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: Facharbeit

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.

Themen für die Projektarbeit

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

1. Ameisenalgorithmus zur Lösung des Travelling-Salesman-Problems:
   Ameisenalgorithmus(Wikipedia)
2. Greedy-Algorithmus am Beispiel Wechselgeld rausgeben:
   Beispiel: 3,47 Euro soll mit möglichst wenig Münzen herausgegeben werden.
   Zu zeigen sind auch die Grenzen des Greedy-Algorithmus in diesem Beispiel, d.h. dass er nicht immer eine ideale Lösung findet.
3. 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.
   Python / Java
4. 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.
   Scratch!
5. Eine Doppelfeder simulieren:
   Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.
   Scratch!
6. Rucksackproblem:
   Pareto-optimale Punkte nutzen
   Algorithmus der Woche
7. Ein Stromnetz optimal planen:
   Minimaler Spannbaum
   Algorithmus der Woche
8. Konvexe Hülle:
   Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
9. Den Zauberwürfel lösen:
   Einen Algorithmus zum Lösen des Zauberwürfels programmieren.
10. Travelling Salesman Problem (TSP)
    z.B. Nearest-Neighbor-Heuristik zum Lösen des TSP für n>18
    Wikipedia: Problem des Handlungsreisenden
    Wikipedia: Nearest-Neighbor-Heuristik
11. Wie macht man die beste Ausbeute an Glücksspielautomaten?
    Das Multi-Armed-Bandit Problem:
    Wikipedia (en): Multi-Armed-Bandit
12. Optimale Verkehrsplanung:
    Maximale Flüsse
    Algorithmus der Woche
13. Minimale Spannbäume berechnen mit dem Algorithmus von Prim
    Algorithmus-von-Prim-(Wikipedia)
14. Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal
    Algorithmus-von-Kruskal-(Wikipedia)
15. Simulationen:
    1. Mit welcher Wahrscheinlichkeit würfelt man beim Spiel Kniffel einen Kniffel (d.h. 5 Gleiche?).
       Zu berücksichtigen ist, dass man bei Kniffel 3x nicht passende Zahlen zurücklegen kann.
       Die Qualität des Ergebnisses muss man geeignet abschätzen, z.B. mit statistischen Verfahren.
       Einfache Programmierung, dafür muss man mehr Mathematik anwenden.
    2. Welche Chancen hat man bei "Risiko", wenn man mit 23 Armeen 20 Armeen angreift?
    3. Flugzeuge überbuchen:
       Fluggesellschaften wissen, dass ca. 5 Prozent der Fluggäste nicht erscheinen.
       Wie viele Plätze können sie in einem Flugzeug mit 250 Sitzplätzen verkaufen, damit es mit einer Wahrscheinlichkeit von 95% nicht überbucht ist?
       Wie viele Plätze können sie verkaufen, um den Profit zu optimieren? (Annahme: Für jeden überbuchten Kunden muss man den doppelten Flugpreis als Schadensersatz einkalkulieren.)
    4. VIELE andere Simulationen sind denkbar!!!'
16. Suchen in O(1):
    Hashing
    Wikipedia: Hash-Funktion
    Algorithmus der Woche
17. Pi berechnen mit einem Monte-Carlo-Algorithmus
    Die Programmierung ist sehr einfach - hier wäre der Schwerpunkt mathematisch: Wie oft muss man "schießen", um mit 95%er Wahrscheinlichkeit eine Abweichung von 1% (bzw. 0,1% oder 0,001%) zu erzielen. D.h. man braucht hier Statistik.
    Daran schließt sich die Frage an, wie effektiv der Algorithmus ist.
    Scratch!
18. Pi berechnen mit einem rekursiven Algorithmus:
    Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit
19. Integrale näherungsweise berechnen mit der Trapezregel:
    Abschätzung der Genauigkeit
20. Magische Quadrate berechnen:
    Systematisches Probieren.
21. Projektwoche: Wie verteilt man die Schüler auf Projekte?
    1000 Schüler und 50 Projekte; an jedem Projekt dürfen max. 25 Schüler teilnehmen. Jeder Schüler hat 3 Wunschprojekte angegeben.
    Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?
22. Welche Funktion erfüllt die Differentialgleichung y'(x) = y²(x) + y(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
23. 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
24. Lässt sich eine Landkarte mit 3 Farben einfärben? - das P-NP-Problem
    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
25. Sortieren mit AVL-Bäumen
    Dafür braucht man Java!