大学のドイツ語③ フライブルク大学情報工学部「AI基礎」試験問題

フライブルク大学は先週の金曜日から春休みとなりました。

春休みというと聞こえがいいですが、理系の学部に限り、休講期間＝試験期間となりますから、むしろこれからが本番です。

昨日はさっそく3年生の講義「Grundlagen der Künstlichen Intelligenz」の試験がありました。せっかくなのでここで実際の試験の流れと問題を紹介したいと思います。一緒に解いてみましょう。

試験の流れ

試験は、開始時刻の15分前までには必ず会場にいるように、と言われますが、（特に情報工学部は）絶対に時間通りには始まりませんから万が一遅刻しても慌てないことです。試験当日に百数十人分の問題を印刷してるというのですから無理はありません。そういうところはいかにもドイツらしいですよね。

さて会場に入ると問題文は既に机の上に用意されています。席は自由ですが、この問題文が置かれている場所以外に座ることはできません。

自分の席に持って行ってもいい物は

• 飲み物／食べ物（長いと4時間という試験もあります。日本からすると考えられないですが、腹が減っては戦はできないので、試験中にムシャムシャは至って普通の行為です！）
• 学生証と顔写真付き身分証（保険証など）
• 青か黒のペン（鉛筆と赤いペンは採点されないので絶対NGです。中が見える物に限り、ペンケースも持ち込みOKです）
• ティッシュ、ハンカチ、寒ければ上着など（試験に関係のある文字や計算などが一切書かれていない物）

上記以外の物は全て、入ってすぐの黒板の下に置きます。

全員が席についたら、表紙に名前と学籍番号を書く時間があります。教授によっては注意事項を全て読み上げる場合もあります。

この時点で体調が悪い場合、まだ名乗り出てその足で医者へ行き、診断証明を発行してもらうことができます！

今回のGrundlagen der Künstlichen Intelligenzの試験は90分で8問（計算が多いのでかなり急ぎ足で解かなければいけません）。満点が90点なので、50％の45点以上とれれば合格です。

それでは実際にはどんな問題が出たのか、覚えている範囲で類題を集めたので見てみましょう！

第一問　Uniform Search／Greedy Best Search／A*

Zeichnen Sie den Suchbaum, der von den Uniform Search, Greedy Best Search und A*-Algorithmus für die Suche eines kürzesten Weges von Knoten A zu Knoten D erzeugt wird. Verwenden Sie hierzu den heuristischen Abstand zu Knoten D welcher in der Tablle angegeben ist. Geben Sie an, in welcher Reihenfolge die Knoten expandiert werden, und annotieren Sie jeden Knoten mit seinen f-, g-, und h-Werten. 

        

この問題ではUniformSearchがg(n)つまりPath Cost、GreedyBestSearchがh(n)、A*がg(n) + h(n)で計算されるコストのうち最小値を選ぶことでAからDへのそれぞれの正しい道順を進むことができます。それぞれの探索アルゴリズムを正しく使えているかどうかが採点ポイントです。とても簡単な問題なのに急いでいる時は数を見間違えることがあるので、よく見直して確実に点を取りたいところです。

第二問　α‐β Pruning

Betrachten Sie den folgenden Spielbaum für ein 2-Personen-Spiel mit Zufallsknoten.

Simulieren Sie das Verhalten des Minimax Algorithmus mit α‐β Pruning und bestimmen Sie die Bewertungen der Knoten des Spielbaumes. 

     

α‐βアルゴリズムを使ってWurzel Knoten（根ノード）の値を求める問題です。教授によって計算途中どのKnotenになんの値が参照されているかまで書くように求める場合もあります。

第三問　DPLL

Verwenden Sie die Davis-Putnam-Logemann-Loveland(DPLL)-Prozedur, um eine
erfüllende Belegung der Formel Φ zu finden. Schreiben Sie alle Schritte, die der Algorithmus währenddessen ausführt, auf. Wenn Sie eine Verzweigungs-Regel anwenden müssen, wählen Sie die Verzweigungs-Variablen in alphabetischer Reihenfolge aus, und wählen Sie zuerst wahr, dann falsch. Geben Sie die erfüllende Belegung an.

DPLLのルール（Splitting, Unit Propagation, Backtracking）を使ってΦが満たされるA,B,C,D,E,Fの値（True/False）があるかどうかを確かめます。多くの場合はアルファベット順、True→Falseの順でルールを適用するように書いてあります。

