Algorithmen Projektarbeit

Themen für die Projektarbeit

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

1. Rucksackproblem:
   Pareto-optimale Punkte nutzen
   Algorithmus der Woche
2. Wie finde ich den Ausweg aus einem Labyrinth?
   Pledge-Algorithmus mit Kara programmieren!
   Algorithmus der Woche
   Das lässt sich auch mit Scratch programmieren.
3. Ein Stromnetz optimal planen:
   Minimaler Spannbaum
   Algorithmus der Woche
4. Facemash:
   Wie erstellt man ein Ranking mithilfe des Vergleichs von Paaren?
   Wikipedia: Schweizer System
   Fahrzeug-Ranking am SIBI
5. Wie werden Internetseiten gerankt?
   Page-Rank-Algorithmus
   Algorithmus der Woche Diesen Algorithmus könnte man auf sibi-wiki.de anwenden.
6. Der Computer spielt "Vier gewinnt":
   Minimax-Algorithmus
   Algorithmus der Woche
7. Wie macht man die beste Ausbeute an Glücksspielautomaten?
   Das Multi-Armed-Bandit Problem:
   Wikipedia (en): Multi-Armed-Bandit
8. Optimale Verkehrsplanung:
   Maximale Flüsse
   Algorithmus der Woche
9. Wie findet man in einem Text möglichst schnell alle Vorkommen eines Wortes?
   String-Matching-Algorithmen
   Wikipedia: String-Matching-Algorithmus
10. Suchen in O(1):
    Hashing
    Wikipedia: Hash-Funktion
    Algorithmus der Woche
11. Wo ist der beste Standort für einen Rettungshubschrauber?
    Kleinster umschließender Kreis.
    Algorithmus der Woche
12. Der kürzeste Zaun um einen Wald:
    Konvexe Hülle.
    Wikipedia: Konvexe Hülle
13. Große Primzahlen (500stellig!) finden:
    Der Miller-Rabin-Test
    Wikipedia: Miller-Rabin-Test
14. 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.