Facharbeit Mathe/Informatik

Hallo,
ich hab eben diesen http://www.c-plusplus.net/forum/viewtopic-var-t-is-160087.html
Beitrag gelesen und mir ist aufgefallen, dass ich ebenfalls noch ein Facharbeitsthema suche. Ich hatte jedoch mehr an etwas aus dem Bereich Informatik-Mathematik gedacht, also am besten etwas, das beides mit einander vermischt.
Ich hätte jetzt was in Richtung Graphentheorie im Kopf, jedoch weiß ich kein explizietes Thema. Ich denke das TSP ist entweder zu umfangreich oder, wenn man es entsorechend kürzt, eher langweilig, da man dann ja einfach auf die unterschielichen Arten der Näherung ans Optimum eingeht.

Weiß jemand vllt ein interessantes Thema?

Jester

the unknown schrieb:

Ich hätte jetzt was in Richtung Graphentheorie im Kopf, jedoch weiß ich kein explizietes Thema. Ich denke das TSP ist entweder zu umfangreich oder, wenn man es entsorechend kürzt, eher langweilig, da man dann ja einfach auf die unterschielichen Arten der Näherung ans Optimum eingeht.

Könnte aber gehen, gibt auch schöne Approximationen mit beweisbarem Gütegrad. Die sind auch nicht zu schwer zu verstehen.
Ansonsten gibt's da natürlich noch Matchings, kürzeste Wege (Routenplanung) etc.

Turing

Interessantes Thema: "Lineare Optimierung"
Durchführung z.B. Simplexalgorithmus

Für Schüler auf jeden Fall schon zu verstehen.

Taurin

Zum TSP fallen mir spontan noch Themen wie P vs. NP, Berechenbarkeit, Turing-Maschine, Busy-Beaver ein. Wenn du das TSP spannend findest, musst du ja nicht zwangsläufig eine Lösung anbieten, sondern kannst es in einen anderen Kontext einbetten (TSP ist ja NP-hart)

Ich habe gerade
Constraint Processing | ISBN: 1558608907 und Automated Planning | ISBN: 1558608567
in der Hand.

Das sind scheißgute Bucher, die ich jedem Informatikstudenten empfehlen kann.

Thema die enthalten sind, die dich vielleicht interessieren:

- Arc-Consistency
- Directionale Konsistenz
- Acyclic Networks
- Tree Decomposion Methods
- Probabilistic Networks

- Hierachical Task Network Planing
- Markov Decision Process
- Planning-Graph Techniques

Prof84@work schrieb:

Thema die enthalten sind, die dich vielleicht interessieren:

- Arc-Consistency
- Directionale Konsistenz
- Acyclic Networks
- Tree Decomposion Methods
- Probabilistic Networks

- Hierachical Task Network Planing
- Markov Decision Process
- Planning-Graph Techniques

lol. ich musste gerade an den bullshit bingo thread denken

Hallo,
vielen Dank für die Vorschläge, da sind wirklich einige bei, die mir gar nicht in den sinn gekommen sind.
Jetzt ist mir noch ein anderes Thema eingefallen ;): 4-Farben-/5-Farbenproblem.
5 Farben deshalb, weil die Lösung des 4-Farbenproblems doch sehr schwer/kompliziert ausgefallen sein dürfte
Inwieweit kann man diese Thema denn in eine, ich glaube, 15-20 seitige Facharbeit unterbringen? (uns wurde noch nicht viel zu den Facharbeiten allgemein gesagt, weil wir auch noch zeit haben die auszufertigen, ist also noch gar keine akute Sache, nur kann man sich sicher nicht zu früh mit dem entsprechenden Thema beschäftigen, vor allem, wenn man sich da noch einarbeiten muss)
MfG

Jester

Den 5-farben Beweis haben wir in ner Vorlesung recht gut in 1,5h geschafft (inklusive Analyse, wo das Verfahren bei 4 Farben schief geht). Allerdings waren wir auch keine Anfänger mehr. Ich halte den Beweis aber nicht für super schwierig. Außerdem ist er recht schön geometrisch.

Korte, Vygen: Combinatorial Optimization