Das Cliquenproblem

Letztmalig dran rumgefummelt: 10.04.22 15:29:50

	Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Das Cliquenproblem ist eines der 21 klassischen NP-vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies.
	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ösunsverfahren Logo für das Cliquenproblem begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Nun, diese recht praxisnahe Problemstellung läst sich folgendermaßen kurz umschreiben:  Gegeben ist eine Folge von n Fächern, jedes Fach enthält ein Steinchen.   Folge von n Fächern

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

	effiziente Lösung nur als rekursiver Algorithmus

3. Lösungsalgorithmus

Dies war die zweite Aufgabe des Flaggenproblems, nämlich nicht nur das Umsortieren der Steinchen, sondern auch das Umsortieren so effizient wie möglich zu machen. E. W. Dijkstra, der Entwickler des Flaggenproblems, ist dabei folgendermaßen vorgegangen. Er schrieb ein Programm in PASCAL in dem der gesuchte Algorithmus als Prozedur dargestellt wird. Hier eine vereinfachte Version seines entworfenen Algorithmus in PASCAL (blau sind die Erklärungen):

4. Programmvorschläge

	Grundlagen der Bedienung: Graphen-Auswahl: In -Graphen-Auswahl- können Sie zwischen zwei Beispielen eines Graphen auswählen oder selbst einen Graphen erstellen. Um selbst einen Graphen erstellen zu können, wählen Sie in -Graphen-Auswahl- den entsprechenden Punkt aus. Weiter rechts sehen Sie -Graphen-Werkzeuge-, mit denen Sie den Graph erstellen können. Sie können Graphen auch importieren beziehungsweise exportieren. Cliquenberechnung: Klicken Sie auf Berechnen. Die gefundenen Cliquen werden in der dunkelblauen Liste angezeigt. Klicken Sie auf -Redundanz vermeiden-, wenn Sie Wiederholungen von Cliquen vermeiden wollen. Mit -Aufsteigend- beziehungsweise -Absteigend- werden die Cliquen der Größe nach sortiert. In -Cliquen-Problem- können Sie mit Hilfe von -k- auswählen, welche Mindestgröße zur positiven Beantwortung der Entscheidungsfrage notwendig ist. Techniksupport: Für weitere Fragen wenden Sie sich an unseren Techniksupport: fl.papsdorf@t-online.de pia.meier120@gmail.com
	Software-Dokumentation & Download zum Projekt von Florian Papsdorf

5. Zusammenfassung

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig

7. Links zum Thema

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 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 Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-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 Mai 2007