Foren » 37. BwInf

Fragen zur 2. Runde – Aufgabe 1: Lisa rennt

    • 108 Beiträge
    22. Januar 2019 12:44:04 CET

    Es sollte weder negative y-Werte noch negative x-Werte geben.

  • 22. Januar 2019 16:49:53 CET

    Ok, danke

    • 108 Beiträge
    23. Januar 2019 15:35:39 CET

    > Ist Lisa punktförmig?

    Ja, der Einfachheit halber.

     

    > Im BWInf-Forum gab es den offiziellen Hinweis, dass an einem
    > Berührpunkt zweier Polygone
    > für Lisa kein Durchkommen ist. In den bereitgestellten Beispielen tritt
    > dieser Fall aber - wie auch der Fall, dass zwei verschiedene Polygone
    > eine gemeinsame Strecke haben, die lt. Forum ebenfalls kein Durchkommen
    > ermöglichen soll - nicht auf.
    > Muss die einzureichende Lösung diese Fälle nun berücksichtigen, um
    > keinen Punktabzug zu riskieren, oder nicht?
    >

    Wenn man auf diese besonderen Fälle in der Dokumentation
    eingeht, werden auch sinnvolle Antworten darauf erwartet.
    Es dürfen zusätzlich auch eigene Beispiele verwendet werden.

    Im Übrigen kann eine schwierige Erweiterung der Aufgabenstellung
    und ihre Lösung in der 2. Runde wertvolle Pluspunkte bringen.
    Inwieweit die besonderen Fälle dazu gehören, wird davon
    abhängen, wie schwierig sie sind und wie sie gelöst werden.


    > In Beispieldatei 5 gibt es einige Merkwürdigkeiten:
    > - drei Punkte des Polygons 3 liegen auf einer Strecke
    > - drei Punkte des Polygons 10 liegen auf einer Strecke
    > - zwei Punkte des Polygons 11 liegen dicht beieinander: (380,340)
    > und (381,340)
    > - zwei Punkte des Polygons 12 liegen dicht beieinander: ( 80,300)
    > und ( 81,300)
    >
    > Diese Merkwürdigkeiten irritieren mich.
    > Wird erwartet, dass das Programm überflüssige Punkte explizit wegoptimiert?
    >

    Nein, das wird nicht erwartet, die Merkwürdigkeiten sollen nicht verunsichern;
    eventuell testen sie nur die Eingabe des Programms ohne Auswirkungen auf Lisas Weg.


    Dieser Beitrag wurde am 23. Januar 2019 15:35:59 CET von Mario Albrecht bearbeitet
    • 2 Beiträge
    25. Januar 2019 13:33:30 CET
    Fährt der Bus eigentlich von unten nach oben oder von oben nach unten?
    • 108 Beiträge
    25. Januar 2019 14:20:15 CET

    Der Bus fährt entlang der y-Achse mit der Haltestelle am Punkt (0,0). Er trifft daher auf Lisa bei einem positiven y-Wert, wenn sie den Bus erreicht.

    • 2 Beiträge
    25. Januar 2019 14:56:51 CET
    Trifft der Bus auf Lisa, nachdem er von der Haltestelle abgefahren ist?
    • 108 Beiträge
    25. Januar 2019 17:23:56 CET

    Ja, der Bus trifft erst auf Lisa, nachdem er von der Haltestelle abgefahren ist.

    • 6 Beiträge
    25. Januar 2019 21:11:54 CET

    Könnte Lisa direkt an der Kante eines Polygons laufen? Da sie die Größe eines Punktes hat müsste das ja gehen, da es keinen unterschied gäbe wenn sie unendlich nah an der Kante dran wäre.

    • 108 Beiträge
    25. Januar 2019 21:29:42 CET

    Ja, Lisa kann entlang der Kante eines Polygons laufen.

  • 26. Januar 2019 10:46:23 CET
    Mario Albrecht said:

    Ja, der Bus trifft erst auf Lisa, nachdem er von der Haltestelle abgefahren ist.

    Ich habe es noch nicht überprüft, aber könnte der optimale Treffpunkt nicht auch an der Haltestelle liegen?

    • 108 Beiträge
    26. Januar 2019 15:26:09 CET

    Ja, aber das würde nicht der Intention der Aufgabenstellung entsprechen.

  • 26. Januar 2019 18:21:12 CET

    Was soll man machen, falls man z.B. selbst Beispieldaten macht und dabei der Treffpunkt an der Haltestelle liegt?

    • 10 Beiträge
    27. Januar 2019 20:36:12 CET

    Handelt es sich bei den x- und y-Koordinaten von Lisa und den Polygonen um Angaben in Metern?

    • 108 Beiträge
    27. Januar 2019 23:15:02 CET

    Ja.

    • 6 Beiträge
    28. Januar 2019 19:45:56 CET

    Wie wichtig ist ein schneller Algorithmus bei der Aufgabe?
    Bei den Dokumentationsinfos steht ja nicht mal, dass die Laufzeit angegeben werden muss

    (neben Daten wie Länge des Weges, Zeit des Treffpunktes usw.)


    Sollte man sich also überhaupt darauf konzentrieren, dass die Laufzeit gering bleibt oder eher auf andere Sachen?

    • 108 Beiträge
    29. Januar 2019 15:20:43 CET

    Wichtige Eigenschaften der eingesetzten Algorithmen wie z.B. Laufzeit sind natürlich stets ebenfalls interessante Angaben. Die Laufzeit sollte sich immer im vernünftigen Rahmen bezüglich der Problemgröße halten, daher sind konkrete Angaben hierzu vorab nicht weiter möglich.

    • 6 Beiträge
    29. Januar 2019 23:20:43 CET

    Wie genau soll die Zeit angegeben, zu der Lisa los muss?

    • 108 Beiträge
    29. Januar 2019 23:24:17 CET

    In Sekunden.

    • 5 Beiträge
    1. Februar 2019 19:23:20 CET

    Sollte in der Doku die Lösungsidee nur sehr ausführlich beschrieben werden, oder auch bewiesen werden, dass es die optimale Lösungsidee ist

    • 108 Beiträge
    1. Februar 2019 23:36:56 CET

    Leider ist mir der Inhalt der Frage nicht ganz klar, aber ich versuche mal eine Antwort:
    Beweise wie in der Mathematik kommen beim BwInf eher selten vor, dagegen sind Hinweise und Nachweise anhand von Beispieldaten, Zufallsdaten und Ergebnisvergleiche etc. über die Qualität eines Verfahrens relativ häufig. Die Lösungsidee sollte stets klar beschrieben und begründet werden, ggf. auch im Vergleich zu anderen Lösungsideen.

    Bei dieser Aufgabe könnte man sich tatsächlich auch einen kleinen mathematischen Beweis vorstellen, z.B. warum Lisas Weg stets einen bestimmten Verlauf haben sollte, um ein kurzer Weg zu sein. Diese Möglichkeit hängt jedoch u.a. vom konkreten Verfahren zur Wegberechnung ab, so dass ich hier nur recht allgemeine Aussagen machen kann und werde. 

  • 2. Februar 2019 14:56:46 CET
    Matej Svaral said:

    Sollte in der Doku die Lösungsidee nur sehr ausführlich beschrieben werden, oder auch bewiesen werden, dass es die optimale Lösungsidee ist

    Ich glaube nicht, dass es tatsächlich eine optimale Lösungsidee gibt, sondern eher viele gleichwertige Wege um ans Ziel zu kommen.

    Meinst du vielleicht ob gezeigt werden soll, dass mit der Lösungsidee der optimale Weg gefunden wird? Ich denke, das müsste in der Dokumentation schon klar werden, da es ja nur eine Lösung der Aufgabe ist, wenn tatsächlich der kürzest mögliche Weg gefunden wird. Man sollte also vermutlich schon zeigen, dass ein kürzerer Weg nicht möglich ist.

    • 1 Beiträge
    5. Februar 2019 13:33:31 CET

    Ich hätte noch eine Frage zu dem Dateiformat. Sind die Punkte der Polygone nach einem bestimmten Schema angegeben (d.h. die Eckpunkte im Uhrzeigersinn oder entgegengesetzt) oder kann das von Polygon zu Polygon variieren?


    Dieser Beitrag wurde am 5. Februar 2019 13:34:12 CET von Ben Lennart Hanßke bearbeitet
    • 108 Beiträge
    5. Februar 2019 16:41:45 CET

    Die Reihenfolge bzw. mit/entgegen dem Uhrzeigersinn kann variieren, siehe hierzu auch beispielhaft SVG.


    Dieser Beitrag wurde am 5. Februar 2019 16:42:57 CET von Mario Albrecht bearbeitet
    • 3 Beiträge
    5. Februar 2019 18:11:04 CET

    Hallo,

    ich habe eine Frage bezüglich der Bearbeitung der fünf Beispiele.

    Darf man die Vorgehensweise (Code) pro Beispiel ändern, da man unterschiedliche Komplexititäten in den Beispielen hat,  oder muss man sozusagen denselben Code auf alle Bsp. anwenden können ? 


    Dieser Beitrag wurde am 5. Februar 2019 18:47:23 CET von Rafael Gagarin bearbeitet
    • 108 Beiträge
    5. Februar 2019 19:29:12 CET

    Ja, es ist durchaus in der Informatik üblich, abhängig von der Komplexität der Daten unterschiedliche Verfahren anzuwenden.