Das KnotenüberdeckungsproblemEine Fallstudie zur Didaktik NP-schwerer Probleme (Teil 2)
Publikationsdatum:
Zu finden in: LOG IN 148/2007 (Seite 81 bis 89), 2007
|
|
Diese Seite wurde seit 4 Jahren inhaltlich nicht mehr aktualisiert.
Unter Umständen ist sie nicht mehr aktuell.
Zusammenfassungen
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 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) 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) Dieser wissenschaftliche Zeitschriftenartikel erwähnt ...
Dieser wissenschaftliche Zeitschriftenartikel erwähnt vermutlich nicht ...
Nicht erwähnte Begriffe | Bildung, Digitalisierung, Informatikunterricht in der Schule, Kinder, LehrerIn, Lernen, P (PTIME), Primarschule (1-6) / Grundschule (1-4), Schweiz |
Tagcloud
Volltext dieses Dokuments
Das Knotenüberdeckungsproblem: Artikel als Volltext (: , 332 kByte) | |
Das Knotenüberdeckungsproblem: Kapitel als Volltext (: , 608 kByte) |
Anderswo suchen
Beat 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.