Algorithmen Projektarbeit: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
| Zeile 6: | Zeile 6: | ||
# '''Rucksackproblem:''' <br>Pareto-optimale Punkte nutzen<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php Algorithmus der Woche] | # '''Rucksackproblem:''' <br>Pareto-optimale Punkte nutzen<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php Algorithmus der Woche] | ||
# '''Wie finde ich den Ausweg aus einem Labyrinth?''' <br>Pledge-Algorithmus mit Kara programmieren! <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo6.php Algorithmus der Woche] | # '''Wie finde ich den Ausweg aus einem Labyrinth?''' <br>Pledge-Algorithmus mit Kara programmieren! <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo6.php Algorithmus der Woche]<br>Das lässt sich auch mit Scratch programmieren. | ||
# '''Ein Stromnetz optimal planen:''' <br>Minimaler Spannbaum <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php Algorithmus der Woche] | # '''Ein Stromnetz optimal planen:''' <br>Minimaler Spannbaum <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php Algorithmus der Woche] | ||
# '''Facemash:''' <br>Wie erstellt man ein Ranking mithilfe des Vergleichs von Paaren? <br>[https://de.wikipedia.org/wiki/Schweizer_System Wikipedia: Schweizer System] <br>[http://sibi-honnef.de/informatikag/match/index.php Fahrzeug-Ranking am SIBI] | # '''Facemash:''' <br>Wie erstellt man ein Ranking mithilfe des Vergleichs von Paaren? <br>[https://de.wikipedia.org/wiki/Schweizer_System Wikipedia: Schweizer System] <br>[http://sibi-honnef.de/informatikag/match/index.php Fahrzeug-Ranking am SIBI] | ||
# '''Wie werden Internetseiten gerankt?''' <br>Page-Rank-Algorithmus <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo10.php Algorithmus der Woche] Diesen Algorithmus könnte man auf sibi-wiki.de anwenden. | # '''Wie werden Internetseiten gerankt?''' <br>Page-Rank-Algorithmus <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo10.php Algorithmus der Woche] Diesen Algorithmus könnte man auf sibi-wiki.de anwenden. | ||
# '''Der Computer spielt "Vier gewinnt":''' <br>Minimax-Algorithmus <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo19.php Algorithmus der Woche] | # '''Der Computer spielt "Vier gewinnt":''' <br>Minimax-Algorithmus <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo19.php Algorithmus der Woche] | ||
# '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit] | # '''Wie macht man die beste Ausbeute an Glücksspielautomaten?''' <br>Das Multi-Armed-Bandit Problem: <br>[https://en.wikipedia.org/wiki/Multi-armed_bandit Wikipedia (en): Multi-Armed-Bandit] | ||
# '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche] | # '''Optimale Verkehrsplanung:''' <br>Maximale Flüsse<br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo23.php Algorithmus der Woche] | ||
# '''Wie findet man in einem Text möglichst schnell alle Vorkommen eines Wortes?''' <br>String-Matching-Algorithmen<br>[https://de.wikipedia.org/wiki/String-Matching-Algorithmus Wikipedia: String-Matching-Algorithmus] | # '''Wie findet man in einem Text möglichst schnell alle Vorkommen eines Wortes?''' <br>String-Matching-Algorithmen<br>[https://de.wikipedia.org/wiki/String-Matching-Algorithmus Wikipedia: String-Matching-Algorithmus] | ||
# '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche] | # '''Suchen in O(1):'''<br>Hashing <br>[https://de.wikipedia.org/wiki/Hashfunktion Wikipedia: Hash-Funktion] <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo34.php Algorithmus der Woche] | ||
# '''Wo ist der beste Standort für einen Rettungshubschrauber?''' <br>Kleinster umschließender Kreis. <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo42.php Algorithmus der Woche] | # '''Wo ist der beste Standort für einen Rettungshubschrauber?''' <br>Kleinster umschließender Kreis. <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo42.php Algorithmus der Woche] | ||
# '''Der kürzeste Zaun um einen Wald:''' <br>Konvexe Hülle. <br>[https://de.wikipedia.org/wiki/Konvexe_Hülle Wikipedia: Konvexe Hülle] | # '''Der kürzeste Zaun um einen Wald:''' <br>Konvexe Hülle. <br>[https://de.wikipedia.org/wiki/Konvexe_Hülle Wikipedia: Konvexe Hülle] | ||
# '''Große Primzahlen (500stellig!) finden:''' <br>Der Miller-Rabin-Test <br>[https://de.wikipedia.org/wiki/Miller-Rabin-Test Wikipedia: Miller-Rabin-Test] | # '''Große Primzahlen (500stellig!) finden:''' <br>Der Miller-Rabin-Test <br>[https://de.wikipedia.org/wiki/Miller-Rabin-Test Wikipedia: Miller-Rabin-Test] | ||
# '''Flächenberechnung mit dem Monte-Carlo-Algorithmus'''<br>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.<br>Daran schließt sich die Frage an, wie effektiv der Algorithmus ist. | |||
Version vom 2. Oktober 2015, 18:14 Uhr
Themen für die Projektarbeit
Hier werden einige Themen vorgeschlagen. Nach Absprache sind natürlich auch ganz andere Themen möglich!
- Rucksackproblem:
Pareto-optimale Punkte nutzen
Algorithmus der Woche - Wie finde ich den Ausweg aus einem Labyrinth?
Pledge-Algorithmus mit Kara programmieren!
Algorithmus der Woche
Das lässt sich auch mit Scratch programmieren. - Ein Stromnetz optimal planen:
Minimaler Spannbaum
Algorithmus der Woche - 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 - Der kürzeste Zaun um einen Wald:
Konvexe Hülle.
Wikipedia: Konvexe Hülle - 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.