Dein Suchergebnis zum Thema: muss

Hallo, wenn ich es richtig verstanden habe gibt es bei Nr.1 nur gerichtete Kanten. Sprich: Du kommst von Knoten A zu B, aber nicht umgekehrt. Kann es aber auch sein, dass man ungerichtete Kanten hat? Also: Du kommst von A zu B und von B zu A. Edit: Bzw. Können Kreise vorkommen? Z.B. A ist mit B verbunden, B mit C und C mit A. Denn beides ist im Beispiel der PDF nicht vorhanden
Sind die Kanten transitiv, also wenn der Graph so aussieht: A —> B —> C Muss

Wenn du nur Junior-Aufgaben abgibst, nimmst Du an der Juniorliga teil. Wenn Du aber mindestens eine der anderen fünf Aufgaben bearbeitest, bist Du aus der Juniorliga raus und es geht um die Punkte, um in die zweite Runde zu kommen. Siehe auch http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf31/Aufgabenblatt311_simple.pdf auf Seite 4 unter der Überschrift „Juniorliga“.
Ich dachte ich muss die „schweren“ Aufgaben machen…

Hallo zusammen, am kommenden Montag, 28.11.2016, ist Einsendeschluss. Nach dem Einsendeschluss kann auch gerne über die konkreten Lösungsideen und deren Umsetzungen diskutiert werden. Dann können die Einsendungen gerne auch online für andere zur Verfügung gestellt werden. Es sollte nur gewartet werden, bis das PMS auch wirklich keine Einsendung mehr entgegen nimmt. Das wird voraussichtlich irgendwann in der Nacht vom Montag zum Dienstag passieren. Wenn Ihr Eure Einsendung online gestellt habt, wäre es auch ganz gut, hier einen Link zu posten. Dann gibt es auch die Möglichkeit, über verschiedenen Lösungen zu diskutieren. Viele Grüße Thomas
möglichen Lösungsweg für Minnie gefunden hat – was nicht zwangsläufig ein Fehler sein muss

Hier könnt ihr Fragen zur Aufgabe 2 (Nummernmerker) der 1. Runde stellen.
Wäre dann die Lösung 01 23 45 6 ungültig und muss zu 01 23 456 umgewandelt werden

Hier könnt ihr Fragen zur Aufgabe 2 (Nummernmerker) der 1. Runde stellen.
Wäre dann die Lösung 01 23 45 6 ungültig und muss zu 01 23 456 umgewandelt werden

Computers & Intractability: A Guide to the Theory of NP-completenessSchwierigkeitsgrad: SchwerAutoren: Michael R. Garey, David S. JohnsonErscheinungsdatum: 1979Sprache: EnglischISBN: 0-7167-1045-5340 SeitenRezension von Sebastian GießeJedem, der Grundkenntnisse in der Komplexitätstheorie hat und nun seineKenntnisse über NP-Vollständigkeit verbessern möchte, dem empfehle ich“Computers & Intractability: A Guide to the Theory of NP-completeness“ vonGarey und Johnson.Das Buch eignet sich sowohl als Lehrbuch als auch zum Nachschlagen. ZumNachschlagen eignet sich vor allem der riesige Anhang, mit mehr als 300NP-vollständigen Problemen. Dieser ist sinnvoll kategorisiert, sodass manschnell Probleme finden kann, auch ohne ihre Namen zu kennen. So konnte ichzum Beispiel unter „A2.1 Spanning Trees“ das Problem „Degree ConstrainedSpanning Tree“ finden, welches ich zum Beweisen der NP-Vollständigkeit vonAufgabe 1 der 2. Runde des 29. BwInf nutzen konnte.Das Buch beginnt mit einer netten Geschichte von einem Informatiker, derkeinen schnellen Algorithmus für ein Problem findet, aber zeigen kann, dassdies nicht daran liegt, dass er ein schlechter Informatiker ist.Nach der Einführung in Kapitel 1, folgt mit Kapitel 2 ein ausführlicher undsehr formaler Einstieg in die NP-Vollständigkeit. Ein Problem ist in NP,wenn die zugehörige Sprache von einer nichtdeterministischen Turingmaschinein Polynomialzeit entscheidbar ist. Schließlich wird noch der Satz von Cook(SAT ist NP-Vollständig) bewiesen.Kapitel 3 vermittelt die Kunst des NP-Vollständigkeitsbeweis. Zunächst wirddie grundlegende Idee hinter einem solchen Beweis erklärt, dann wird dieNP-Vollständigkeit von 6 bekannten und wichtigen Problemen (3-SAT,3-Dimensional-Matching, Vertex-Cover, Clique, Hamiltonian Circuit undPartition) bewiesen. Kapitel 3.2 beschreibt allgemein anwendbare Verfahrenzum Beweis von NP-Vollständigkeit und demonstriert diese an Beispielen.Kapitel 4: Using NP-Completeness to Analyze ProblemsKapitel 5: NP-HardnessKapitel 6: Coping with NP-Complete Problems behandeltApproximationsalgorithmen und vermittelt wie man zeigen kann, dass dasErgebniss eines solchen Algorithmus maximal k-mal schlechter als dasoptimale Ergebniss ist.Kapitel 7: Beyond NP-Completeness geht auf unterschiedliche Problemklassen,z.B. P, NP, NPC, co-NPC, PSPACE, DLOGSPACE ein.Leider habe ich das Buch, weil ich es in der Bibliothek ausgeliehen hatte,nicht komplett lesen können. Aber nichtsdestoweniger habe ich sehr vielgelernt. Beim Lesen wird man oft auf Passagen stoßen, die man mehrfach lesenmuss, um sie zu verstehen. Dies liegt aber nicht am Schreibstil der Autoren,sondern an der Schwierigkeit der Thematik. Die Erklärungen sind gut undwerden durch sinnvolle Abbildungen unterstützt. Wer dieses Buch gelesen undverstanden hat, der hat fortgeschrittene Kentnisse über NP-Vollständigkeit,ist in der Lage Probleme als NP-vollständig zu erkennen und dies dann zubeweisen, weiß wie er mit solchen Problemen umgehen soll und ist in der Lageandere Fachliteratur zu verstehen.Das Buch ist ein Klassiker und früher oder später sollte jeder Informatikerdieses Buch (wenigstens teilweise) lesen.
Beim Lesen wird man oft auf Passagen stoßen, die man mehrfach lesen muss, um sie

