Foren » 34. BwInf

• Manuel Drehwald

  

  • 3 Beiträge
   

  16. Januar 2016 17:24:08 CET

  In der ersten Runde habe ich auf meine Lösung 2 Punkte abzug erhalten, einmal wegen einer zu komplexen Lösung und darauf aufbauend unzureichender begründung. Da wir dennoch knapp weitergekommen sind habe ich mir damals keine Gedanken mehr drüber gemacht. In dieser Runde würde ich auf die abzüge aber ganz gern verzichten.
  
  Was die Begründung angeht kann ich es beim ansehen meiner Dokumentation jetzt auch nachvolziehen dass ein paar Sätze mehr nicht geschadet hätten. Das zu komplexe Prgrogramm finde ich dagegen recht schwammig, weswegen ich jetzt einfach mal für die nächste Aufgabe nachfrage.
  
  
  Meine Lösung für aufgabe 3 (in c++) geht über 150-200 Zeilen.
  Ich könnte auch einen simpleren ansatz wählen den ich auf weniger Zeilen unterbringen könnte, dafür würde sich halt je nach Ansatz die zeit/xyz/... komplexität (stark) verschlechtern oder es würde dank zeigernutzung meiner Meinung nach schwerer verständlich werden.
  
  Daher meine Frage, was hier eher gewünscht ist. Ein "Asymptotisch optimales"/längeres Programm und eine Dokumentation in der steht warum simplere ansätze mehr sekunden benötigen
  oder
  etwas kurzes und simples, dass dafür ineffizienter arbeitet mit einem kurzen hinweis in der Dokumentation wie man das programm noch verbessern könnte.
  
  Da ich c++ nutze ist die Zeit in sekunden eh volkommen egal, selbst mittels brute force müsste man unter einer sekunde pro beispiel bleiben können.
  Dieser Beitrag wurde am 16. Januar 2016 18:30:00 CET von Manuel Drehwald bearbeitet
• Tim Weiland

  

  • 17 Beiträge
   

  16. Januar 2016 20:59:53 CET

  Hallo,
  ich kann keine offizielle Antwort geben, aber meiner Meinung nach hat Laufzeit Vorrang vor Simplizität. Allerdings muss ich hinzufügen, dass das Eine das Andere nicht ausschließt. Man kann auch eine effiziente Lösung elegant umsetzen. Ich denke überhaupt, dass dieses Kriterium die Laufzeit schon berücksichtigt. Anscheinend hätte deine Lösung mit einer ähnlichen Laufzeit noch simpler umgesetzt werden können. Zumindest habe ich in der ersten Runde immer die Option mit der besten Laufzeit gewählt und bei diesem Kriterium keine Abzüge erhalten.
  Dieser Beitrag wurde am 16. Januar 2016 21:00:26 CET von Tim Weiland bearbeitet
• Thomas Leineweber

  

  • 230 Beiträge
   

  17. Januar 2016 18:33:34 CET

  [blockquote]Manuel Drehwald said:
  Daher meine Frage, was hier eher gewünscht ist. Ein "Asymptotisch optimales"/längeres Programm und eine Dokumentation in der steht warum simplere ansätze mehr sekunden benötigen
  oder
  etwas kurzes und simples, dass dafür ineffizienter arbeitet mit einem kurzen hinweis in der Dokumentation wie man das programm noch verbessern könnte.
  [/blockquote]
  
  Das hängt immer auch von der Aufgabe ab :). Die Lösungshinweise sind momentan noch nicht online, da sollte dann aber auch zu diesen Punkten etwas stehen. Die Komplexität eines Programms hat aber erstmal nichts mit der Länge und/oder Schönheit des Programms zu tun.
  
  [blockquote]
  Da ich c++ nutze ist die Zeit in sekunden eh volkommen egal, selbst mittels brute force müsste man unter einer sekunde pro beispiel bleiben können.[/blockquote]
  
  Bei dieser Aussage kann ich nur sagen: "Kühne Behauptung". Egal welche Programmiersprache Du nimmst, bei Brute Force wirst Du die schwereren Eingabevorgaben nicht innerhalb der Bearbeitungszeit der ersten Runde gelöst bekommen. Dazu eine schnelle Überschlagsrechnung: Die flaschenzug5.txt hat schon 42376183321681306437343953352208
  Lösungen. Wenn Du 1 Billion Möglichkeiten pro Sekunde aufaddieren könntest, wären das
  42376183321681306437 Sekunden oder immer noch 1343739958196 Jahre... Da hilft Dir auch C++ nicht (auch wenn Dein Rechner noch 1 Million mal schneller ist) :)
