Prüfungsfragen (ab WS 2005) zur Vorlesung Einführung in die Artificial Intelligence

Einführung und Geschichte der AI

• Durch welches Resultat wurde Hilberts Programm zunichte gemacht?
• Nennen Sie mindestens drei Wurzeln der Arificial Intelligence.
• Beschreiben Sie die Funktion des Turing-Tests.
• Wie hiess das in Dartmouth vorgestellte erste AI-Programm und was machte es?
• Wo fand die erste IJCAI Konferenz statt? Was wurde dort u.a. vorgestellt?
• Wie hiess das erste Expertensystem und was war seine Aufgabe?
• Wo findet man heutzutage im Alltag Anwendungen der AI?
• Für was sind McCulloch und Pitts bekannt?

Wissensrepräsentation

•    Nennen Sie die drei Ebenen eines Wissensbasierten Systems

•    Vor- und Nachteile der prozeduralen Wissensrepräsentation.

•    Wie ist der Ablauf in einem Regelinterpreter?

•    Was ist eine Beschreibungslogik (description logic)?

•    Was wird mit Skripten beschrieben?

•    Was bedeutet "die klassische Logik ist monoton"?

Komplexität (Informatische Lösungsmethoden schwerer Probleme)

• Was bedeutet P, NP bzw. NP-vollständig? (Kurze Beschreibung)
• Nennen Sie zwei NP-vollständige Probleme.
• Nennen Sie drei Lösungsansätze für NP-vollständige Probleme.
• Beschreiben Sie kurz das Verfahren der Randomisierten Suche.
• Beschreiben Sie kurz das Verfahren der NP-Approximation.
• Wodurch ist NP-Härte bei Graphenproblemen oft bedingt?
• Nennen Sie eine polynomielle Subklasse für das Dreifärbbarkeitsproblem.

Konfiguration

• Was ist eine key component?
• Erläutern Sie die strukturbasierte Konfiguration.
• Beschreiben Sie Horizont- und Schwelleneffekte.
• Was ist Partial Commitment?
• Was ist Propose-Revise?
• Erläutern Sie den Unterschied in der Vorgehensweise zwischen regelbasierter und modellbasierter Konfiguration.
• Welche Unterschiede ergibt sich zwischen constraintbasierter und regelbasierter Konfiguration bei der Beschreibung der Wissensbasis?
• Geben Sie die Vorteile des constraintbasierten Konfigurationsansatzes gegenüber dem regelbasierten an.

Diagnose

• Was versteht man unter Diagnose? Was ist die Idee der Modellbasierten Diagnose?
• Warum heißt die Modellbasierte Diagnose auch "Diagnosis from First Principles"?
• Welche Verfahren zur Diagnose gibt es? Was sind die Nachteile? Was sind die Vorteile?
• Definieren Sie Diagnosesystem, Diagnoseproblem, und Diagnosen.
• Zählen Sie die Vor- und Nachteile der Modellbasierten Diagnose auf.
• Was ist der Unterschied zwischen Quantitativen Modellen und Qualitativen Modellen.
• Was sind Fehlermodelle? Wozu werden sie benötigt?

Constraint Satisfaction Systeme

• Aus welchen Komponenten besteht ein CSP? Wie lassen sich diese darstellen?
• Geben Sie ein praktisches Beispiel (nicht aus der Vorlesung und nicht das Kino-Beispiel ) für ein CSP an. Welcher Aspekt des Beispiels entspricht welcher Komponente des CSP?

• Beschreiben Sie chronologisches Backtracking. Wodurch kann man die Effizienz des Verfahrens beeinflussen?

• Was ist der Unterschied von Backjumping und Conflict-Directed Backjumping?

• Nennen Sie zwei unterschiedliche Darstellungsarten von Constraints.

• Wie lassen sich unterschiedliche Lösungsverfahren fuer CSPs vergleichen?

• Welche Vorteile hat es, ein gegebenes Problem als CSP zu lösen?

Wissensbasierte Suche

