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 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-89 |
| Sprache | deutsch |
| Dokumenttyp | gedruckt; Zeitschriftenaufsatz |
| ISSN | 0720-8642 |
| Schlagwörter | Komplexitätstheorie; Algorithmus; Informatikunterricht; Kombinatorik; Mathematisches Modell; Komplexitätstheorie; Matrizenrechnung; Theoretische Informatik; 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 |
Literaturbeschaffung und Bestandsnachweise in Bibliotheken prüfen
Permalink als QR-Code
Inhalt auf sozialen Plattformen teilen (nur vorhanden, wenn Javascript eingeschaltet ist)
Teile diese Seite:
