Info 3 – lernen Alle Sätze,Definitionen und Probleme KAPITEL 1 & 2

Info 3 – lernen
Alle Sätze,Definitionen und Probleme
KAPITEL 1 & 2: DEAs und Regularität
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
DEA: Zustände & Alphabet endlich, d ist eine Funktion und keine Zuordnung (deterministisch)
Sprache: Teilmene von Sigma Stern.
Suffix: Gegenteil von Präfix
Komplementsprache: Sigma* ohne L
Regulär: Verankerung (L={a} oder L=Leer) oder Induktion (Konkat., Vereigungung und
Kleesch' Stern
SATZ: DEA ex. <=> Sprache regulär
NEA: d ist Zuordnung mit Epsilon
epsilon-Abschluss: Alle Zustände die von p mit epsilon-Übergängen erreichbar sind
Jeder NEA lässt sich in ein DEA überführen, DEA ist per Def. schon ein NEA.
Potenzmengenkonstruktion: Aus NEA (mit epsilons) mache DEA
Äquivalente Autmaten erzeugen die selbe Sprache.
NEA: epsilonübergänge lassen sich entfernen ohne dass es mehr Zustände werden: Skizze:
Es soll d'(q,a) für a genau die Zustände enthalten, in die A von q aus mit einer beliebigen
Anzahl von e-Übergängen und dem anschließenden Lesen von a kommen kann.
Pumping-Lemma regulär: |w|>n, w=uvx, uv<=n, |v|>0 Für alle i element N0
überflüssiger Zustand: von Anfang nicht erreichbar. Berechnungsaufwand: O(|Q|*|Z|)
äquivalente Zustände: selbe 'Sprache' zu Endzuständen. (einfach zu zeiten: Nicht-Äquivalenz
durch Gegenbeispiel)
Äquivalenzklassenautomat: Q'=Äquivalenzklassen von Q
Äquivalenzklassenautomat-Konstruktion: Zustände trennen in Klassen durch aufsteigende
Wortlänge, dabei werden nur die Übergänge beachtet, die ihren Ursprung in der aktuellen(!)
Klasse haben und wieder in diese zeigen (=Teil1) oder woander hinzeigen/nicht existieren
(=Teil2) Beginn mit epsilon: Trennt Q\F von F
Äquivalenzklassenautomat ist wohldefiniert aber nur dann minimal wenn überflüssige Zustände
fehlen und keine Fehlerzustünde existieren.
Rechtsinvariante Äquivalenzrelation: f.a. x,y eSgma*: ( xRy => xzRyz, f.a. z eSgma*)
Index(Relation R), Anzahl der Äquivalenzklassen die R auf der Menge (immer Sigma* und nicht
die Sprache L) bezüglich einer Sprache L erzeugt.
Nerode-Relation: xRy <=> (xz e L <=> yz e L , f.a. z eSgma*) Beweis für Nichtrelation sehr
einfach durch finden eines z. Beweis für unendlichen Index: Konstruktion eines z, für das xz in L
und yz nicht in L für z.b. festes x und variables y.
SATZ: von Nerode: Folgende 3 Aussagen sind äquivalent:
1. L wird von einem DEA erkannt
2. L ist Vereinigung aller Äquivalenzklassen EINER BELIEBIGEN rechtsinv.
Äquivalenzrel. Mit endl. Index
3. Nerode-Relation hat endl. Index
KAPITEL 3: Tms und enscheidbarkeit/berechenbarkeit
•
•
•
•
Registermaschine: Befehlszähler, Akkumulator, (mehrere) Register, Programm
DTM: Q,Sigma,Bandalphabet endlich, Blanksymbol nicht in Sigma
TMs akzeptieren Eingaben, erzeugen aber Ausgaben die u.U. nichts mit ihrer eigenen Sprache zu
tun haben: sie können Funktionen realisieren.
Halten(=stoppen): es gibt keinen Übergang mehr der passen könnte (!), muss auch in
Endzustünden gelten.
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
w akzeptieren: für w halten in F.
L akzeptieren: alle w eL akzepieren
entscheidbar (=rekursiv) Es gibt TM, die immer hält, und L akzeptiert
semi-entscheidbar (=rekursiv aufzählbar) Es gibt TM, die L akzeptiert (und für Sigma*\L undef.
ist.
Konfiguration einer TM: Aktueller Zustand aus Q, kompletter Bandzustand + Zeiger auf
Bandposition.
(Turing-)berechenbar (=totalrekursiv) (Funktion f auf Sigma*!): TM hält für alle w aus
Sigma* und auf dem Band steht danach f(w).
eine TM realisiert eine Funktion f wenn sie nur für w aus Definitionsmenge von f stoppt und
sonst undef.
Eine Sprache ist entscheidbar <=> ihre charakteristische Funktion ist berechenbar.
Church'sche These: TM ist LeadHackÜber-mächtig (es gibt nix mächtigeres)
Mehrere Bänder lassen sich mit einer TM simulieren.
Mehrere Lese/Schreibköpfe lassen sich mit einer TM simulieren.
Mehrdimensionale Bänder lassen sich mit einer TM simulieren.
Gödelnr . <M>, wenn M TM ist. 111 _code_ 11 _code_ 11 _ ... 111 dabei ist code=
0010100010010 (die nullen bedeuten die kodierung eines Eintrags in der Übergangszuordnung)
Universelle TM: erhält <M> und eingabe w und simuliert M mit w.
Diagonalsprache: Tabelle mit allen eingabewörtern und allen Gödelnummern in kanonischer
Reihenfolge: Inhalt: 1=M akzepiert w, 0= sonst (fehler oder endloslauf)
Ld ist die Sprache, die die Hauptdiagonale der Tabelle enthält: Ld={wi | Mi akzeptiert wi
NICHT!!!!!} mit i ist der Index der Tabelle. Also da wo die Tabelle eine 0 hat.
SATZ: Ld ist nicht entscheidbar. Sigma*\Ld ist nicht entscheibar.
Halteproblem: H = { wv | Tw hält für v }, sagt also für welche Eingaben die Universelle TM hält.
Und zwar gdw. wv e H.
SATZ: Halteproblem ist nicht entscheibar.
Universelle Sprache: Lu={ wv | Tw akzeptiert v }
SATZ. Lu ist nicht entscheidbar.
SATZ: Lu ist semi-entscheidbar.
SATZ von Rice: R:= Menge aller von TMs berechenbaren (mehr als nur realisierbar)
Funktionen. S nichttriv. Teilm von R. Dann gilt: L(S):={<M> | M berechnet eine Fkt aus S} ist
nicht entscheidbar.
Aus dem Satz von Rice folgt: Es ist für Programme nicht entscheibar ob ihre Sprache leer,
unendlich oder ganz Sigma* ist.
Beweisschema für Unentscheidbarkeit: Annahme A sei entscheidbar, damit kann ein
bekanntes unentscheidbares Problem entschieden werden. Widerspruch.
Postsches Korrespondenzproblem: 2er Tupel links-bzw. Rechsseitige Konkatenation muss gleich
sein für eine endliche Auswahl (mehr als keine) an Tupeln
SATZ: PKP ist nicht entscheibar
KAPITEL 4: Komplexitätsklassen P, NP, NPC und so Gedönsviecher...
•
•
•
•
•
•
Travelling Salesman Problem (TSP): Vollständiger Graph, Längenfunktion E auf Z (Ganze
Zahlen). Frage: Gibt es eine Rundtour mit Länge l<=K, K ganze Zahl.
Entscheidungsproblem: JaNein Antwort verlangt, dabei ist meist ein Parameter K.
Optimimalwertproblem: Gesucht ist der Wert der Optimalen Lösung
Optimierungsproblem: Gesucht ist die optimale Lösung
Alle 3 Probleme sind bei TSP polynomiell Überführbar. Zumindest bei TSP. Anderes ist im
Script nicht explizit erwähnt.
Kodierungsschema: ordnet jedem Problembeispiel eines Problems eine Zeichenkette oder
Kodierung über einem Alphabet Sigma zu. Verschiedene Probleminstanzen müssen versch.
Kodierungen haben. Vernünftige Kodierung ist k-är mit k>1 denn für k=1 siehe
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Pseudopolynomial und für k=0 gibt es nur eine Kodierung. Doof.
Äquivalente Kodierungsschemata s1 und s2 für ein Problem P: Es gibt 2 polynome die jeweils
die Kodierungslänge des anderen Schemas nach oben beschränken. Und zwar für alle
Probleminstanzen von P.
Probleminstanz = Problembeispiel.
Entscheidungsproblem: Lässt sich unterteilen in JA-Beispiele und Nein-Beispiele.
Sprache eines Entscheidungsproblems P mit Kodierungsschema s: Alle Wörter, die s-kodierte
Ja-Beispiele für P darstellen.
Achtung: Dieser Punkt/Definition ist im Script ein wenig LariFari...Eine TM löst ein
Entscheidungsproblem mit Kodschem. s: TM akzeptiert alles und danach steht auf dem Band ob
es ein Ja-Beispiel war oder nicht.
Zeitkomplexitätsfunktion Tm(n)=maximale anzahl von berechnungsschritten über allen
kodierten beispielen der Länge n.
Die Klasse P ist die Klasse aller Tms mit Tm(n) ist ein Polynom.
SATZ: Liegt das Enscheidungsproblem TSP in P, dann liegt auch das Optimierungsproblem in P.
Algorithmus OPT-TOUR ist polynomial und berechnet das Optimierungsproblem mit
polynomial höherem Aufwand als das Entscheidungsproblem des TSP.
NTM: Orakel schreibt links von Eingabe auf das Band und wandert dann zurück zum ersten
Zeichen der Eingabe, danach wird der Det. Teil der TM laufen gelassen.
Die Klasse NP ist die Klasse aller NTMs mit Tm(n) ist ein Polynom.
Alle Sprachen in NP sind entscheidbar.
TSP ist in NP.
Polynomiale Transformation einer Sprache L1 auf L2: Funktion f:L1->L2, TM für f in P und für
alle x auf Sigma* muss gelten: (x in L1 <=> f(x) in L2). Formal: L1 (komischer kringel mit
öffnung nach rechts) L2.
NP-Vollständig: L in NP und für alle L' auf NP: L' polynomial transformierbar in L, da pol.
Tranformationen transitiv sind, genügt es die vollständigkeit mit der Transformation von einem
einzigen NP-vollständigen Problem zu zeigen.
Problem SAT. Menge von Klauseln und Menge von Variablen. Gibt es eine Wahrheitsbelegung
der Variablen?
SATZ von Cook: SAT ist NP-vollständig: Beweis: Konstruktion von Klauseln die genau dann
erfüllt sind, wenn eine NTM akzeptiert.
Problem 3SAT: Alle Klauseln haben nur 3 Literale.
SATZ: 3SAT ist NP-Vollständig Beweis über SAT -> 3SAT.
Problem CLIQUE: Graph, Parameter K: gibt es einen zushängenden Teilgraph (Clique) mit
mind. K Knoten?
SATZ: CLIQUE ist NP-vollständig: Beweis: 3SAT->Clique: 3er Knotengruppen und verbinden,
wo sie dem selben literal entsprechen oder wenn sie sich nicht widersprechen, ausserdem werden
sie innerhalb ihere 3ergruppe nicht verbunden. 3Sat mit n klauseln entspricht dann clique im
graph mit K=n.
Problem 2SAT: nur 2 pro klausel:
2SAT ist in P: Beweis Algorithmus: Konstruiere für jede Var. Ein a und ein a quer. -Knoten
(gewichteter graph). Für eine Klausel (x,y) verbinde folgende Knoten: (xquer,y) (yquer,x), es
gibt dann eine belegung, wenn für x und xquer kein pfad nach links UND nach rechts ex., also
genau dann wenn beide pfade nicht existieren. (Johannes, hab ich das richtig verstanden?)
Max2SAT: NP-Vollständig, Beweis: 3SAT->2SAT keine Ahnung wie genau.
Problem COLOR: Graph mit K, gibt es eine Knotenfärbung mit höchstens K Farben
3COLOR: COLOR mit K=3
SATZ: 3COLOR ist NP-Vollständig. Beweis: 3SAT->3COLOR. Der graph mit den Satelitten
und den Farben a,f,t. Belegung in 3SAT entspricht dann den knoten mit denen der (einzig) fgefärbte Knoten pro Satelitt verbunden ist.
Problem EXACT COVER: Menge X und S Teilmenge von P(X) (Potenzmenge). Gibt es
Teilmenge S' von S sodass alle T auf S' paarweise disjunkt sind und ihre Vereinigung T1undT2
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
und... und Tn = X ist?
SATZ: EXACT COVER ist NP-vollständig. Beweis: 3COLOR -> EXACT COVER: Für alle
Knoten werden in die Menge X elemente Angelegt 3malNachbarschaft+3 plus das original
element v. In S gibt es für jedes v 3 disjunkte Mengen Sr Sg Sb mit jeweils nachbarschaft+1
elementen. Ausserdem noch 3 zweielementige Mengen {v,er} {v,eb} {v,eg} mit ei ist aus Si.
Interpretation: Si enspricht der Farbe i, enthält für jeden Knoten aus Nachbarscahft eine Kopie
und einen zusätzlichen Knoten ei.
Problem SUBSET SUM. Menge M + Gewichtsfunktion w M->N0 + Konstante K. Existiert
Teilmenge M' aus M mit Summe aller w(a)=K, a aus M.
SUBSET SUM ist NP-vollständig. Beweis: EXACT COVER -> SUBSET SUM. Abgespacete
Scheiße.
Problem PARTITION: Graph, Gewichtsfunktion. Gibt es eine Teilmenge, die genau die selbe
Gewichtung wie ihr Komplement hat.
PARTITION ist NP-vollständig. Beweis: SUBSET SUM -> PARTITION
Problem KNAPSACK: Menge M + Gewichtsfunktion + Kostenfunktion, W,C, alles natürlich.
Gibt es Teilmenge mit Gewichtssumme höchstens W aber Kosten mindestens C
KNAPSACK ist NP-vollständig. Beweis: PARTITION->KNAPSACK.
Für NP-vollständige Probleme L gilt: (L in P) -> (P=NP), (nicht in P)=>(alle L' in NP sind nicht
in P)
NPC ist die Klasser der NP-Vollständigen Sprachen/Probleme
NPI ist die Klasse NP\(P u NPC), also diejenigen, die in NP sind, aber nicht NP-Vollständig und
nicht in P.
Co-P ist die Klasse aller Komplemente von P-Sprachen.
Co-NP ist die Klasse aller Komplemente von NP-Sprachen.
SATZ (von Ladner): (P!=NP)=>NPI ist nicht leer.
Problem: co-TSP: Gibt es KEINE Tour mit Länge höchstens K?
Cp-TSP liegt in co-NP. Weitere Folgerungen nicht möglich.
Sei L in NPC und in co-NP => NP=co-NP
Problem:Subgraphisomorphie: egal.
Problem:Graphenisomorphie: mut zur Lücke!
Suchprobleme, Aufzählungsprobleme und Optimierungsprobleme sind Kandidaten, die nicht in
NP liegen könnten.
Suchproblem P: Dp ist die Menge der Problembeispiele und I aus Dp also Sp(I) die Menge aller
Lösungen von I. „Lösung“: Gib ein Treffer aus oder Nein, falls nix gefunden.
Problem: TSP-Suchproblem: wie TSP-Optimierungsproblem nur dass Gewichtung reell ist.
Nicht in NP.
Problem: Hamilton-Kreis(Suchproblem). Suche Hamiltonkreis (enthält jeden Knoten) in bel.
Graph. Nicht in NP.
Aufzählungsproblem P: Meine der Problembeispiele Dp. Rest wie Suchprob. „Lösung“ ist die
Angabe der Kardinalität aller existierenden Suchtreffer. |Sp(I)|
Hamilton-Kreis(Aufzählungsproblem): Anzahl der versch. Hamilton-Kreise im Graph. Nicht in
NP.
Relation Rp sind alle Tupel(SP,AP) SP Suchprob. AP Aufzählungsprob.
Funktion realisiert eine Relation wenn sie f(x)=y für x ein passendes y ausspuckt oder aber ein
epsilon, falls nichts in Relation mit x steht. x ist SP, y ist AP. (x,y) in Rp.
Orakel-Turing-Maschine: TM mit Orakelband und Antwort- und Fragezustand.
Turing-Reduktion: (kringelsymbol mit einem Altdeutschen T im Index) Seien R, R' Relationen
über Sigma*. Eine Turing Reudktion von R auf R' ist eine Orakel-Turing-Maschine deren Orakel
die Realtion R' realisiert und die selber in polynomiealer Zeit die Funktion f berechnet, die R
realisiert.
NP-Schwer. Ein Suchproblem P heiß so, wenn es ein P' in NPC gibt, das auf PÜ reduzierbar ist.
Also: Optimierungsprobleme für die das zugehörige Entscheidungsproblem NPC ist. Und
Entscheidungsprobleme die aus NP-vollst. Problemen poylnomiell reduzierbar sind aber für die
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
nicht klar ist, ob sie selbst in NP liegen.
P in NPC => P ist NP-schwer.
Problem INTEGER PROGRAMMING. mn-Matrix A, m-vektor: m-vektor b und n-vektor c, B.
Alles natürliche Zahlen. Gibt es einen n-Vektor x mit Summe aller cx = B und Summe aller Ax
kleiner gleich b für alle werte in b, bzw. Spalten in A.
INTEGER PROGRAMMING ist NP-schwer. Beweis: rofl -> lol
L ist NP-Schwer => L-Komplement ist NP-Schwer.
Pseudopolynomial: NP-Vollst. Probleme, die bei unärer Kodierung der Probleminstanzen mit
einer DTM in poylnomieller (bezügl. Länge des unären Wortes) Zeit lösbar sind.
Approximationsalgorithmus mit Differenzengarantie = absoluter Approximationsalgorithmus:
|OPT(I) – A(I)|<=K, K fest für ein existierendes A mit gegebenem Problem.
Beweisschema zur Nichtexistenz: Nimm an P!=NP. Wähle Probleminstanz I, gibt OPT(I) an,
pumpe Probleminstanz zu I' auf, sodass OPT(I')>K(OPT(I), zeige, dass A() genauso mitwachsen
muss, zeige dass A()=OPT() gelten muss => P=NP. Widerspruch zur Annahme.
Für KNAPSACK,CLIQUE lässt sich dieses Schema durchführen.
Approximationsalgorithmus mit relativer Gütegarantie: Quotient A(I)/OPT(I) ist immer
größer/kleiner (jenach Problem) als K für alle Probleminstanzen, auch nur dann wenn N!=NP
Der Greedy-Algorithmus für KNAPSACK erfüllt die Bedingung <=2 (relative Gütegarantie)
Falls P!=NP geht nicht weniger als 4/3 für KNAPSACK (relative Gütegarantie)
TSP mit Dreiecksungleichung geht mit <2 (relative Gütegarantie)
epsilon-approximativer Approximationsalgorithmus: R(I) ist kleiner gleich 1+epsilon für alle
Probleminstanzen I.
(P)AS (polynomiales) Approximationsschema: Menge von Epsilon-approximativen
Algorithmen. Poylnomial, falls alle Algorithmen poylnomial bzgl. einer Kodierungslänge von I
sind.
FPAS: Vollpolynomiales Approximationsschema: Alle Algorithmen sind polynomial bzgl.
1/epsilon
SATZ: Sei P ein Problem in NP-schwer => OPT(I) ist natürliche Zahl mit 0. und es gibt ein
polynom q das die Obergrenze von OPT(I) bestimmen kann. Also OPT(I) kleinergleich q(|I|)
SATZ: Für KNAPSACK gibt es ein FPAS-Algorithmus Mit Aepsilon ist in O(n³ * 1/epsilon)
SATZ: Sei P ein Optimierungsproblem => OPT(I) ist in N0, und es gibt ein Polynom q mit OPT
(I) kleinergleich (q(I)+max#(I)). max# ist die größte in I vorkommende Zahl..
•
KAPITEL 5:Chomsky n Friends
•
•
•
•
•
•
•
•
•
•
Grammatik G=(Alphabet Sigma,Nichtterminale V, S, Ableitungsregeln R)
Sprache, die eine Grammatik erzeugt: alle Wörter die aus S mit bel. Vieleln R's entstehen
können. Und zwar nur die ohne Nichttterminale (Variablen)
Jede Grammatik G hat CH-0-Typ. Jede Grammatik ist semi-entscheidbar(=rekursiv aufzählbar)
CH-1-Typ bedeutet: Epsilon nur als S->epsilon erlaubt, u->v mit |u| kleinergleich |v| mit u nur
Nichtterminale (mehr als 0) und v beliebig (aber halt nicht epsilon und nicht kürzer als u.
Formale Bezeichnung: kontextsensitiv. Es macht keinen Unterschied, ob man auch für u
Terminale zulassen würde, da gibt es sicherlich einen passenden Konstruktionsalgorithmus. CH1-Klasse ist genau die Klasse NTAPE(n) (s.u.)
CH-2-Typ: kontextfrei: A->v, A ist genau 1 Nichtterminales zeichen und v beliebig.
CH-3-Typ: rechtslinear (Linkslinear wurde nur im Goos definiert, also nicht klausurrelevant): A>epsilon oder A-> aB , A,B Nichtterminale Zeichen und a ist element Sigma. CH-3-Klasse ist
genau die Klasse der NEAs/DEAs (ist ja egal was).
DTAPE(s(n)) sind alle Sprachen von DTMs mit Platzbedarf s(n)
NTAPE(s(n)) sind alle Sprachen von NTMs mit Platzbedarf s(n)
NTAPE(s(n)) = NTAPE(n), falls s nur linear ist.
CLIQUE gehört zu NTAPE(n)
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Syntaxbaum = Ableitungsbaum. Buchstaben in Kringel und neue Teilwörter nach unten auf
selber Höhe.
Links(rechts)ableitung: in jedem Schritt wird nur das am weitesten Links(rechts) stehende
Zeichen abgeleitet.
Eindeutige Grammatik: für jedes Wort ist der Ableitungsbaum eindeutig, die Sprache heißt dann
eindeutig wenn es für sie eine (eventuell andere) Grammatik gibt
Inhärent mehrdeutige Grammatik/Sprache: nicht eindeutige Grammatik/Sprache.
Nochmal: Eine eindeutige Sprache kann auch inhärent mehrdeutige Grammatiken besitzen. Aber
sie muss auf jeden Fall mind. 1 eindeutige Grammatik besitzen.
Chomsky-Normalform: A->BCoder A->a epsilon nur so erlaubt: S'->epsilon, S'->S.
Ch-Normalform ex. f. a. CH-2-Grammatiken und umgekehrt. (Achtung: gilt nicht für epsilonGrammatiken)
SATZ (cocke-younger-kasami): Es gibt einen Algorithmus in P der für w prüft ob es in einer
kontextfreien Grammatik ist: Bilde Pyramide und die Grammatik in CH-Normalform. Spiele rum
bis oben ein S steht, wenn nicht, geht's net.
Pumping-Lemma für Kontextfreiheit: |z|>=n z=uvwxy mit |vx|>=1, |vwx|<=n und uv(i)wx(i)y ist
in L für alle i aus N0. Nur für Widerspruchsbeweise geeignet. (also um Nicht-Kontextfreiheit zu
zeigen)
Odgens Lemma: Es gibt ein n mit in |z|>=n könen wir mind. n Buchstaben markieren sodass bei
z=uvwxy mind 1 markierter Bst in vx liegt und höchstens n in vwx liegen. Und: Mit (i) wie beim
Pumpinglemma
SATZ: CH-3 teilm. CH-2 teilm. CH-1 teilm. CH-0
eine nutzlose Variable in einer Grammatik: Sie wird nirgendwo erzeugt
SATZ: Die Menge der nutzlosen Variablen kann in polynomieller Zeit berechnet werden.
Insbes. Kann S nutzlos sein, somit ist L(G) leere Menge gdw. S nutzlos ist. (G kontextfrei!!!)
G kontextfrei: ion polynomaler Zeit entscheibar, ob L(G) endlich.
Kontextfreiheit ist abgeschlossen bzgl. Vereinigung, Konkatention und Kleescher Abschluss
(Stern)
Kontextfreiheit ist nicht abgeschlossen bzgl. Schnitt und Komplementbildung.
Greibach-Normalform: A->aw, a terminal, w ein Wort aus V* (also nur Variablen)
SATZ: G ist kontextfrei und enthält kein epsilon <=> es gibt Greibachnormalform
Kellerautomat (PDA): Q,Sigma,Stackalphabet endlichZ0 initialisierung, anfangs,endzustand,
übergangsfunktion delta d.
Deterministischer PDA: |d(q,a,Z) + d(d,epsilon,Z)| höchstens 1, ansonsten nichtdeterministisch:
NPDA.
SATZ: NPDA, PDA, Kontextfrei, Greibach-Normalform, Chomsky-Normalform, CH-2 sind
genau die selben Klassen. Alle! Achtung mit epsilon bei den Normalformen. Wird aber in der
Klausur nicht vorkommen, wurde gesagt.
PDA,NPDA akzeptieren entweder durch leeren Stack oder durch Endzustand oder durch beides,
solche Kellerautomaten sind alle ineinander überführbar.
SATZ: Das Problem für kontextfreie Grammatiken G1 und G2 zu entscheiden, ob ihr Schnitt
leer ist, ist nicht entscheidbar.
Das Problem für eine kontextfreie Grammatik G zu entscheiden, ob sie eindeutig (siehe
Syntaxbaum) ist, ist nicht entscheidbar.
BM ist die Sprache der korrekten Rechenwege einer TM M. BM besteht aut
w1#w2R#w3#w4R#... also abwechselnd ein R oben drauf, aber der index wird immer erhöht.
Und es beginnt immer mit w1. w sind kodierte Konfigurationen der TM.
Für alle TM ist BM der Schnitt der Sprache von 2 kontextfreien Grammatiken.
Sei M TM die mind. 2 Schritte ausführt für alle Eingaben => BM ist genau dann kontextfrei,
wenn L(M) endlich ist.
Für jede TM M ist das Komplement (BM)c von BM kontexfrei.
SATZ: G1, G2 sind alle kontextfrei, folgende Enscheidungsprobleme sind nicht Entscheidbar:
1. schnitt G1 und G2 ist kontextfrei.
•
•
2. L(G1) = Sigma*
3. L(G1)=(G2)
4. L(G1) ist Teilmenge von L(G2)
SATZ: Sprache L={a(i) b(j) c(k) | i=j oder j=k}, L ist inhärent mehrdeutig, aber kontextfrei.
Folgende Probleme sind nicht semi-entscheidbar:
1. Erfüllbarkeitsproblem der Prädikatenlogik
2. Komplement des Halteproblems.
Wichtige Stichworte aus den Übungsblättern und alten Klausruen(also vielleicht Klausurrelevant
sind) :
Huffman-Codierung
Präfixfrei
Regulären Ausdruck für einen DEA finden.
DEA für einen Regulären Ausdruck finden.
Rechnen mit folgenden Operatoren für Reguläre Sprachen: Schnitt, Vereinigung (+),
Konkatenation, \, /, Kleescher Stern, einfache Hochzahlen.
Gleichungssyteme mit Sprachen lösen: A=bBB, B=A + bb, C=AB\aC oder so...
Beweis: endliche Sprachen sind regulär.
Beweis: Ein Automat akzeptiert eine bestimmte Sprache. L(A)=L mit Teilmenge in beide
Richtungen ist der korrekte Beweis, dabei muss L(A) informell erklärt werden.
Beweis: (A schnitt B)* = A* schnitt B* ist falsch, Gegenbeispiel.
Beweis: (A u B)* = A* u B* ist falsch: Gegenbeispiel.
Selber Beweis: Unter der Annahme A teilmenge B.
Sprache von DEA erkennen mithilfe der Methode aus dem
Script: L(qr,i+1,qt) = L(qr,i,qt) u (L(qr,i,qi+1)(L(qi+1,i,qi+1))*L(qi+1,i,qt)) Auswendig
lernen!!!
epsilon-Übergänge am NEA eliminieren: Für jedes Epsilon: Skizze: Es soll d'(q,a) für a genau die
Zustände enthalten, in die A von q aus mit einer beliebigen Anzahl von e-Übergängen und
dem anschließenden Lesen von a kommen kann. Also an allen Blättern von einem 'epsilonBaum' die beginnenden Kanten kopieren und ihren Anfang an die wurzel des baumes setzen, die
kantenenden bleiben an der gleiche stelle, gilt auch für reflexive kanten, reflexive epsilonübergänge
können einfach so gelöscht werden. Mit diesem Verfahren bleibt die anzahl der zustände gleich.
Potenzmengenkonstruktion: geht auch mit epsilonübergängen.
Beweis L= a hoch p, p prim ist nicht regulär. z.b. mit Pumpinglemma.
Beweis: L= a hoch 2i ist regluär. Angabe eines DEA
Beweis: L= a hoch (2 hoch i) ist nicht regulär: beweis.Pumpinglemma.
Gleichung: X=AX u B Mögliche Lösung: X=A*B
Beweis: Automat für eine Sprache hat eine Minimale Zustandsmenge. Entweder informell oder
DEA konstruieren und dann Äquivalenzklassenautomat bilden.
Beweis: (AB u A)*A = A(BA u A)* ist wahr. Durch ganz formale Zerlegung der einzelnen Seiten
der Gleichung.
Beweis: A(AB u B)* = AA*B(AA*B)*A* ist falsch durch gegenbeispiel. aba
Beweis: Regulär ist abgeschlossen unter komplementbildung: Konstruktion eines Negations-DEA.
Beweis: Regulär ist abgeschlossen unter Schnitt: L=(Lc vereinigt Lc)c ist gleich L schnitt L
Beweis: Minimalität von DEA: Gegenbeispiel für alle Zustandspaare. Auch Endzustände.
Beweis: L={a(j)b(k)c(l) | j,k,l => 0, und k=l falls j=1} Zeigen, dass Pumpinglemma erfüllt ist unter
der Annahme L sei regulär. Daraus folgt, dass PL nur zu Widerspruchsbeweisen benutzt werden
kann.
Beweis: obiges L ist nicht regulär: L=ab(n)c(n) vereinigt mit aaa*b*c* und der erste Teil ist nicht
regulär, dafür der zweite Teil. Da beide Teile disjunkt sind, gilt dass L nicht regulär sein kann.
Beweis: NEAs können in einen NEA mit nur einem Endzustand überführt werden.
Beweis: Für NEAs ohne epsilon gibt es einen NEA ohne epsilon mit max. 2 Endzuständen.
Beweis: Nicht zu jedem NEA ohe epsilon gibt es einen NEA ohne epsilonmit max. 1 Endzustand.
Gegenbeispiel.
Beweis: Ein DEA ist eindeutig bzgl. seiner Sprache, wenn er Zustandsminial ist.
Potenzmengenkonstruktion
Beweis: es gibt keinen DEA mit weniger als K zuständen: Potenzmengekonstruktion.
Pumplinglemma benutzen für : Gerade Palindrome
PL für a(n+i+j)b(n+i)c(n) mit n=>0, i,j>0
PL für Sprache aller wörter die mehr 0en als 1en enthalten.
L=0 hoch k, k ist vielfachen von p oder q, mit p teilerfremd q, dann hat jeder DEA mindestens pq
zustände.
TM konstruieren, die die Differenz zwischen der anzahl von a und b als a auf band schreibt.
Beweis: Rechts-Turingmaschine: Sie kennt kein L,N, sondern nur R. Eine Rechts-TM ist genau so
mächtig wie reguläre Sprachen.
Busy-Beaver-Problem. BBP: ist nicht berechenbar.
Beweis: Äquivalezrelationen und ihre eigenschaften benutzen.
Kontruktion eines Äquivalenzklassenautomaten.
Beweis: ein NEA hat wörter größer n => L ist unendlich.
Beweis: gerade Palindrome sint nicht regulär (Pumpinglemme, oder Neroderel. Hat unendlich
großen index)
Äquivalenzklassen einer Sprache auf Sigma* bzgl. Nerode-Relation bestimmen.
Beweis: Die Sprache aller Turingmaschinen(Gödelkodiert) mit M entscheidet Leere Menge ist nicht
entscheidbar, da KEINE AHNUNG
Das komplement der Sprache ist semi-entscheidbar.
PKP ist entscheidbar für |Sigma|=1;0, in alen anderen Fällen nicht entscheidbar, auch wenn =1 dabei
ist. z.b. |Sigma|=1;4;5;6;7;...
Konfigurationsverlauf für ein Beimmtes Wort in TM, in NPDA, PDA.
Sprache einer TM angeben, informelle Begründung.
Platzbeschränkte TM sind nicht so mächtig wie TMs, z.b. lässt sich für sie das Halteproblem
entscheiden. Beweis. Algorithmus der das kann angeben.
TM angeben, die die Eingabe um 1 nach rechts verschiebt.
2-Band-TM lässt sich in O(T²(n)) mit einer DTM silmulieren, wenn diese den Aufwand T(n) hat.
Genau darauf achten, dass der Aufwand polynomiell zur KODIERTEN eingabe ist, also damit
können noch e-Funktionen eliminiert werden.
PKP ist entscheidbar wenn alle Wörter die selbe Länge haben.
TM die kanonische Aufzählung vollzieht.
Beweise:
1. L1, L1c sind semi-entscheidbar => L1 ist entscheidbar.
2. Semi-entscheidbarkeit ist unter komplement bildung nicht abgeschlossen (halteproblem)
3. semi-entschdeidbarkeit ist unter Vereinigung/Schnitt abgeschlossen.
4. L1, L2 semi-entscheidbar => L1\L2 semi-entscheidbar.
5. Min(L1) mit kein echtes Präfix(suffix auch möglich) ist entscheidbar, wenn L1
entscheidbar ist. (damit ist keine Äquivalenz beweisen <=>!!!)
LÄQUI ist nicht entscheidbar L={u#v | Tu und Tv entscheiden die selbe Menge } Beweis: H0 auf
LÄQUI transformieren.
Andere Definition für NTM möglich: automatenteil ist nicht-deterministisch. Beweisen, dass diese
Sprache genau die der normalen NTMs (Orakel) ist.
Beweis: Polynomiale Transformierbarkeit ist Äquivalenzrelation auf P.
Index bestimmen von Pol. Transf auf P.
RSA-Verschlüsselung: Aufwand polynomiell. n=pq (p,q prim) e teilerfremd mit (p-1)(q-1), d<n mit
ed rest 1 bei mod n. Öffentlich: (n,e) privat (n,d); Nachricht x wird kodiert (xhoch e)mod n;
Entschlüsseln: x =( y hoch d) mod n. Angriffe liegen nicht mehr in P.
Satelitten-Graph für 3SAT -> 3COLOR angeben.
Transformation von CLIQUE auf INDEPENDENT SET.
Beweis: P=NP => P\{leere menge und Sigma*} ist genau die Klasse NPC.
Beweis: Leere Menge und Sigma* sind nicht NP-Vollständig, da keine Transformation von einem
NP-vollst. Auf die beiden existieren kann, da diese Triviale Probleme (konstanter Aufwand) sind.
Beweis: TSP ist stark-NP-vollständig (also nicht pseudopolynomial)
Beweis: Nicht-Existenz einen aapproxalg für CLIQUE, falls P!=NP
EXACT COVER als INTERGER PROGRAMMING formulieren: (hardcore): x repräsentiert die
vorkommen der teilmengen in S' und a die vorkommen der elemente in ihren Teilmengen. b ist
immer 1.
NP-Probleme sind bzgl. Komplement nicht abgeschlossen,
PLÄTZCHENDOSENPROBLEM (PDP): n gleiche Dosen, Plätzchen mit ganzzahligem Gewicht.
Entscheidung: passen die plätzchen in die Dosen?
Alle Probleme in der Übersicht:
Halteproblem – alle wv mit Tw hält für v.
Ho – Halteproblem für leere Eingabe ist nicht entscheidbar.
Diagonalsprache – alle wi mit Twi akzeptiert wi nicht. (i ist index auf tabelle)
Universelle Sprache – alle wv mit Tw akzeptiert v
Post'sches Korrespondenzproblem (PKP) Tupelauswahl gesucht damit Gleichheit
Travelling Salesman Problem (TSP), Optw, Optimier., Entsch.; Graph+ganzzahlige Gewichtung,
alle Knoten mind. Einmal in der Lösung dabei.
Co-TSP: Gibt es keine Tour mit Länge höchstens K
SAT Gibt es eine Wahrheitsbelegung über (verschieden großen) Klauseln
3SAT : SAT mit 3er-Klauseln (Transformation von 3SAT)
Max3SAT: NP-Vollständig.
CLIQUE: gibt es vollst. Teilgraph mit |V'|>=K?
k-CLIQUE: ist in P. Gibt es Clique mit größe mind. k. Beweis: Der Aufwand ist in O(n hoch k)
mal O(p(n)).
CLIQUE-Cover: Gibt es max. K vollst. Teilgraphen die disjunkt sind zusammen genau V ergeben?
=> NP-Vollständig.
2SAT: 2er-Klauseln
Max2SAT: 2er-Klauseln und K, gibt es Belegung dass mind. K Klauseln erfüllt sind.
COLOR: Graph, K. K-Farbbelegung gesucht. JaNein als Antwort.
3COLOR: Graph: Gibt es 3er-Färbung?
EXACT COVER: Überdeckung von Teilmengen exakt möglich?
SUBSET SUM: Teilmengen gewichtungssumme ist genau = K
PARTITION: Gibt es Teilmenge mit dem selben Gewicht wie ihr Komplement?
KNAPSACK: Gibt es Teilmenge mit: Gewicht höchstens W, und Kosten mindestens C?
Subgraphisomorphie: würg.
Graphenisomorphie: würg
INTEGER PROGRAMMING, Ax<=b, cx=B
BUSY-BEAVER: BBP. Ist nicht berechenbar.
Sortierung von nat. Zahlen nach Differenz.
LINEAR INEQUALITIES System von Gleichungen c11X1 + ... + c1nXn >= d1 mit c,d Gegeben
und Belegung X gesucht, sodass alle Gleichungen erfüllt sind. => NP-Vollständig. Transformation
von 3SAT.
HAMILTON-KREIS (HASSSSEEEE): NP-Vollständig.
EULERKREIS: in P
Alle NP-Probleme sind in 2 hoch p(n) entscheidbar. Mit Polynom p abhängig vom Problem.
p Permutation mit k Elementen dann ist p hoch k gleich der identität.
COMMON SUPERSEQUENCE (CSS): (u,v,n) wenn u und v eine gemeinsame SS der länge n
besitzen. Shortest CSS ist NP-Vollständig. CSS ist in P.
INDEPENDENT SET (IS): Teilmenge mind. K Knoten ohne interne Kanten. => NP-Vollständig.
IN-PLACE-ACCEPTANCE (IPA): Gegeben TM und Eingabe x der Länge n. Frage: berechnet
TM x nur auf n Bandzellen und sonst nirgendwo? PSPACeE ist wohl die Klasse der TMs deren
Platzbedart polynomial zur Eingabelänge ist.
NEAR-TAUT: Gegeben Variablenmenge Klauselmenge gibt es eine Variablengelegung so dass
nicht alle Klauseln erfüllt sind. Liegt in co-NP.

Download Report