Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2018-03

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:effi-2018-03 [05.04.2018 10:21] – angelegt ThiloKpruefungen:hauptstudium:ls12:effi-2018-03 [05.04.2018 12:14] (aktuell) – ThiloK
Zeile 9: Zeile 9:
   * Sonderbehandlung der DFS-Wurzel: Wie und warum?   * Sonderbehandlung der DFS-Wurzel: Wie und warum?
   * Laufzeit inkl. Begründung (war ihm in der Vorlesung ja schon wichtig: __Kanten__ sind ausschlaggebend!)   * Laufzeit inkl. Begründung (war ihm in der Vorlesung ja schon wichtig: __Kanten__ sind ausschlaggebend!)
-  * Warum Aufwand pro Kante konstant? Was ist der Aufwand pro Kante?+  * Warum Aufwand pro Kante konstant? Was ist der Aufwand pro Kante __vor__ rekursivem Abstieg? (Knoten bereits besucht, wenn ja tief aktualisieren, wird pro Aufruf/Kante gemacht, daher konstant)
  
 **SAT**: **SAT**:
Zeile 18: Zeile 18:
   * Was genau sind die Zustände hj? ⇒ Anzahl Schritte bis zum Endzustand ("hitting")   * Was genau sind die Zustände hj? ⇒ Anzahl Schritte bis zum Endzustand ("hitting")
   * Schreiben sie das lineare Gleichungssystem hin ⇒ hj = 1/2 (hj-1, hj+1) + 1; h0 = h1 + 1; hn = 0   * Schreiben sie das lineare Gleichungssystem hin ⇒ hj = 1/2 (hj-1, hj+1) + 1; h0 = h1 + 1; hn = 0
-  * Warum kann man das Lösen? Wissen Sie die Lösung ⇒ n+1 Variablen, n+1 Gleichungen, hj = n^2 - j^2+  * Warum kann man das Lösen? Wissen Sie die Lösung ⇒ n+1 Variablen, n+1 Gleichungen (Matrix hat vollen Rang), hj = n^2 - j^2 daher schlechtestenfalls quadratische Laufzeit
  
-Ich wurde noch nach dem Algorithmus aus der Übung mit Hamming-Balls gefragt, da war ich blank, war aber nicht weiter tragisch. Insgesamt dadurch dann "nur" 1.3 - sonst sehr angenehme Stimmung, wie ja auch den anderen Protokollen zu entnehmen ist.+Ich wurde noch nach dem Algorithmus Local_Search für 3-SAT aus der Übung mit Hamming-Balls gefragt, da war ich blank, war aber nicht weiter tragisch. Insgesamt dadurch dann "nur" 1.3 – sonst sehr angenehme Stimmung, wie ja auch den anderen Protokollen zu entnehmen ist.