•    Warum braucht man in der künstlichen Intelligenz im  Speziellen effiziente Suchverfahren?

•    Was ist der Unterschied zwischen einer informierten und  einer uninformierten Suchstrategie?

•    Was ist der Vorteil einer Suche mit iterativer Vertiefung?

•    Was versteht man unter einer heuristischen Suche?

•    Aus welchen beiden Komponenten setzt sich die  Schätzfunktion eines A* Algorithmus zusammen?

•    Welchen Vorteil besitzt der IDA* Algorithmus gegenüber dem  A* Algorithmus?

•    Was versteht man unter ”alpha/beta pruning”?

Wissensbasiertes Planen

•    Aus welchen Teilen besteht die Beschreibung eines  Planungsproblems?

•    Aus welchen Teilen besteht ein Planungsoperator?

•    Was versteht man unter dem Situationskalkül?

•    Was ist der Unterschied zwischen einer Eintrittsbedingung  und einer Einschränkung bei einem Planungsoperator?

•    Spezifizieren Sie einen Planungsoperator, der beschreibt, wie ein Besucher in ein Kino geht!

•    Was ist eine nicht-lineare Planung?

•    Was wird bei einer Situationsabstraktion gemacht?

Maschinelles Lernen

• Schreiben Sie einen abduktiven Syllogismus auf.
• Welche Arten maschinellen Lernen gibt es?
• Was ist der Unterschied zwischen Unsupervised und Supervised Learning?
• Beschreiben Sie den ID3 Algorithmus.
• Geben Sie ein Beispiel für den ID3 Algorithmus an.
• Was ist Clustering?
• Beschreiben Sie ein Beispiel für Reinforcement-Learning.

Moderne Heuristiken

• Was sind Heuristiken und warum werden sie verwendet?
• Was ist der Unterschied zwischen Simulated Annealing und Stochastic Hill-Climbing
• Was sind die wichtigen Fragen bei Simulated Annealing?
• Welche Lokalen Suchmethoden sind deterministisch?
• Was ist eine Tabu Liste? Warum wird sie verwendet?
• Welche Operatoren werden bei Genetischen Algorithmen verwendet? Was tun Sie?
• Geben Sie ein Beispiel für einen Kreuzung-Operator an.

Unsicheres Schliessen

