Literaturnachweis - Detailanzeige
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 1. Gefälligkeitsübersetzung: The vertex cover problem: A case study on the didactics of NP-hard problems. Pt. 1. |
Quelle | In: Log in : informatische Bildung und Computer in der Schule, 27 (2007) 146-147, S. 53-59 |
Sprache | deutsch |
Dokumenttyp | gedruckt; Zeitschriftenaufsatz |
ISSN | 0720-8642 |
Schlagwörter | Komplexitätstheorie; Informatikunterricht; Kombinatorik; Mathematisches Modell; Komplexitätstheorie; Matrizenrechnung; Theoretische Informatik; Informatikunterricht; Theoretische Informatik; Graf (Math); Kombinatorik; Mathematisches Modell; Matrizenrechnung; Menge (Math); Näherungsberechnung; 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. Ausgehend von unterschiedlichen Modellierungen werden verschiedene Lösungsverfahren erläutert und bewertet. Die mit NP-schweren Problemen verbundene, anscheinend unvermeidliche kombinatorische Explosion wird thematisiert. Ausgehend vom konkreten Problem werden 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. Starting from different mathematical models, several solution methods are explained and assessed. It explores 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. 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 |