Das Knotenüberdeckungsproblem: Eine Fallstudie zur Didaktik NP-schwerer Probleme. Teil 2.

Autor/inn/en	Niedermeier, Rolf; Vogel, Jörg; Fothe, Michael; König, Mirko
Titel	Das Knotenüberdeckungsproblem: Eine Fallstudie zur Didaktik NP-schwerer Probleme. Teil 2. Gefälligkeitsübersetzung: The vertex cover problem: A case study on the didactics of NP-hard problems. Pt. 2.
Quelle	In: Log in : informatische Bildung und Computer in der Schule, 27 (2007) 148-149, S. 81-89Infoseite zur Zeitschrift Verfügbarkeit
Sprache	deutsch
Dokumenttyp	gedruckt; Zeitschriftenaufsatz
ISSN	0720-8642
Schlagwörter	Komplexitätstheorie; Algorithmus; Informatikunterricht; Theoretische Informatik; Graf (Math); Kombinatorik; Mathematisches Modell; Matrizenrechnung; Menge (Math); Näherungsberechnung; Zufallsgröße; Matrize
Abstract	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 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 NP-schweren 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. The article processes the topic of "NP-hard problems" for use in school from the point of view of didactics and teaching methods. It discusses the example of the vertex cover problem which is considerably relevant for practice. The first part presented examples and showed some aspects on modelling vertex covers in graphs. Starting from different mathematical models, several solution methods were explained and assessed. It also explored the apparently inevitable issue of 'combinatorial explosion' arising with NP-hard problems. Taking the concrete problem as a starting point, problem relationship, determinism and non-determinism are explained intuitively below. This leads to explanations on the problem of P=NP, one of the most interesting problems of current research in computer science.
Erfasst von	FIZ Karlsruhe - Leibniz-Institut für Informationsinfrastruktur
Update	2009/2