上の場合はまずSplittingルールよりA→Trueを入れてみて、残りの (B,C), (￢E),(￢B,C,D,E),(￢C,￢D),(F)を満たす値があるかどうか順番に見ていきます。この場合、F→True, B→True, C→True, D→False, E→False と決まっていきます。上手くいかない場合は直前のSplittingルールへBacktrackingします。

試験で使用されるフォームはとにかく横に長いので最初に見落としがあると全部くるってしまいます。それなのに配点が10点以上とだいたい恐ろしく高く設定されています。これを落とすと痛いので念入りに練習しておきたい問題です。

第四問　Logik

Betrachten Sie folgenden STRIPS-Task II. Geben Sie für die folgenden Formeln θ an, ob I unter α = {(x, 0), (y, 1)} ein Modell für θ ist, d.h. ob I,α |= θ. Begründen Sie Ihre Antwort durch eine formale Anwendung der Semantik.

Logikは他の問題と違って、やり方が分かっていなくてもよく見れば解けるサービス問題だと私は思っています。今回まさかこれが出てくれるとは！

a) ～ e) のAussageが上の箇条書きのルールに沿っているかどうかを見極めるだけです。例えば a) ではoddにyが含まれていて、かつ、evenにtwoが含まれているのでルールに従っていると言えます。という具合で他のシータも確認します。

ちなみにθはドイツ語ではテータです。シータというと通じないので注意です！

第五問　CSP

Betrachten Sie das 6-Damen Problem, bei dem 6 Spielfiguren auf einem 6 × 6 Felder großen Brett so platziert werden sollen, dass sich keine zwei Damen auf der selben horizontalen, vertikalen oder diagonalen Line befinden.

Betrachten Sie nun den Zustand α = {v1 → 2, v2 → 5}.

a) Erzeugen Sie Kantenkonsistenz in α.

b) Führen Sie Forward-Checking in α aus. Vergleichen Sie das Ergebnis mit a).

                         

FCとAC3をそれぞれ6クイーン問題に使ってみてその違いを確かめる問題です。n-クイーン問題とはn×nのゲーム盤にn個のクイーンを縦横斜めのマスに2つ以上が被らないように置いていくゲームです。

やってるうちにこんがらがってしまいがちですが、FCもAC3もどれかの変数に値が代入される度に他の変数にとってルール違反になる数字を消していきます。

その中で、FCの場合、ルール違反かどうかは今値を代入された変数とそれ以外の変数とをペアにして比較します。なので、他の変数との組み合わせではルール違反になってしまいかねない値もそのペアが判定されるまで残ってしまいます。

AC3は一度に一つの変数しかアクセスできませんが、アクセスされている変数はそれまでの他の全ての変数への変更を加味した上で自分にとってのルール違反である値を判断することができます。

試験では多くの場合、探索の全過程ではなく最初の3ステップを書きなさいと言われます。そこでちゃんと二つのアルゴリズムの違いを理解できているかが見られます。

第六問　Entscheidungsbaum

Wir betrachten das Attribut Genre als Kandidaten für den ersten Knoten eines Entscheidungsbaums der klassifizieren soll, ob eine Vorstellung ausverkauft war oder nicht. Um wieviel würde das Attribut die Unsicherheit der Klassifikation reduzieren? Rechtfertigen Sie Ihre Antwort mit detaillierten Berechnungen. 

  

判断木を書くために必要なのはなるべく小さくコンパクトにすることです。つまりKandidat以外の3つの項目（Alter, Einkommen, Bildung）のどれをWurzelとして選ぶかどうかが大事な判断になります。それを決めるために計算するのがInformation Gainです。なのでこの問題は公式をちゃんと覚えていないと解けません。

試験で使用する表はもう少し情報量が多くなるので見間違いにも注意したいです。 

最後に

試験問題は全て回収されるので持ち帰ることはできません。

試験が終わってから採点までには早くて3日、長くて2ヵ月かかります。試験後には必ず 点数見直し日が設けられていて、そこへ行けば採点の不備を確認できます。落ちてしまった場合も、再試で同様の問題が出る可能性があるため、出題された問題を見に行く価値はあります。ただし、その場で写真を撮ったりメモを取ることはできませんから、問題を覚えて、部屋を出てすぐにメモをするしかないです。

ちなみに情報工学部の追試は半年後の試験期間になります。

試験期間は始まったばかり、残り2ヵ月頑張りましょう！！