/ 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 6 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 in der Zeitschrift LOG IN 148/2007 im Text Das Knotenüberdeckungsproblem (2007)

iconDieser Zeitschriftenartikel erwähnt...


Fragen
KB IB clear
P=NP ?

Begriffe
KB IB clear
Algorithmusalgorithm, BerechenbarkeitComputability, Determinismusdeterminism, Didaktikdidactics, Entscheidungsproblem, Informatikcomputer science, Informatik-Didaktikdidactics of computer science, Informatik-Unterricht (Fachinformatik)Computer Science Education, Komplexitätcomplexity, Komplexitätstheorie, Modellmodel, NP, NP-completeNP-complete, Problemproblem, Schuleschool, Theorietheory, Turing-Maschineturing machine, Unterricht

iconDieser 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 Zeitschriftenartikel 1
Verweise von diesem Zeitschriftenartikel 20
Webzugriffe auf diesen Zeitschriftenartikel 32173263333251221111326211112123216231132131214411322124125144
2011201220132014201520162017