Computers & Intractability: A Guide to the Theory of NP-completenessSchwierigkeitsgrad: SchwerAutoren: Michael R. Garey, David S. JohnsonErscheinungsdatum: 1979Sprache: EnglischISBN: 0-7167-1045-5340 SeitenRezension von Sebastian GießeJedem, der Grundkenntnisse in der Komplexitätstheorie hat und nun seineKenntnisse über NP-Vollständigkeit verbessern möchte, dem empfehle ich“Computers & Intractability: A Guide to the Theory of NP-completeness“ vonGarey und Johnson.Das Buch eignet sich sowohl als Lehrbuch als auch zum Nachschlagen. ZumNachschlagen eignet sich vor allem der riesige Anhang, mit mehr als 300NP-vollständigen Problemen. Dieser ist sinnvoll kategorisiert, sodass manschnell Probleme finden kann, auch ohne ihre Namen zu kennen. So konnte ichzum Beispiel unter „A2.1 Spanning Trees“ das Problem „Degree ConstrainedSpanning Tree“ finden, welches ich zum Beweisen der NP-Vollständigkeit vonAufgabe 1 der 2. Runde des 29. BwInf nutzen konnte.Das Buch beginnt mit einer netten Geschichte von einem Informatiker, derkeinen schnellen Algorithmus für ein Problem findet, aber zeigen kann, dassdies nicht daran liegt, dass er ein schlechter Informatiker ist.Nach der Einführung in Kapitel 1, folgt mit Kapitel 2 ein ausführlicher undsehr formaler Einstieg in die NP-Vollständigkeit. Ein Problem ist in NP,wenn die zugehörige Sprache von einer nichtdeterministischen Turingmaschinein Polynomialzeit entscheidbar ist. Schließlich wird noch der Satz von Cook(SAT ist NP-Vollständig) bewiesen.Kapitel 3 vermittelt die Kunst des NP-Vollständigkeitsbeweis. Zunächst wirddie grundlegende Idee hinter einem solchen Beweis erklärt, dann wird dieNP-Vollständigkeit von 6 bekannten und wichtigen Problemen (3-SAT,3-Dimensional-Matching, Vertex-Cover, Clique, Hamiltonian Circuit undPartition) bewiesen. Kapitel 3.2 beschreibt allgemein anwendbare Verfahrenzum Beweis von NP-Vollständigkeit und demonstriert diese an Beispielen.Kapitel 4: Using NP-Completeness to Analyze ProblemsKapitel 5: NP-HardnessKapitel 6: Coping with NP-Complete Problems behandeltApproximationsalgorithmen und vermittelt wie man zeigen kann, dass dasErgebniss eines solchen Algorithmus maximal k-mal schlechter als dasoptimale Ergebniss ist.Kapitel 7: Beyond NP-Completeness geht auf unterschiedliche Problemklassen,z.B. P, NP, NPC, co-NPC, PSPACE, DLOGSPACE ein.Leider habe ich das Buch, weil ich es in der Bibliothek ausgeliehen hatte,nicht komplett lesen können. Aber nichtsdestoweniger habe ich sehr vielgelernt. Beim Lesen wird man oft auf Passagen stoßen, die man mehrfach lesenmuss, um sie zu verstehen. Dies liegt aber nicht am Schreibstil der Autoren,sondern an der Schwierigkeit der Thematik. Die Erklärungen sind gut undwerden durch sinnvolle Abbildungen unterstützt. Wer dieses Buch gelesen undverstanden hat, der hat fortgeschrittene Kentnisse über NP-Vollständigkeit,ist in der Lage Probleme als NP-vollständig zu erkennen und dies dann zubeweisen, weiß wie er mit solchen Problemen umgehen soll und ist in der Lageandere Fachliteratur zu verstehen.Das Buch ist ein Klassiker und früher oder später sollte jeder Informatikerdieses Buch (wenigstens teilweise) lesen.
Beim Lesen wird man oft auf Passagen stoßen, die man mehrfach lesen muss, um sie

