Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2017-01 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:hauptstudium:ls12:effi-2017-01 [05.04.2017 15:08] (aktuell) – angelegt vvalter | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | DFS: | ||
+ | * Was ist eine nichttrivale Eigenschaft die wir auf gerichteten Graphen mit Tiefensuche berechnet haben? => Starke Zusammenhangskomponenten erkennen | ||
+ | * Was ist eine starke Zusammenhangskomponenten? | ||
+ | * Wie macht man das? => Tiefnummer etc. erklären. Erster Knoten mit tief == dfnr. Superstrukturgraph und Knoten mit Ausgangsgrad 0 der Reihe nach abgehen (Tiefensuche macht das automatisch). | ||
+ | * Wie war das mit Crosskanten? | ||
+ | * Was waren 2 Anwendungen die wir in der Übung gemacht haben? => Entscheiden ob ein endlicher Automat eine endliche Sprache akzeptiert und topologische Sortierung. (Hier waren explizit Anwendungen aus der Übung gefordert. 2SAT gilt nicht) | ||
+ | |||
+ | SAT: | ||
+ | * Definieren sie SAT. | ||
+ | * Erklären sie den Algoritmus von M&S | ||
+ | * Wie ist die Laufzeit. => Rekursionsgleichung aufstellen und charakteristisches Polynom. Es wurde gefragt welche Nullstelle es für k=3 hat, aber ist nicht schlimm wenn man das nicht weiß. | ||
+ | * Wir haben auch einen randomisierten Algorithmus für 2SAT gemacht? => Random Walk für 2SAT erklären. Markov Kette hinmalen. | ||
+ | * Was genau sind die Zustände hj? => Anzahl Schritte bis zum Endzustand. | ||
+ | * 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, | ||
+ | |||
+ | DP: | ||
+ | * Manche NP vollständigen Probleme kann man besser machen als Holzhammer wie? => Dynamische Programmierung. | ||
+ | * Definieren Sie TSP. | ||
+ | * Wie geht das mit DP? | ||
+ | * Wie nennt man diese Gleichungen? | ||
+ | * Wie ist die Laufzeit? | ||
+ | |||
+ | Ich habe ziemlich schnell geantwortet und bei einigen Fragen deshalb auch etwas ungenau bzw. falsch geantwortet, | ||