Algorithmen Projektarbeit: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 39: Zeile 39:
=Themen für die Projektarbeit=
=Themen für die Projektarbeit=
Hier werden einige Themen vorgeschlagen. Nach Absprache sind natürlich auch ganz andere Themen möglich!
Hier werden einige Themen vorgeschlagen. Nach Absprache sind natürlich auch ganz andere Themen möglich!
 
# '''Aus einer Liste von 1.000.000 Codes möglichst schnell den häufigsten finden.'''<br/>Dafür braucht man Hashmaps, d.h. das Hashing-Verfahren muss erklärt werden.<br/>Python / Java
# '''Kürzeste Abstände berechnen:'''<br>Welchen Abstand haben die Graphen von <br>f(x) = (x-4)<sup>2</sup>+2 und g(x) = -(x-1)<sup>2</sup>+3 ?<br>Einen geeigneten Approximationsalgorithmus entwickeln!
# '''Planetenbahnen zeichnen:'''<br/>Aus den Gesetzen der Schwerkraft kann man Näherungen gewinnen, so dass man (näherungsweise) Schritt für Schritt eine Planetenbahn zeichnen kann. <br/>Scratch!
# '''Eine Doppelfeder simulieren:''' <br/>Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.<br/>Scratch!
# '''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 oder mit Scratch programmieren! <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo6.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]
# '''Ein Stromnetz optimal planen:''' <br>Minimaler Spannbaum <br>[http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php Algorithmus der Woche]
# '''Konvexe Hülle:''' <br/>Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
# '''Den Zauberwürfel lösen:'''<br/>Einen Algorithmus zum Lösen des Zauberwürfels programmieren.
# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Neighbor-Heuristik zum Lösen des TSP für n>18<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
# '''Travelling Salesman Problem (TSP)'''<br>z.B. Nearest-Neighbor-Heuristik zum Lösen des TSP für n>18<br>[https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Asymmetrisches_und_symmetrisches_TSP Wikipedia: Problem des Handlungsreisenden]<br>[https://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Wikipedia: Nearest-Neighbor-Heuristik]
# '''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.
# '''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]
# '''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]<br>[https://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/fakultaet/programmierpraktikum/2009_ss_aufgabenstellung.pdf Lösung des Kernproblems]
# '''Pi berechnen mit einem 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.<br/>Scratch!
# '''Große Primzahlen (500stellig!) finden:''' <br>Der Miller-Rabin-Test <br>[https://de.wikipedia.org/wiki/Miller-Rabin-Test Wikipedia: Miller-Rabin-Test]
# '''Pi berechnen mit einem rekursiven Algorithmus:''' <br/>Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit
# '''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.
# '''Welche Funktion erfüllt die Differentialgleichung y'(x) = y<sup>2</sup>(x) + y(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]
# '''Welche Funktion erfüllt die Differentialgleichung y'(x) = y<sup>2</sup>(x) + y(x) ?'''<br>Für Differentialgleichungen dieser Art gibt es numerische Verfahren, die (gute!) näherungsweise Lösungen ausgeben.<br>[https://de.wikipedia.org/wiki/Gewöhnliche_Differentialgleichung#Numerische_Verfahren Wikipedia: Numerische Verfahren für gewöhnliche Differentialgleichungen]
# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
# '''Numerische Verfahren''':<br>Ziel der Numerik ist es ''"das eigentlich Unberechenbare zu berechnen, und das in Lichtgeschwindigkeit."''<br>Es gibt SEHR unterschiedliche numerische Verfahren für SEHR VIELE unterschiedliche Problemstellungen<br>[https://de.wikipedia.org/wiki/Liste_numerischer_Verfahren Wikipedia: Liste numerischer Verfahren]
# '''automatische Troll-Erkennung?!'''<br>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 [https://de.wikipedia.org/wiki/Troll_(Netzkultur) Wikipedia: Troll (Netzkultur)])<br>[https://www.wired.de/collection/latest/ein-algorithmus-der-trolle-erkennt Wired.de: Ein Algorithmus, der Trolle erkennt]<br>[http://arxiv.org/pdf/1504.00680v1.pdf Antisocial Behavior in Online Discussion Communities (PDF)]
# '''Lässt sich eine Landkarte mit 3 Farben einfärben? - das P-NP-Problem'''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]
# '''Lässt sich eine Landkarte mit 3 Farben einfärben? - das P-NP-Problem'''<br>''Zur Klasse '''P''' gehören alle Entscheidungsprobleme, die in polynomieller Zeit '''gelöst''' werden können.<br>Zur Klasse '''NP''' gehören alle Entscheidungsprobleme, bei denen die Antwort "JA" in polynomieller Zeit '''verifiziert''' werden kann.'' <br>Es soll aufgezeigt werden, dass das 3-Farben-Problem nicht zur Klasse P, aber zur Klasse NP gehört. <br>Außerdem soll die Bedeutung von NP-vollständigen Problemen für die Algorithmik an diesem Beispiel erläutert werden.<br>''Das ist eine rein theoretische Arbeit!''<br>[https://de.wikipedia.org/wiki/Färbung_(Graphentheorie) Wikipedia: Färbung eines Graphen]<br>[http://www14.in.tum.de/lehre/2008WS/ea/EA-12.pdf Erläuterung von P und NP]<br>[https://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme Wikipedia: 21 NP-vollständige Probleme]