• Nennen Sie zwei verschiedene Arten von Unsicherheit und geben Sie Beispiele an.
• Was besagt die und wann gilt für Ereignisse die Additionsregel in der Wahrscheinlichkeitstheorie?
• Drei Todeskandidaten warten auf ihre Hinrichtung. Allerdings ist bekannt, dass einer der drei begnadigt werden soll. Der Kandidat 1 frägt den Gefängniswärter: "Hör mal, kannst Du mir verraten, wer von den beiden anderen dran glauben muss? Einer ist auf jeden Fall an der Reihe, also verrätst Du mir kein großes Geheimnis." Der Wärter überlegt und sagt "Irgendwie hast Du recht. Also, Kandidat 2 ist fällig." Jetzt ist der erste Todeskandidat erleichtert, denn er denkt: "Bleiben zwei übrig, einer davon überlebt, also ist meine Überlebenswahrscheinlichkeit von 1/3 auf 1/2 gestiegen." Was sind die tatsächlichen Überlebenswahrscheinlichkeiten der drei Kandidaten wenn sonst nichts bekannt ist?
• Wie lautet die Bayes'sche Inferenzregel?
• Der HIV-Test liefert mit hoher Wahrscheinlichkeit die richtige Antwort (die "Sensitivität" des Tests, d.h. die Wahrscheinlichkeit, dass das Testergebnis positiv ist wenn die Testperson infiziert ist, ist 0.998; die "Spezifität"' des Tests, d.h. die Wahrscheinlichkeit, dass das Testergebnis negativ ist wenn die Testperson nicht infiziert ist, ist 0.99). Die von Experten am häufigsten genannte Zahlen für Westeuropa besagen, dass rund ein Promille der sexuell aktiven Bevölkerung infiziert sind. Wäre es dann sinnvoll, einen Zwangs-HIV-Test für alle in Österreich lebenden Erwachsenen einzuführen? Nehmen wir an, ein zufällig ausgewählter Erwachsener testet positiv. Wie gross ist dann die Wahrscheinlichkeit, dass er oder sie trotzdem nicht mit HIV infiziert ist (schreiben Sie auch die verwendete Formel auf; falls kein Taschenrechner zur Hand, so schätzen Sie die Größenordnung des Ergebnisses ab)?
• Entwerfen Sie eine kleine Fuzzy-Regelbasis (ohne Angabe der Fuzzy Mengen; nur die linguistischen Regeln sind gefragt) für die Auftau-Automatik eines Mikrowellen-Herdes. Nehmen Sie dabei an, dass geeignete Sensoren zur Verfügung stehen.

Intelligente Agentensysteme

• Nennen Sie die zwei Teilgebiete und zwei großen Fragestellungen der DAI!
• Auf welchen drei Beschreibungsebenen kann ein wissensbasierter Agent beschrieben werden?
• Geben Sie drei Techniken an die in der Distributed AI verwendet werden.
• Nennen Sie drei Eigenschaften, die ein Agent aufweisen sollte um sich von einem "gewöhnlichen" Programm abzuheben!
• Beschreiben Sie den Unterschied zwischen reaktiven und deliberativen Agenten.
• Erläutern Sie den Unterschied zwischen remote procedure calling und remote programming anhand eines kurzen Beispiels!
• Wie sieht das Schichtenlayer von KQML aus? Welche Gestalt hat ein KIF Satz?

Informationsagenten im Internet

• Erläutern Sie folgende Begriffe: SGML, XML, HTML. Worin unterscheidet sich HTML von XML?
• Welche Abfrage- und Transformationssprachen für XML kennen Sie? Führen Sie drei an.
• Welche der im Vortrag erwähnten Sprachen eignen sich zur Beschreibung nichtmobiler Agenten? Welche davon sind Skriptsprachen?
• Skizzieren Sie das Agency-Intelligence-Mobility-Diagramm und erläutern Sie kurz wo das MindIt-Tool darin anzusiedeln ist, bzw. der ContinualQuery Agent.
• Schreiben Sie drei der genannten Eigenschaften/Vorteile von Java auf.
• Schreiben Sie eine XML Darstellung eines Bucheintrages die zu folgendem DTD Fragment konform ist:
• <!ELEMENT book (author+, title, price)>
• <!ELEMENT title (#PCDATA)>
• <!ELEMENT author (#PCDATA | lastname | firstname | fullname)*>
• <!ELEMENT price (#PCDATA)>
• <!ATTLIST price currency CDATA "USD" source (list|regular|sale) list taxed CDATA #FIXED "yes">

• Erläutern Sie die Begriffe Wrapper und Mediator.

Neuronale Netze

• Welches Lernmethode gab der stagnierenden Forschung im Bereich der kNN ab 1986 neuen Schwung?
• Aus welchen 3 Funktionen besteht ein künstliches Neuron? Nennen Sie auch die korrespondierenden 3 Bestandteile eines biologischen Neurons.
• Aus welchen 3 Schichen (Layern) sind kNNs normalerweise aufgebaut?
• Nennen Sie mind. 2 verschiedene Arten von Aktivierungsfunktionen.
• Beschreiben Sie kurz die wesentlichen Unterschiede zwischen Feedforward-Netzen und Recurrent-Netzen.
• Neben der Veränderung der Gewichte, welche prinzipiell möglichen Lernprozesse in kNN sind Ihnen noch bekannt? Nennen Sie mind. drei.
• Beschreiben Sie kurz (2 Sätze) die prinzipielle Funktionsweise des Backpropagation Algorithmus (Formeln sind nicht notwendig).

Last changed: 03. Oktober 2005 by Nysret Musliu