Sorry für die Verspätung musste selber BuK lernen und das macht man am besten wenn man es tatsächlich macht :(
Berechenbarkeit
Die müssen drauf sein...
Diagonalsprache D={⟨M⟩w∣M akzeptiert ⟨M⟩ nicht}
Halteproblem: H={⟨M⟩w∣M ha¨lt auf w}
spezielle Halteproblem: Hϵ={⟨M⟩∣M ha¨lt auf der Eingabe ϵ}
Allgemeine Halteproblem: Hall={⟨M⟩w∣M ha¨lt auf jeder Eingabe}
PKP: Kein Bock das hier nochmal zu erklären guckt es euch bei Reduktionen an.
NP
Am besten kennt ihr die jetzt schon auswendig... Aber ich muss sie ja auch noch lernen. Ich schreib hier nur die Entscheidungsvariante, die anderen sind zwar auch potenziell wichtig aber halt nicht soooo.
CLIQUE
Eingabe: Graph G=(V,E), k∈{1,...,∣V∣}
Frage: enthält G eine k-Clique? Heißt jedes Knotenpaar ist mit einer Kante verbunden, heißt alle Knoten sind voll verbunden.
KNAPSACK (KP)
Eingabe: n Gegenstände (I) jedes mit Gewicht wi∈W und Wert vi (i∈n) und eine maximales Gewicht W
Frage: gegeben V∈N, gibt es eine Teilmenge I′⊆I mit ∑i∈I′wi≤W und ∑i∈I′vi≥V?
BIN PACKING (BPP)
Eingabe: n Gegenstände (I) jedes mit Gewicht wi∈W
Frage: gegeben k∈N, gibt es eine Funktion f:n→k so dass ∀i∈k:∑j∈f−1(i)wj≤b, also passen die Gegenstände in k Behälter.
TSP
Eingabe: Graph G=(V,E), c(i,j)∈N für alle i,j∈∣V∣ mit c(i,j)=c(j,i)
Frage: gegeben b∈N, gibt es eine Tour mit der Länge höchstens b.
SAT
Eingabe: Formel ϕ in KNF (Konjuktiver Normalform, also (x1∧x2)∨(x3∧x4))
Frage: gibt es eine erfüllende Belegung für ϕ?
3-SAT
Eingabe: Formel ϕ in KNF, aber mit nur drei Variablen pro und verknüpfun (Konjuktiver Normalform, also (x1∧x2∧x3)∨(x1∧x2∧x3))
Frage: gibt es eine erfüllende Belegung für ϕ?
COLORING
Eingabe: Graph G=(V,E), k∈∣V∣
Frage: gibt es eine k-Farbierung von G? Heißt gibt es ein c:V→k so dass für alle Nachbarn unterschiedliche Farben haben: ∀e={u,v}∈E:c(u)=c(v)
SUBSETSUM
Eingabe: ai,...,an∈N, b∈N
Frage: gibt es eine Teilmenge K⊆n so dass ∑i∈Kai=b?
HAMILTONKREIS (HC)
Eingabe: Graph G=(V,E)
Frage: gibt es einen Hamiltonkreis in G? Heißt gibt es einen Kreis so dass jeder Knoten genau einmal besucht wird.
DHC ist genau das gleiche nur mit einem gerichteten Graphen.
Das auswählen passender Probleme ist eure Sache...
Viel Glück.
Spass Spaß Spas
?Rossmanith Zitate Quiz: Ist es ein Rossmanith Zitat oder nicht?
""
*eventuell sind ein paar Zitate frei erfunden. Sendet mir mehr: [email protected]