Effiziente kombinatorische Algorithmen 7.5 ECTS Prüfung

Die Pruefung war insgesamt sehr konsistent mit den anderen Protokollen, die man hier so liest. Es war eine entspannte Atmosphaere - wenn man nicht sofort kapiert, was gemeint war wird man vorsichtig in die richtige Richtung gestupst. Ich wurde bei einigen Laufzeiten gefragt, ob ich die exakten Werte weiss (z.B. Monien-Speckenmeyer in O*(1.83^n)).

Wir haben uns zu Beginn des Semesters nichttriviale Eigenschaften in gerichteten Graphen angeschaut. Welche war das?

Starke Zusammenhangskomponenten.

Was ist das. Definieren sie das mal.

<Definition>

Wie haben wir die jetzt berechnet.

Dfnr, tief-nr definiert.

Wir definieren die tief-nr. also ueber starke Zusammenhangskomponenten, obwohl wir die gerade erst berechnen. Wie geht das?

Es werden zunaechst die Blaetter des Superstrukturgraphen ausgegeben (Ausgangsgrad = 0). Wenn das Blatt/die starke ZHK komplett ausgegeben wurde, wird mit der naechsten Komponente weitergemacht, d.h. Crosskanten in ander ZHKs spielen praktisch gesehen keine Rolle.

D.h. in welcher Reihenfolge werden die Knoten des Superstrukturgraphen ausgegeben?

Umgekehrt topologisch sortiert.

Erklaeren sie den Algorithmus mal weiter

Tiefensuche in beliebigem Knoten starten. Jeden besuchten Knoten auf einen Stack pushen. Fuer jeden Knoten die noch unbesuchten Nachfolger besuchen. Bei Rueckkehr aus der Rekursion die Tief-nr updaten. Nachdem alle Nachfolger besucht wurden: dfnr(t) == tief(t)?

→ Falls ja: t ist erster besuchter Knoten einer starken ZHK (Einsprungspunkt in einen Knoten des Superstrukturgraphen). Die Knoten der starken ZHK werden ausgegeben (pop vom Stack).

Wenn ich ihnen das jetzt nicht glaube. Also die Tatsache, dass von ihrem Knoten t alle anderen Knoten erreichbar sind ist ja geschenkt, da man den Baumkanten folgen kann. Aber die Rueckrichtung? Also, dass t von jedem Knoten der starken ZHK erreichbar ist?

Sei t der oberste Knoten auf dem Stack fuer den gilt dfnr(t) == tief(t). Dann gilt fuer jeden Knoten v oberhalb von t auf dem Stack: dfnr(v) > tief(v) >= tief(t) == dfnr(t).

• Die erste Ungleichung gilt, da per Definition dfnr(v) >= tief(v) ist und da t der oberste Knoten ist fuer den die Gleichheit der beiden Werte gilt, muss tief(v) echt kleiner als dfnr(v) sein.
• Die zweite ungleichung gilt, da die tief-nr von t auf die minimale tief-nr seiner Kinder gesetzt werden kann. Waere tief(v) also kleiner als tief(t) wuerde man tief(t) bei der Rueckkehr aus der Rekursion auf tief(v) setzen.

Also gilt jetzt, dass tief(v) == dfnr(u) sein muss, wobei u ein Knoten oberhalb von t auf dem Stack ist. Fuer u gelten die gleichen Bedingungen wie fuer v. D.h.: tief(v) == dfnr(u) > tief(u). u ist also von v aus ueber Baumkanten, gefolgt von einer Rueckkante erreichbar. Fuer u kann man genauso argumentieren wie fuer v und man hat eine streng monoton fallende Folge von tief-nr, die (da endlich) terminiert.

Wofuer haben wir diesen Algorithmus spaeter im Semester noch einmal benutzt

2-SAT

Aha. SAT. Definieren sie das mal.

<Definition>

Und was ist dann k-SAT?

Laenge jeder Klausel ist durch k begrenzt.

Wie haben wir 2-SAT mit der Tiefensuche geloest?

• Klausel als Implikation zeigen
• Graphen aufstellen (Knoten = Variablen und deren Negation, Kanten = Implikationen)
• Starke ZHK bestimmen
• Falls eine Komponente sowohl x als auch nicht-x enthaelt ist die Formel nicht erfuellbar
• Knoten des Superstrukturgraphen mit Eingangsgrad 0 waehlen
• Dort alle Variablen so setzen, dass Literale zu FALSE evaluieren
• Komponente entfernen

Wie ist die Laufzeit des Algorithmus?

Polynomiell

Genauer

Tiefensuche in O(|V| + |E|). |V| = Anzahl der Variablen * 2. |E| = Anzahl der Klauseln * 2

Bei 3-SAT funktioniert das ja nicht mehr. Klauseln auf Implikationen abzubilden. Wie haben wir das dann geloest?

Hammingkugeln.

Erklaerung?

• Hammingdistanz definiert
• Hammingkugeln definiert
• LOCAL_SEARCH erklaert

Wie ist die Laufzeit von LOCAL_SEARCH fuer 3-SAT?

O(3^d) mit d = Rekursionstiefe.

Das ist ja bei n-Variablen schlechter als alle Belegungen ausprobieren.

Deterministischen Ansatz erklaert. Zwei Startbelegungen (alle Bits 0 / alle Bits 1). Durchsuchen der halben Hammingkugel ist ausreichend. Laufzeit O*(√3 ^n)

Dann gab es noch den Algorithmus von Monien-Speckenmeyer. Erklaeren sie den mal

<Algorithmus wie im Skript>

Wie schaut es hier mit der Laufzeit aus

t(n) ⇐ t(n-1) + t(n-2) + … + t(n-k) + poly(n)

→ Lineare Differenzengleichung aufgestellt und geloest. O*(1.83^n)

Am Ende der VL haben wir uns noch das TSP angeschaut. Definieren sie das mal.

Travelling Salesman + Definition

Wie haben wir das geloest?

Dynamische Programmierung. Formel erklaert und deren rekursive Definition aufgeschrieben.

Laufzeit?

Dominierend sind die l-elementigen Mengen → O*(2^n), was besser als Brute-Force O*((n/e)^n) ist.

Worin besteht das Problem bei diesem Loesungsansatz?

Speicherplatz liegt auch in O*(2^n)