Version vom 12. Dezember 2016, 17:37 Uhr


Anforderungen an die Projektarbeit

mögliche Gliederung

In der Regel umfasst die Projektarbeit die folgenden Teile:

  1. 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!.
  2. Einleitung
    Die Einleitung führt zum Thema hin, z.B. indem die Bedeutung des Algorithmus aufgezeigt wird.
  3. Beschreibung des Algorithmus
    1. Zweck
    2. Funktionsweise
    3. Vorteile / Nachteile
  4. Laufzeitabschätzung / Genauigkeitsabschätzung für n Elemente
    1. Average Case
    2. Worst Case
  5. 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.
  6. Praxistest
    Dokumentation von Beispielläufen des Algorithmus
    1. Average Case
    2. (wenn möglich:) Worst Case
  7. Vergleich Theorie - Praxis
    1. ggf.: welche Probleme ergaben sich?
    2. ggf.: Warum ist der Algorithmus in der Praxis langsamer/schneller als in der Theorie?
  8. Resümee
    1. z.B.: Verbesserungsvorschläge
    2. Bedeutung in der Praxis
    3. andere Optionen für das Problem
  9. Anhang
    1. 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!

  1. 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
  2. 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!
  3. Eine Doppelfeder simulieren:
    Aus physikalischen Gesetzen das Verhalten einer Doppelfeder näherungsweise darstellen.
    Scratch!
  4. Rucksackproblem:
    Pareto-optimale Punkte nutzen
    Algorithmus der Woche
  5. Ein Stromnetz optimal planen:
    Minimaler Spannbaum
    Algorithmus der Woche
  6. Konvexe Hülle:
    Die Konvexe Hülle (d.h. "Umrandung") einer Punktmenge möglichst schnell bestimmen.
  7. Den Zauberwürfel lösen:
    Einen Algorithmus zum Lösen des Zauberwürfels programmieren.
  8. 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
  9. Wie macht man die beste Ausbeute an Glücksspielautomaten?
    Das Multi-Armed-Bandit Problem:
    Wikipedia (en): Multi-Armed-Bandit
  10. Optimale Verkehrsplanung:
    Maximale Flüsse
    Algorithmus der Woche
  11. Suchen in O(1):
    Hashing
    Wikipedia: Hash-Funktion
    Algorithmus der Woche
  12. Pi berechnen mit einem 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.
    Scratch!
  13. Pi berechnen mit einem rekursiven Algorithmus:
    Einen geeigneten rekursiven Algorithmus recherchieren, seine Herleitung, Genauigkeit
  14. 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
  15. 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
  16. 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
Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Algorithmen_Projektarbeit&oldid=2395“