Algorithmen Projektarbeit
Version vom 24. September 2018, 19:48 Uhr von Akaibel (Diskussion | Beiträge) (→Themen für die Projektarbeit)
Diese Seite wird noch überarbeitet - sowohl im Hinblick auf die Algorithmen als auch auf die formalen Anforderungen!
Anforderungen an die Projektarbeit
mögliche Gliederung
In der Regel umfasst die Projektarbeit die folgenden Teile:
- 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!. - Einleitung
Die Einleitung führt zum Thema hin, z.B. indem die Bedeutung des Algorithmus aufgezeigt wird. - Beschreibung des Algorithmus
- Zweck
- Funktionsweise
- Vorteile / Nachteile
- Laufzeitabschätzung / Genauigkeitsabschätzung für n Elemente
- Average Case
- Worst Case
- 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. - Praxistest
Dokumentation von Beispielläufen des Algorithmus- Average Case
- (wenn möglich:) Worst Case
- Vergleich Theorie - Praxis
- ggf.: welche Probleme ergaben sich?
- ggf.: Warum ist der Algorithmus in der Praxis langsamer/schneller als in der Theorie?
- Resümee
- z.B.: Verbesserungsvorschläge
- Bedeutung in der Praxis
- andere Optionen für das Problem
- Anhang
- 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!
- Ameisenalgorithmus zur Lösung des Travelling-Salesman-Problems:
Ameisenalgorithmus(Wikipedia)
- Fehler-Erkennungs-Algorithmen:
zwei ausgewählte darstellen und an Beispielen testen.
Fehlerkorrekturverfahren(Wikipedia) - 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 (d.h. dass er nicht immer eine ideale Lösung findet) und andere Anwendungsbeispiele für Greedy-Algorithmen. - 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 - 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!
Gravitationsgesetz(Wikipedia) - Eine Doppelfeder simulieren:
Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.
Scratch! - Rucksackproblem:
Pareto-optimale Punkte nutzen
Algorithmus der Woche - Ein Stromnetz optimal planen:
Minimaler Spannbaum
Algorithmus der Woche - Konvexe Hülle:
Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen. - Den Zauberwürfel lösen:
Einen Algorithmus zum Lösen des Zauberwürfels programmieren. - 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 - Wie macht man die beste Ausbeute an Glücksspielautomaten?
Das Multi-Armed-Bandit Problem:
Wikipedia (en): Multi-Armed-Bandit - Optimale Verkehrsplanung:
Maximale Flüsse
Algorithmus der Woche - Minimale Spannbäume berechnen mit dem Algorithmus von Prim
Algorithmus-von-Prim-(Wikipedia) - Minimale Spannbäume berechnen mit dem Algorithmus von Kruskal
Algorithmus-von-Kruskal-(Wikipedia) - 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.- Mit welcher Wahrscheinlichkeit würfelt man beim Spiel Kniffel eine kleine Straße (d.h. vier aufeinanderfolgende Zahlen?)?.
Bei Kniffel würfelt man mit 5 Würfeln. Man würfelt dreimal und kann nicht passende Zahlen zurücklegen. - Welche Chancen hat man bei "Risiko", wenn man mit 23 Armeen 20 Armeen angreift?
- 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.) - Bestellungen simulieren:
Für einen Großauftrag von 10.000 Computern müssen Grafikkarten bestellt werden: Jede Grafikkarte kostet 80€. Der Hersteller gibt an, dass 1% der Grafikkarten unbrauchbar sind. Laut Liefervertrag müssen unbrauchbare Grafikkarten nicht bezahlt werden. Wenn ein Computer wegen der fehlenden Grafikkarte nicht rechtzeitig geliefert werden kann, dann bedeutet das einen Verlust von 300€. Wie viele Grafikkarten bestellt man am besten, um den Gewinn zu maximieren? - 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. - VIELE andere Simulationen sind denkbar!!!'
- Mit welcher Wahrscheinlichkeit würfelt man beim Spiel Kniffel eine kleine Straße (d.h. vier aufeinanderfolgende Zahlen?)?.
- Suchen in O(1):
Hashing
Wikipedia: Hash-Funktion
Algorithmus der Woche - Pi berechnen mit einem rekursiven Algorithmus:
Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit - Integrale näherungsweise berechnen mit der Trapezregel:
Abschätzung der Genauigkeit mit mathematischen Mitteln. - Magische Quadrate berechnen:
Systematisches Probieren. - 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 und 3 "geht-so"-Projekte angegeben.
Wie verteilt man die Schüler, so dass möglichst viele in ein Wunschprojekt kommen?
Wie gewährleistet man, dass die Verteilung fair ist?
Anhand welcher Kriterien entscheidet man, ob eine Verteilung "gut" ist? - Welche Funktion erfüllt die Differentialgleichung 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 - 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 - 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 - Sortieren mit AVL-Bäumen
Dafür braucht man Java! - Bestimmung des kürzesten Weges von A nach B in einem Graph mit dem Algorithmus von Bellman-Ford:
Wikipedia: Bellman-Ford-Algorithmus - Maximum Subarray Problem: Aus einer Liste von Zahlen die Teilliste herausfinden, deren Summe maximal ist.
Wikipedia (en): Maximum subarray 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?
Wikipedia: Zuordnungsproblem - Graphen so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben: Wie viele Farben braucht man dafür?
Wikipedia (en): Graph Coloring - Ternary Search: Die Suche nach einem Maximum in einer Funktion, die überall rechts gekrümmt ist.
Wikipedia (en): Ternary search - 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