FSI-Zimmer: geschlossen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 8 » OntoSWeb WS14/15 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| — | pruefungen:hauptstudium:ls8:ontosweb_ws14 [13.03.2015 16:09] (aktuell) – angelegt rootzlevel | ||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| + | ==== OntoSWeb WS14/15 ==== | ||
| + | |||
| + | Prüfer: Lutz Schröder, Daniel Hausmann | ||
| + | |||
| + | == FOL == | ||
| + | |||
| + | * Welche Logiken haben wir betrachtet? | ||
| + | * Wie ist die Komplexität von FOL? | ||
| + | * Unentscheidbar; | ||
| + | * Warum ist Gültigkeit r.e.? | ||
| + | * Beweise aufzählen? | ||
| + | * Welche Eigenschaft ist dafür notwendig? | ||
| + | * Vollständigkeit von Beweiskalkül | ||
| + | * Was passiert mit Erfüllbarkeit bei endlichen Modellen? | ||
| + | * r.e. | ||
| + | * Cool, dann ist FOL auf endlichen Modellen entscheidbar, | ||
| + | * Nein, Gültigkeit nicht mehr r.e. | ||
| + | * Gibt's eine Formel, die nur in unendlichen Modellen erfüllbar ist? | ||
| + | * Ja, man muss so ein paar Eigenschaften fordern, wie irreflexibilität, | ||
| + | * Und eine, die nur in endlichen? | ||
| + | * ¬ von der vorherigen | ||
| + | * Was haben wir gemacht um die Ausdrucksstärke zu analysieren? | ||
| + | * FO-Derfinierbarkeit | ||
| + | * Wie zeigt man sowas? | ||
| + | * Ehrenfeucht-Fraïssé-Spiele. Erklären. | ||
| + | * E-F-S => ≃m | ||
| + | * Dann kam Nachfrage nach Umkehrung | ||
| + | * Antwort: Mit endlichem Σ | ||
| + | * Welche Klassen haben wir beispielsweise so angeschaut? | ||
| + | * ORD und EVEN | ||
| + | | ||
| + | == ALC == | ||
| + | |||
| + | * Bisimulation? | ||
| + | * Bisimilare Zustände erfüllen die selben Modalformeln. | ||
| + | * Welche Umkehrungen gibt es und gelten die? | ||
| + | * Zustände, die die gleichen Modalformeln erfüllen, sind bisimilar. | ||
| + | * Nur in endlich verzweigten Modellen (Hennessy/ | ||
| + | * Beispiel für unendiche Modelle, wo es nicht gilt? | ||
| + | * Das Beispiel aus dem Skript | ||
| + | * Algo für Erfüllbarkeit? | ||
| + | * Tableaux. Erklären, ¬□-Regel hinzeichnen | ||
| + | * Welche Platzschranke und warum? | ||
| + | * PSPACE. Stacktiefe * Stackframe | ||
| + | * Geht's besser? | ||
| + | * Nein, PSPACE-hart | ||
| + | * Wie zeigt man das? | ||
| + | * Reduktion | ||
| + | * Welche Reduktionen haben wir für PSPACE-härte gemacht? | ||
| + | * TQBF (Quantorenbaum) -> Modalformel | ||
| + | * Wie ging das ungefähr? | ||
| + | * Formel bauen, so dass Quantorenbaum Modell und man aus Modellen für die Formel Quantorenbäume extrahieren kann. | ||
| + | |||
| + | == EL == | ||
| + | |||
| + | * Welche Komplexität? | ||
| + | * PTIME | ||
| + | * Algo? | ||
| + | * Materialisator. erklären, wie und warum. | ||
| + | * Simulationsstabilität? | ||
| + | * erklären | ||
| + | * Modalformel, | ||
| + | * □⊥ | ||