/ en / Traditional / mobile

Beats Biblionetz - Texte

Das Knotenüberdeckungsproblem

Eine Fallstudie zur Didaktik NP-schwerer Probleme (Teil 2)
Rolf Niedermeier, Jörg Vogel, Michael Fothe, Mirko König
Publikationsdatum:
Zu finden in: LOG IN 148/2007 (Seite 81 bis 89), 2007
Erste Seite des Textes (PDF-Thumbnail)
Diese Seite wurde seit 7 Jahren inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconZusammenfassungen

In diesem Beitrag wird das Thema ,,NP-schwere Probleme“ für die Schule aus didaktisch-methodischer Sicht aufbereitet. Stellvertretend geschieht dies am Knotenüberdeckungsproblem, das erhebliche praktische Relevanz besitzt. Im ersten Teil (siehe LOG IN, Heft 146/147, S. 53 ff.) wurden Beispiele sowie Modellierungsaspekte zur Knotenüberdeckung in Graphen aufgezeigt. Ausgehend von unterschiedlichen Modellierungen wurden verschiedene Lösungsverfahren erläutert und bewertet. Darüber hinaus wurde die mit NPschweren Problemen verbundene, anscheinend unvermeidliche ,,kombinatorische Explosion“ thematisiert. Ausgehend vom konkreten Problem werden im Folgenden Problemverwandtschaft, Determinismus und Nichtdeterminismus intuitiv erklärt. Dies mündet in Erläuterungen zur P=NP-Frage, einem der interessantesten Probleme der aktuellen Forschung in der Informatik.
Von Rolf Niedermeier, Jörg Vogel, Michael Fothe, Mirko König im Journal LOG IN 148/2007 im Text Das Knotenüberdeckungsproblem (2007)

iconDieser wissenschaftliche Zeitschriftenartikel erwähnt...

iconDieser wissenschaftliche Zeitschriftenartikel erwähnt nicht... Eine statistisch erstelle Liste von nicht erwähnten (oder zumindest nicht erfassten) Begriffen, die aufgrund der erwähnten Begriffe eine hohe Wahrscheinlichkeit aufweisen, erwähnt zu werden.

icon
Nicht erwähnte Begriffe
Knapsack-Problem, LehrerIn, P (PTIME)

iconTagcloud

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

iconVolltext dieses Dokuments

LokalDas Knotenüberdeckungsproblem: Artikel als Volltext (lokal: PDF, 332 kByte)

iconAnderswo suchen Auch im Biblionetz finden Sie nicht alles. Aus diesem Grund bietet das Biblionetz bereits ausgefüllte Suchformulare für verschiedene Suchdienste an. Biblionetztreffer werden dabei ausgeschlossen.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.

Verweise auf diesen wissenschaftlichen Zeitschriftenartikel 1
Verweise von diesem wissenschaftlichen Zeitschriftenartikel 20
Webzugriffe auf diesen wissenschaftlichen Zeitschriftenartikel 3217326333325122111132621111212321623113213121441132212412514468214
20112012201320142015201620172018