Algorithmen Projektarbeit

Aus SibiWiki
Zur Navigation springen Zur Suche springen


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.