/ en / Traditional / help

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 local 
Erste Seite des Textes (PDF-Thumbnail)
Diese Seite wurde seit 4 Jahren inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconZusammenfassungen

LOG IN 148/2007In 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 1 46/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)
LOG IN 148/2007In 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 ...


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 , Modellemodel , NP , NP-completeNP-complete , Problemproblem , Schuleschool , Theorietheory , Turing-Maschineturing machine , Unterricht

iconDieser wissenschaftliche Zeitschriftenartikel erwähnt vermutlich 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.

iconTagcloud

iconVolltext dieses Dokuments

Das Knotenüberdeckungsproblem: Artikel als Volltext (lokal: PDF, 332 kByte)
Das Knotenüberdeckungsproblem: Kapitel als Volltext (lokal: PDF, 608 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.

iconBeat und dieser wissenschaftliche Zeitschriftenartikel

Beat hat Dieser wissenschaftliche Zeitschriftenartikel während seiner Zeit am Institut für Medien und Schule (IMS) ins Biblionetz aufgenommen. Beat besitzt kein physisches, aber ein digitales Exemplar. (das er aber aus Urheberrechtsgründen nicht einfach weitergeben darf). Es gibt bisher nur wenige Objekte im Biblionetz, die dieses Werk zitieren.

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.