Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
46 Aufrufe

Hey,

Ist mit dem festen k in Aufgabenteil b gemeint, dass wir nun einen Graphen untersuchen ob dieser genau k Cliquen hat und nicht wie ursprünglich mindestens k? Falls ja, so ist doch k in beiden Fällen fest, wird jedoch nur unterschiedlich interpretiert?

 

in 2011-N-05 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

Zunächst: k ist die Anzahl der Knoten in der Clique, nicht die Anzahl Cliquen.

Beim Clique-Problem geht es darum, wenn ein Nutzer einen Graph und ein k vorgibt, zu entschieden, ob der Graph eine Clique der Größe k enthält.

In Teil b) ist das Problem vereinfacht, indem der Nutzer nur noch einen Graph eingeben kann, während das k festgelegt ist und vom Nutzer nicht verändert werden kann. Das heißt, ein Verfahren zur Lösung dieses Problems kann auf dieses k optimiert werden. Das ist beim ursprünglichen Clique-Problem nicht möglich.

Gruß,

Tobias (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Danke für deine Antwort.

Beim vereinfachten Clique Problem schaut man sich laut Musterlösung alle k elementigen Teilmengen an und multiplizierte die Anzahl jener Teilmengen mit den jeweils k^2 Möglichkeiten der Knoten Kanten zu bilden.

Wenn jetzt nun das k nicht vorgegeben ist, dann muss der Algorithmus doch genau das gleiche leisten? Warum sollte jener Algorithmus NP vollständig sein und der andere in P liegen? Was ist beim orginalen Clique Algorithmus speziell anders im Vorgehen?
0 0
Wenn man dem Nutzer die Eingabe von k überlässt, kann es passieren, ist k in der Formel für den Aufwand keine Konstante mehr, sondern kann k beliebige Werte k <= n annehmen (k > n macht wenig Sinn...) Also auch z.B. k =  n/2. Setzt man das in die Formel ein, erhält man kein Polynom mehr...

Gruß,

Tobias (Tutor)
0 Pluspunkte 0 Minuspunkte

Hallo,

die Antwort von Tobias ist vollkommen richtig und zeigt die mathematische Seite, aber vielleicht kann ich noch ein bisschen zum intuitiven Verständnis beitragen.

Wenn wir uns vorstellen, dass konstant k=10 gilt, dann ist es vielleicht ein intuitiv "schwieriges" Problem, in einem Graphen mit vielleicht n=30 Knoten nach einer Clique mit 10 Knoten zu suchen - das ist nicht anders als wenn wir das normale Clique-Problem auf diesen Graphen anwenden und k=10 setzen. Der Unterschied ist aber in der relativen Schwierigkeit, wenn die Knotenzahl n steigt (denn wir betrachten ja normalerweise den ZeitZUWACHS bei steigender Eingabelänge). Wenn wir in einem Graphen mit n=1000 nach einer Clique mit 10 Knoten suchen, dann ist das k verhältnismäßig klein und führt insgesamt zu einem nur polynomiellen Zuwachs der Laufzeit: \( O(n^k \cdot k^2) \). Ist das k nicht konstant, dann kann es mit n wachsen und wir erhalten beispielsweise mit \( k=\frac{n}{2}: O(n^{\frac{n}{2}} \cdot (\frac{n}{2})^2)\), was nicht mehr polynomiell ist.

(Das ist übrigens kein Beweis dafür, dass Clique ein schwieriges Problem ist, sondern nur eine obere Schranke. Sonst würde man ja noch schlimmere Komplexität bekommen, wenn man \(k=n\) oder noch größer setzt, aber stattdessen wird es wieder leichter, wenn sich k der Knotenanzahl n annähert. Will man zeigen, dass Clique schwer ist, muss man eine Reduktion durchführen.)

Viele Grüße

Lukas König

von uafjv uafjv Tutor(in) (168k Punkte)  
...