• Manuel Drehwald

  

  • 3 Beiträge
   

  17. Januar 2016 19:42:14 CET

  [blockquote]Thomas Leineweber said:
  Das hängt immer auch von der Aufgabe ab :). Die Lösungshinweise sind momentan noch nicht online, da sollte dann aber auch zu diesen Punkten etwas stehen.
  [/blockquote]
  Wunderbar, darauf hatte ich gehoft, dann warte ich einfach noch ein paar Tage.
  [blockquote]Tim Weiland said:
  Allerdings muss ich hinzufügen, dass das Eine das Andere nicht ausschließt. [/blockquote]
  [blockquote]Thomas Leineweber said:
  Die Komplexität eines Programms hat aber erstmal nichts mit der Länge und/oder Schönheit des Programms zu tun.
  [/blockquote]
  Wundert mich, aber praktisch habe ich nicht viel programmiert, daher warte ich mal auf den Lösungsvergleich.
  
  
  [blockquote]Thomas Leineweber said:
  Bei dieser Aussage kann ich nur sagen: "Kühne Behauptung". Egal welche Programmiersprache Du nimmst, bei Brute Force wirst Du die schwereren Eingabevorgaben nicht innerhalb der Bearbeitungszeit der ersten Runde gelöst bekommen. Dazu eine schnelle Überschlagsrechnung: Die flaschenzug5.txt hat schon 42376183321681306437343953352208
  Lösungen. Wenn Du 1 Billion Möglichkeiten pro Sekunde aufaddieren könntest, wären das
  42376183321681306437 Sekunden oder immer noch 1343739958196 Jahre... Da hilft Dir auch C++ nicht (auch wenn Dein Rechner noch 1 Million mal schneller ist) :)[/blockquote]
  
  Interessante Rechnung, allerdings hätte ich wohl anmerken sollen dass es um alle Beispielswelten der Aufgabe 3 der 2. Runde ging, wo man höchstens eine welt aus 25*25 Feldern hat.
  Eine Beispielrechnung zur aktuellen Runde unterlasse ich dann aber lieber mal nicht das mein schöner beitrag hier entfernt wird.
  
  
  Dieser Beitrag wurde am 17. Januar 2016 19:55:19 CET von Manuel Drehwald bearbeitet
• Wolfgang Pohl

  

  • 391 Beiträge
   

  18. Januar 2016 19:16:04 CET

  Wenn es um die Bewertungspunkte "Verfahren unzureichend begründet bzw. schlecht nachvollziehbar" bzw. "Verfahren allzu aufwändig" geht: Der erste Punkt bezieht sich auf die Dokumentation. Der zweite Punkt bezieht sich nicht auf das Programm, sondern auf das dadurch implementierte Verfahren: Das Verfahren selbst ist dann wohl unnötig kompliziert oder umständlich (woraus folgen kann, aber nicht muss, dass es auch unnötig komplex ist) oder wirklich unnötig komplex. Wobei "komplex" sich in der Informatik auf den Verbrauch von Ressourcen wie Laufzeit oder Speicher bezieht und eine Frage von mathematisch formulierbaren Größenordnungen ist, nicht von Sekunden.
  
  Näheres wird sich aus den Lösungshinweisen ergeben, die hoffentlich bald online sind (aber ein paar Tage wird es noch dauern).
  
  Aber wie auch immer: Die Frage ist also nicht, wie viele Programmzeilen man schreiben sollte.
  Dieser Beitrag wurde am 18. Januar 2016 19:19:03 CET von Wolfgang Pohl bearbeitet