127 lines
6.3 KiB
Markdown
127 lines
6.3 KiB
Markdown
# Frage-Muster für Lern-Prüfung: aak
|
||
|
||
---
|
||
|
||
## BAUSTEIN: CliqueAndIndependentSet-Problem
|
||
|
||
### Subbaustein: Clique: Knotenmenge, in der je zwei Knoten durch eine Kante verbunden sind
|
||
**Muster:** Wann ist eine Knotenmenge C ⊆ V eine Clique in einem Graphen G = (V, E) und welche Bedingung müssen alle Knotenpaare einer Clique erfüllen?
|
||
|
||
### Subbaustein: Independent Set: Knotenmenge ohne Kanten zwischen je zwei Knoten
|
||
**Muster:** Was ist die formale Definition eines Independent Set in einem Graphen G = (V, E) und welche Bedingung muss für je zwei Knoten eines Independent Set gelten?
|
||
|
||
### Subbaustein: Komplementgraph: Independent Set in G ist Clique in G̅
|
||
**Muster:** Welche Beziehung besteht zwischen einem Independent Set in G und einer Clique in G̅, warum sind die Probleme gegenseitig in Polynomialzeit aufeinander reduzierbar, und was bleibt bei der Bildung des Komplementgraphen gleich bzw. ändert sich?
|
||
|
||
### Subbaustein: K-CLIQUE ⪯ K-INDEPENDENT-SET mittels Komplementgraph
|
||
**Muster:** Wie transformiert man eine Instanz (G, k) von CLIQUE in eine Instanz von INDEPENDENT-SET, und bleibt die Größe k bei der Reduktion erhalten?
|
||
|
||
### Subbaustein: NP-vollständig via gegenseitige Reduktion über Komplementgraph
|
||
**Muster:** Wie folgt aus Korollar 6.18 die NP-Vollständigkeit von Independent Set, und welche untere Schranke für die Laufzeit von Algorithmen für Independent Set folgt aus der ETH?
|
||
|
||
### Subbaustein: Existenz von IS bzw. CLIQUE der Größe k ist NP-vollständig
|
||
**Muster:** Durch welche Polynomialzeitreduktion lässt sich zeigen, dass Independent Set NP-schwer ist, und wie wird in Satz 6.26 die NP-Schwere von k-Clique bewiesen?
|
||
|
||
### Subbaustein: Beide Probleme sind in NP (Verifizierer existiert)
|
||
**Muster:** Welche Eigenschaft müssen Zertifikat und Verifizierer für die Probleme k-Clique und k-Independent-Set erfüllen?
|
||
|
||
### Subbaustein: Konsequenz: P = NP falls eines in P
|
||
**Muster:** Welche fundamentale Konsequenz ergibt sich aus Satz 6.16, wenn ein NP-vollständiges Problem in P liegt?
|
||
|
||
### Subbaustein: Formale Sprachen: CLIQUE und INDEPENDENT-SET
|
||
**Muster:** Wie sind die formalen Sprachen CLIQUE und INDEPENDENT-SET über dem Alphabet Σ = {0, 1} kodiert und welche Struktur haben sie?
|
||
|
||
### Subbaustein: Eingabe/Ausgabe von k-Clique und k-Independent-Set
|
||
**Muster:** Was ist die Eingabe und was die Ausgabe bei den Entscheidungsproblemen k-Clique und k-Independent-Set?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: Reduktion CLIQUE → CLIQUE-NOMEMBER
|
||
|
||
### Subbaustein: Füge isolierten Knoten v zu G hinzu: G' = G ∪ {v}
|
||
**Muster:** Wie wird bei der Reduktion von CLIQUE auf CLIQUE-NOMEMBER der neue Graph G' konstruiert, und welche Elemente werden gegenüber der ursprünglichen Instanz verändert?
|
||
|
||
### Subbaustein: v ist in G' in keiner k-Clique (isoliert)
|
||
**Muster:** Warum kann der hinzugefügte Knoten v in keiner gültigen k-Clique von G' enthalten sein, und welche Eigenschaft hat der Knoten v in der konstruierten Instanz (G', v, k)?
|
||
|
||
### Subbaustein: G hat k-Clique ⟺ G' hat (k+1)-Clique mit v
|
||
**Muster:** Wie hängt eine k-Clique in G mit einer k-Clique in G' zusammen, und warum bleibt die Cliquengröße k bei der Reduktion unverändert?
|
||
|
||
### Subbaustein: Polynomielle Transformation
|
||
**Muster:** Warum ist die beschriebene Reduktion von CLIQUE auf CLIQUE-NOMEMBER in polynomieller Zeit berechenbar?
|
||
|
||
### Subbaustein: CLIQUE: Eingabe Graph G, Frage: existiert K-clique?
|
||
**Muster:** Was ist die Eingabe und was ist die Frage beim Entscheidungsproblem CLIQUE?
|
||
|
||
### Subbaustein: CLIQUE-NOMEMBER formal definiert
|
||
**Muster:** Wie ist das Problem CLIQUE-NOMEMBER gemäß Skript 6.50 formal definiert?
|
||
|
||
### Subbaustein: Reduktion beweist CLIQUE-NOMEMBER ∈ NP-vollständig
|
||
**Muster:** Welche drei Bedingungen müssen erfüllt sein, damit CLIQUE-NOMEMBER als NP-vollständig gilt?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: Independent Set
|
||
|
||
### Subbaustein: Independent Set S⊆V: keine Kante zwischen je zwei Knoten in S
|
||
**Muster:** Welche Bedingung muss für je zwei Knoten eines Independent Set gelten und was bedeutet es, dass die Knoten eines Independent Set paarweise nicht adjazent sind?
|
||
|
||
### Subbaustein: Komplementär zur Clique
|
||
**Muster:** In welchem Graphen entspricht ein Independent Set einer Clique und wie hängt ein Independent Set in G mit einer Clique im Komplementgraphen G' zusammen?
|
||
|
||
### Subbaustein: NP-vollständiges Problem
|
||
**Muster:** Welche Komplexitätsklasse enthält Independent Set und wie wurde dies bewiesen?
|
||
|
||
### Subbaustein: INDEPENDENT-SET = {(G,k) | G enthält unabhängige Menge der Größe ≥k}
|
||
**Muster:** Welche Sprache formalisiert das Entscheidungsproblem Independent Set?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: Tiefensuche (DFS) für Zykluserkennung
|
||
|
||
### Subbaustein: Weiß/Grau/Schwarz: Farbcodierung der DFS
|
||
**Muster:** Welche Farbe hat ein Knoten während er von der DFS bearbeitet wird, welche nach Abschluss, und wann wird ein Knoten in der DFS schwarz gefärbt?
|
||
|
||
### Subbaustein: Tree Edge (weiß): Kante zu unbesuchtem Knoten
|
||
**Muster:** Welche Kante wird als Tree Edge bezeichnet?
|
||
|
||
### Subbaustein: Rückkante (grau → weiß): signalisiert Zyklus
|
||
**Muster:** Zu einem Knoten welcher Farbe muss eine Kante führen, um einen Zyklus anzuzeigen?
|
||
|
||
### Subbaustein: DFS-Zykluserkennung in O(V+E) bei adjacency List
|
||
**Muster:** Warum beträgt die Laufzeit der DFS-Zykluserkennung bei Adjazenzliste Θ(|V|+|E|)?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: Turingmaschine für 0^n (Zweierpotenz)
|
||
|
||
### Subbaustein: Eingabe: n Nullen in unärer Codierung
|
||
**Muster:** In welcher Codierung wird die Eingabezahl n der TM für 0^n dargestellt?
|
||
|
||
### Subbaustein: Akzeptiert nur wenn n = 2^k für ein k ≥ 0
|
||
**Muster:** Nach welchem Kriterium entscheidet die TM, ob eine Eingabe akzeptiert wird?
|
||
|
||
### Subbaustein: Phase 1: Markiere jede zweite 0 mit x (alternierend)
|
||
**Muster:** Wie markiert die TM die Nullen im ersten Schritt?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: 3-SAT zu 3-Färbung Reduktion
|
||
|
||
### Subbaustein: Knotenzahl linear in Variablen und Klauseln
|
||
**Muster:** Aus welchen Komponenten setzt sich die Knotenmenge V der konstruierten Instanz zusammen?
|
||
|
||
### Subbaustein: Dreieck erzwingt drei verschiedene Farben für die drei Knoten
|
||
**Muster:** Warum benötigen die drei Knoten xi, x̄i und vi eines jeden Dreiecks drei verschiedene Farben?
|
||
|
||
---
|
||
|
||
## BAUSTEIN: MC-Knapsack
|
||
|
||
### Subbaustein: Ziel: Maximierung des Gesamtwerts
|
||
**Muster:** Was ist die Zielfunktion beim Maximum-Cut Knapsack Problem?
|
||
|
||
---
|
||
|
||
**Gesamt: 28 Frage-Muster**
|