====== Effiziente kombinatorische Algorithmen 7.5 ECTS Prüfung ======

{{indexmenu>:pruefungen:hauptstudium:ls12:effi-2022-02-23#1|navbar}}

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)).

===== Fragen =====

**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)