Die Mathe-Redaktion - 19.10.2017 16:30 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 798 Gäste und 21 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » Sonstiges » Al Zimmermann's Programming Contest: Primorial Soup
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Al Zimmermann's Programming Contest: Primorial Soup
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1288
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-09-24 20:38


Seit gestern läuft ein neuer Contest mit dem Thema Primorial Soup.
Wie bei den früheren Wettbewerben sind drei Monate Zeit, um Lösungen einzusenden.

Eine erneute Herausforderung für alle Programmierexperten! smile



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2618
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-09-25 07:50


Danke für den Hinweis :)

Hat jemand denn interesse da im Team dranzugehen? Man sollte ja (eigentlich) die Teams anmelden bevor man loslegt und Lösungsfragmente einreicht...

Sieht jedenfalls auf den ersten Blick schon mal spannend aus :)

grüsse aus dem Harz
gonz



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1288
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2017-09-25 22:29


Eine Teambildung ist jederzeit möglich, solange man nicht schon als Einzelperson (so wie ich smile ) angemeldet ist (und insbesondere Lösungen eingesandt hat).



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2618
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-09-26 11:49


Yep. die von AZ in den FAQ gegebene Formulierung lautet konkret:

"But a team can only be formed by those who have not already entered the contest as individuals. Once you enter as an individual, team membership is no longer open to you. Likewise, once you've joined a team you can't break away and start submitting graphs on your own behalf."

Für das was in der Diskussionsgruppe erlaubt ( oder eben untersagt ) ist, und das gilt dann m.E. auch für einen Austausch hier auf dem MP, wird gesagt:

"The exception is spoilers. Spoilers include:

specific graphs
detailed algorithms"




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2618
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2017-09-26 14:18


ok, ich habe mich dann auch einfach mal so "ins getümmel" gestürzt, sprich testweise mal einen graphen eingereicht.

Allen die teilnehmen oder mitknobeln : frohes Schaffen :)


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5019
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2017-09-26 18:51


Die Bewertungsfunktion ist ziemlich hart. Man kann sehr, sehr dicht an der optimalen Lösung sein und erhält trotzdem nahezu 0 Punkte.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 450
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2017-09-26 20:13


Hallo,

ich habe mir die Programmieraufgabe auch schon angeschaut.
Allerdings - vor Al Zimmermann's Programmieraufgaben habe ich größten Respekt. Seit letztem Jahr weiß ich, dass die optimale Gesamtlösung nur durch die Formel

("extrem viel Gehirnschmalz" * "extrem effizienter Algorithmus" * "extrem starke Rechenpower")^Unendlich

lösbar ist. biggrin
Na gut - vielleicht ist auch eine kleine Übertreibung dabei, aber bisschen was Wahres ist schon dran. razz

Aber nichtsdestotrotz - für n=4 hätte ich immerhin schon eine Lösung.
Aber schon für n=5 rechnet sich mein Rechner wieder halb zu Tode.
Habe zwar schon eine Idee, was man da tun könnte, aber ich fürchte, ich werde auch hier wieder nicht sonderlich weit kommen. Ich weiß noch nicht, ob ich bei dieser Aufgabe mitmachen werde.

Eine interessante Aufgabe ist es jedoch in jedem Fall.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5019
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-09-26 20:57


Die Schwierigkeit besteht (für etwas größere n) darin, dass zwischen beweisbarer unterer Schranke ("target energy" genannt) und dem tatsächlichen Optimum nur ein ganz winziger Spalt (verglichen mit dem Wert der "graph energy" selbst) liegt. Dem Optimum auf 0,01% nahe zu kommen ist für die meisten n immer noch "meilenweit daneben".

Um Mißverständnisse zu vermeiden: Ich finde das gerade spannend. Mit vier ganz verschiedenen Ansätzen bin ich bis jetzt jeweils ein n weiter gekommen.



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1288
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-09-26 21:10


Hi Kitaktus,

Interessant, dass du schon so viele Ansätze ausprobiert hast. Ich habe aus dem letzten Contest gelernt und denke erst mal ein paar Tage über das Problem nach... Beim letzten Mal hätte ich mir dadurch sehr viel Zeit sparen können - die ersten schnell ausprobierten Ideen waren reine Zeitverschwendung. smile

Die beiden kleinsten Probleme habe ich mit Pen&Paper gelöst und scheinbar auch die besten Lösungen gefunden.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5019
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2017-09-27 18:22


Ja, über das Problem nachzudenken, kann nicht schaden.

Die erste Variante (Erzeugen einer zufälligen Lösung) war mehr ein Test, ob ich das Problem, die Nebenbedingung und die Zielfunktion richtig verstanden habe. Das reichte aber schon aus, um (mit genügend vielen Versuchen) die optimale Lösung für n=4 zu finden.

Die nächsten beiden Varianten waren einfache Heuristiken (lokale Suche und ein Greedy-Verfahren). Im Idealfall findet man damit (für kleinere n) auch ein paar optimale Lösungen. Ansonsten findet man zumindest etwas bessere Lösungen, die man mal testweise eingeben kann, um zu sehen, wie weit man von der besten bekannten Lösung noch entfernt ist. Zu dem Zeitpunkt standen die besten Roh-Werte noch nicht auf Als Seite.

Zu wissen, wie gut die besten bekannten Lösungen sind, hat mir dann schon einiges weitergeholfen. Damit kann ich besser abschätzen, "worin eigentlich das Problem besteht" und mit welchen Mitteln man ihm sich nähern kann.
Für kleine n sehr gute oder gar optimale Lösungen zu kennen, ist natürlich auch nicht verkehrt.
Beim letzten Wettbewerb hat mir das sehr gefehlt.



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]