Bundeswettbewerb Informatik - nur für Genies?
-
Hallo,
ich hab mir gedacht, ich könnte so einigermaßen gut programmieren und mal auf der Seite http://www.bwinf.de vorbeigeschaut. Seitdem bin ich kurz vorm Verzweifeln. Abgesehen davon, dass ich keine einzige Aufgabe auf Anhieb umsetzen könnte, find ich besonders die 2. Aufgabe in der PDF-Datei
( http://www.bwinf.de/aufgaben/runde1/aufgaben1.php) nahezu unmöglich. Nachdem der Einsendeschluss für den Wettbewerb eh schon um ist, kann mal das ja wohl in ein Forum setzen: Wie soll das bitte gehen? und vor allem: Wer von euch kann das? Bin ich der einzige Depp der nicht auf die Lösung kommt?
-
Das heißt ja auch Bundeswettbewerb Informatik und nicht Bundeswettbewerb Programmieren.
Von den Aufgaben würde mir nach Aufgabe1 die Beispielaufgabe am leichtesten Fallen, mit den Problemen aus den anderen Aufgaben hab ich mich noch nie befasst..
-
nich schlecht die Aufgaben. Da müsst ich glaub ich auch ne Weile rumprobieren.
-
Wäre auch ein langweiliger Wettbewerb wenn jeder ohne weiteres auf eine perfekte Lösung kommen würde.
-
das ganze ist ein informatik wettbewerb. das heisst, programmieren ist zwar integraler bestandteil, aber hauptaugenmerk liegt darauf, aus den aufgabenstellungen auf das eigentliche problem zu schließen.
was ist also das kernproblem bei aufgabe 2? auf welche mathematischen probleme lässt sich das ganze reduzieren, vielleicht optimierung?
sobald das klar ist, kann das programmieren beginnen. und erst dann kommt die fähigkeit der umsetzung (des programmierens) zum tragen.aufgabe 2 ist tatsächlich nicht trivial und wird ohne gründliche vorüberlegung schwerlich zu lösen sein.
ein ansatz wäre folgender:
zu finden sind die koeffizienten A und B, so dass die varianz von M der in der aufgabe dargestellten formel bezüglich der messwerte minimiert wird.
-
Für Aufgabe2 sollte man mal nach "Lineare Optimierung" suchen.
-
Überseh ich was? Oder was soll an Aufgabe 2 jetzt so schwer sein? Drei verschachtelte Schleifen, zwei Formeln zum einsetzten, Fehler merken, die mit kleinstem Fehler sind die besten, wenns mehrere gibt noch die Faktoren anschauen.
-
ja, du übersiehst, dass das problem unbeschränkt ist. kleinen koeffzienten wird zwar der vorzug gegeben, aber wenn ein wenig größere andere anforderungen besser befriedigen, dann sind sie auch ok.
es wird aufgrund der generellen beschränktheit der aufgabe mittels brute-force in annehmbarer zeit lösbar sein. aber das birgt zwei probleme:
1. brute force ist niemals schön
2. kannst du die nachfolgenden fragen dann ohne probleme beantworten?
-
Hier mal mein Ansatz:
Seinen x,y,z die Messwerte wobei z der M Wert ist uns a,b,c die Koeffizienten. und .Die angegebene Formel ist dann:
a\*x + b\*y = c*z
Ziehen wir da z raus
z = \frac{a\*x + b\*y}{c}
Die Abweichung wäre dann
|\frac{a\*x+b\*y}{c} - z|
Es gilt also
\sum|\frac{a\*x+b\*y}{c} - z|
Zu minimieren.Dieser absoluter Wert stört mich enorm. Anderseits sollte sich die Abweichung ja eh um 0 liegen also bleibt der Fehler klein wenn wir ihn ignoriren.
Geben wir uns zwei Messergebnise
\frac{a\*x\_1+b\*y\_1}{c} - z\_1 + \frac{a\*x\_2+b\*y\_2}{c} - z\_2
= \frac{a\*x\_1+b\*y\_1+a\*x\_2+b\*y\_2}{c} - (z\_1 + z\_2)
Das sieht ja toll aus.
\sum\frac{a\*x+b\*y}{c} - z = \frac{a*\sum{x}+b*\sum{y}}{c} - \sum{z}
Überprüfen wir das mal gleich mit dem angegebenen Beispiel:
Huch Sollte die Abweichung nicht 0 sein?Mal sehen:
2*57 - 1*31 = 3*29
114-31 = 87
83 = 87
Nee also für Experiment 2 ist die Abweichung doch nicht 0. Also kann die Summe aller Abweichungen gar nicht 0 sein!Weiter mit diesem Ansatz geh ich jetzt nicht. Das Problem ist, dass 2 schlimme Fehler in 2 Exprerimenten sich ausgleichen können.
-
Ok, vielleicht sollt ich schaun, dass ich mich in Mathe etwas steigere. Oder mich als Altgrieche(!) nach anderen Problemen umsehen. Aber andererseits kann ich die restlichen Aufgaben fast ebenso wenig (außer die erste, da müsst ich zwar lange rumprobieren, aber ich versteh wenigstens die Angabe
).Außerdem ich glaub nicht, dass man "Programmieren" und "Informatik" so strikt trennen darf. Wenn jemand weiß, wie man ein Werkzeug bedient und trotzdem keine Ahnung hat, was er schließlich damit anfangen soll, steht auch blöd da, oder? Wenn ich programmieren, aber kein Problem lösen kann, werd ich wohl auch nicht sehr erfolgreich werden.
-
Ben04 schrieb:
Dieser absoluter Wert stört mich enorm. Anderseits sollte sich die Abweichung ja eh um 0 liegen also bleibt der Fehler klein wenn wir ihn ignoriren.
Das mit dem ignorieren kann ich nicht nachvollziehen. Wenn Du das machst, dann kannst Du Dein Verfahren nicht mehr gut analysieren, weil Du nicht weißt welche Fehler passieren.
Eine gute Möglichkeit den Betrag loszuwerden ist, den quadratischen Fehler zu minimieren. Damit bestraft man große Abweichungen stärker. Kriegt man den quadratischen Fehler auf 0, dann ist auch der absolute 0. Außerdem bleibt so die Fehlerfunktion differenzierbar, was man sich unter Umständen für die Minimumsuche zu Nutze machen könnte.
Das wäre vielleicht ne ganz nette Idee. Erstmal den quadratischen Fehler minimieren, dann die schlechtesten Experimente rausschmeißen, neu berechnen und dann die Koeffizienten auf ganze Zahlen runden.
Ich denke die Aufgabe zielt auch insgesamt mehr drauf ab, daß geschickte Vereinfachungen der Aufgabenstellung gemacht werden, um so das Problem lösen zu können. Eine "Optimallösung" ist da vermutlich garnicht gefordert.
-
Außerdem ich glaub nicht, dass man "Programmieren" und "Informatik" so strikt trennen darf.
doch, das darf man, beziehungsweise muss man sogar. informatik ist eine wissenschaft, die sich (grob) mit informationsauswertung/-beschaffung befasst und versucht, probleme so zu formulieren, dass sie automatisiert gelöst werden können.
das umsetzen solcher ergebnisse, also der praktische ansatz, ist dann meist das programmieren. also der vorgang, die problembeschreibung und lösung in ein standardisiertes format (eine hochsprache) zu bringen.
wie heisst es so schön? computer sind für die informatik das, was teleskope für die astronomie sind.