Das Knotenüberdeckungsproblem

Letztmalig dran rumgefummelt: 28.01.08 08:16:34

	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.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Knotenüberdeckungsproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 53 ff.

1. Problembeschreibung

	Das hier vorgestellte Problem befasst sich mit der Überdeckung der Kanten eines Graphen mit möglichst wenigen Knoten und wird als Knotenüberdeckungsproblem bezeichnet. Beispiele zur Knotenüberdeckung in Graphen Viele Probleme aus Alltag und Wissenschaft lassen sich als Knotenüberdeckungsprobleme formulieren. Die nachfolgend genannten Fallbeispiele verdeutlichen am konkreten Problem Knotenüberdeckung, in welch verschiedenen Bereichen das mit der P=NP-Frage inhärent verknüpfte Phänomen der kombinatorischen Explosion auftreten kann.
	Ein Partyproblem Nehmen wir an, Person X will eine harmonische Geburtstagsfeier gestalten. Einzuladende Kandidaten wären am liebsten acht Personen, nämlich die Personen A bis H. Nun ist es jedoch so, dass nicht alle potenziellen Gäste miteinander harmonieren; Ziel von X ist es, möglichst viele der acht Personen so einzuladen, dass nur miteinander harmonierende Personen an der Feier teilnehmen. Man versuche. eine möglichst gute Lösung zu finden. wenn Nicht-Harmonie genau zwischen folgenden Personenpaaren besteht: (A,D), (B,D), (B,E). (C,E), (D,F), (D,E), (E,G), (EG), (EH). Eine grafische Darstellung dieses Beziehungsgeflechts sieht wie unten aus: X kann bis zu fünf Personen für eine harmonische Party einladen.
	Ein Experimentproblem Forscherin A arbeitet in einer experimentellen Wissenschaft auf Basis teurer, nicht immer fehlerfreier Experimentdurchführungen an einer neuen wissenschaftlichen Hypothese. Leider widersprechen sich einige der Experimentergebnisse, was aber allein an der Fehlerhaftigkeit der Ergebnisdaten liegen kann. In den empirischen Wissenschaften ist es daher nicht unüblich, folgende Plausibilitätsbetrachtung anzustellen: Die aus den Experimentdaten abzuleitende Hypothese ergibt sich am besten bzw. am wahrscheinlichsten so, indem man eine möglichst kleine Zahl von (vermutlich) fehlerhaften Experimentergebnissen eliminiert, sodass der verbleibende Rest in sich widerspruchsfrei ist und somit zur Hypothesenbildung taugt. Man versuche eine möglichst breite Hypothesenbasis zu finden, wenn folgende Experimentpaare jeweils einander widersprechen: (l ,2), (2,3). (2,4), (3.4), (4,5), (4,6), (5.6). (6,7), (6,8), (6,9). Unten wieder eine grafische Darstellung: Die Elimination von drei der neun Experimente würde zu einer schlüssigen Hypothese führen.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Unter Annahme der Tatsache, dass wir nicht die Kaprekartiefe, sondern die Regelmäßigkeit der Wiederkehr der einzelnen Werte selbiger suchen, fällt die Aufgabe heute typischerweise in den Bereich der nicht entscheidbaren Probleme. Und diese Beschreibung selbst zu finden, dürfte dann schon in die Klasse der komplexen Probleme fallen.

3. Lösungsalgorithmus

	Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Dezember 2007