Algorithmen Projektarbeit
Version vom 8. November 2015, 18:03 Uhr von Akaibel (Diskussion | Beiträge) (→Themen für die Projektarbeit)
Anforderungen an die Projektarbeit
mögliche Gliederung
In der Regel umfasst die Projektarbeit die folgenden Teile:
- 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
- Praxistest
- Dokumentation von Beispielläufen des Algorithmus
- Average Case
- (wenn möglich:) Worst Case
- Dokumentation von Beispielläufen des Algorithmus
- Vergleich Theorie - Praxis
- ggf.: welche Probleme ergaben sich?
- ggf.: Warum ist der Algorithmus in der Praxis langsamer/schneller als in der Theorie?
- Resumee
- z.B.: Verbesserungsvorschläge
- Bedeutung in der Praxis
- andere Optionen für das Problem
- Programmquelltext (-> Anhang)
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!
- Kürzeste Abstände berechnen:
Welchen Abstand haben die Graphen von
f(x) = (x-4)2+2 und g(x) = -(x-1)2+3 ?
Einen geeigneten Approximationsalgorithmus entwickeln! - Rucksackproblem:
Pareto-optimale Punkte nutzen
Algorithmus der Woche - Wie finde ich den Ausweg aus einem Labyrinth?
Pledge-Algorithmus mit Kara oder mit Scratch programmieren!
Algorithmus der Woche - Ein Stromnetz optimal planen:
Minimaler Spannbaum
Algorithmus der Woche - 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 - Facemash:
Wie erstellt man ein Ranking mithilfe des Vergleichs von Paaren?
Wikipedia: Schweizer System
Fahrzeug-Ranking am SIBI - Wie werden Internetseiten gerankt?
Page-Rank-Algorithmus
Algorithmus der Woche Diesen Algorithmus könnte man auf sibi-wiki.de anwenden. - Der Computer spielt "Vier gewinnt":
Minimax-Algorithmus
Algorithmus der Woche - 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 - Wie findet man in einem Text möglichst schnell alle Vorkommen eines Wortes?
String-Matching-Algorithmen
Wikipedia: String-Matching-Algorithmus - Suchen in O(1):
Hashing
Wikipedia: Hash-Funktion
Algorithmus der Woche - Wo ist der beste Standort für einen Rettungshubschrauber?
Kleinster umschließender Kreis.
Algorithmus der Woche - Große Primzahlen (500stellig!) finden:
Der Miller-Rabin-Test
Wikipedia: Miller-Rabin-Test - Flächenberechnung mit dem 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. - Welche Funktion erfüllt die Differentialgleichung y'(x) = y2(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 - 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 - automatische Troll-Erkennung?!
Als Troll bezeichnet man im Netzjargon eine Person, welche Kommunikation im Internet fortwährend und auf destruktive Weise dadurch behindert, dass sie Beiträge verfasst, die sich auf die Provokation anderer Gesprächsteilnehmer beschränken und keinen sachbezogenen und konstruktiven Beitrag zur Diskussion enthalten. Dies erfolgt mit der Motivation, eine Reaktion der anderen Teilnehmer zu erreichen. (Definition aus Wikipedia: Troll (Netzkultur))
Wired.de: Ein Algorithmus, der Trolle erkennt
Antisocial Behavior in Online Discussion Communities (PDF) - 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