Hallo zusammen, am kommenden Montag, 28.11.2016, ist Einsendeschluss. Nach dem Einsendeschluss kann auch gerne über die konkreten Lösungsideen und deren Umsetzungen diskutiert werden. Dann können die Einsendungen gerne auch online für andere zur Verfügung gestellt werden. Es sollte nur gewartet werden, bis das PMS auch wirklich keine Einsendung mehr entgegen nimmt. Das wird voraussichtlich irgendwann in der Nacht vom Montag zum Dienstag passieren. Wenn Ihr Eure Einsendung online gestellt habt, wäre es auch ganz gut, hier einen Link zu posten. Dann gibt es auch die Möglichkeit, über verschiedenen Lösungen zu diskutieren. Viele Grüße Thomas
möglichen Lösungsweg für Minnie gefunden hat – was nicht zwangsläufig ein Fehler sein muss

Till Tantau ist seit 2005 Professor für Theoretische Informatik an der Universität zu Lübeck. (Stand 25. Jan. 2010) „In der Mathematik hat man immer das Gefühl, alle grundsätzlichen Fragen sind…
Bei der Bewerbung zu einem Forschungsstipendium muss man immer in einem „Research

Hallo liebe Mitstreiter,   Hier ist eine Sammelstelle zum Austausch von Dokumentationen und der Diskussion darüber:   Alle Dokus (Zusammen): http://files.flysoftiii.de/Dokumentationen.7z (16MB) http://files.flysoftiii.de/Dokumentationen.zip (32MB) Falls Ihr 7zip habt nehmt bitte die Version: Sie ist trotz dem selben Inhalt nur halb so groß!   Alle Dokus (Übersicht): Meine Doku: http://files.flysoftiii.de/bwinf.zip Hennigs Doku: (Beitrag unten) http://hediet.de/temp/doku.php Livenou pwnd yous Demo: (Beitrag unten) http://www.weebly.com/uploads/6/3/7/4/6374817/bwinf_2012_aufgabendoku.zip   Georgios Samaras: (Beitrag Seite 2) https://dl.dropbox.com/u/1882637/Dokumentation.pdf Kai G: (Beitrag Seite 3) https://docs.google.com/folder/d/0Bw1kVw8A2-UkOThfNW1DV2s3Vm8/edit Philip Wellnitz und ein Klassenkamerad: (Beitrag Seite 3): https://skydrive.live.com/redir?resid=DB095059D46F74B!113  Tristan: (ein Freund von mir) http://files.flysoftiii.de/Tristan.zip Danthe: (Skype-Konferenz) https://docs.google.com/folder/d/0B56XaplthylNSGVoNG9aRl9nVEk/edit?pli=1 Elina: (Per E-Mail) http://files.flysoftiii.de/Elina.zip Daniel: (Seite 4) http://files.flysoftiii.de/Daniel.zip   Fabian Sturm: (Seite 4) http://fabiansturm.co/bwinf.zip  Felix R: (Per E-Mail, siehe Seite 4) http://files.flysoftiii.de/Felix_R.pdf Ansonsten freue ich mich auch, wenn ihr in den nächsten Tagen eure Doku hochladet, die Doku von anderen ist immer intressant.   Das hosten übernehme bei bedarf ich, schreib mir einfach eine Mail mit eurer Doku im Anhang: flysoft@flysoftiii.de   Viele Grüße,   Moritz   Alter Beitrag, neues siehe weiter unten: ich werde heute Abend um 22:30 hier meine Dokumentation und Lösung als PDF hochladen, wenn es okay ist.Es wäre nett, wenn sich noch ein paar mehr beteiligen. Bitte macht es alle so spät wie möglich, damit man keinen Betrug feststellt. An Herrn Pohl / andere BWInf-Mitarbeiter: Falls dies nicht in Ordnung geht, schreiben Sie das einfach, dass ist der Grund, warum ich jetzt schon nachfrage.   Ansonsten freue ich mich auf einen schönen Ideenaustausch!  
auch mal meine ganzes Zeug hochladen (; allerdings hab ich zur zeit kein webspace, muss