Das Cliquenproblem history menue Letztmalig dran rumgefummelt: 16.04.18 17:31:11

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:
Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer


1. Problembeschreibung history menue scroll up

 
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 history menue scroll up

 
effiziente Lösung nur als rekursiver Algorithmus


3. Lösungsalgorithmus history menue scroll up
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 history menue scroll up

 
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
 


5. Zusammenfassung history menue scroll up

 
 


6. Weiterführende Literatur history menue scroll up

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


7. Links zum Thema history menue scroll up

 
 


8. Verwandte Themen history menue scroll up

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

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)