基礎情報処理(H.20)最終レポート

情報の授業ページに、最終レポート課題が掲載されています。

情けないことに、このページいつから存在していたのかよく分かりません。手元にはあるもののサーバ上になかったのでとりあえずアップしましたが、ただの作りかけ文書の可能性もあるので、そのつもりで読んでください。

はじめに

出題されたレポート問題は例年通りの傾向・レベルの問題だと言えます。つまり、基本的・教科書的な問題なのですが、それだけに基本部分が理解できないと全く解けないでしょう。ところがこの分野、慣れていない人にとっては今までにない馴染まない考え方をする学問なので、その基礎で躓く人が結構多いのです。その意味では難しい問題に違いありません。

一応解説はするのですが、基礎的なこと、本当に簡単な解説しかしません。と言うか、それ以上行くともう答えその物になってしまうので、簡易解説しかできないという方が正しいです。

大問１

関数flipの定義

与えられたSchemeプログラムによる関数flipの定義を、数学的な記法で書き直せば次のようになります。 

wが原子ならば
　　flip(w) := w
それ以外のときは
　　flip(w) := cons(flip(cdr(w)), flip(car(w)))

define, cond, car, cdr などのSchemeの基本は自分で確認しておいてください。

なお、atom?関数はSchemeでは使えないので、自分で予め定義しておく必要があります。

大問２

記号

  • ∧ (AND)
  • ∨ (OR)
  • ¬ (NOT)

基本法則

交換法則
Ａ∨Ｂ＝Ｂ∨Ａ
Ａ∧Ｂ＝Ｂ∧Ａ
分配法則
(Ａ∨Ｂ)∧Ｃ＝(Ａ∧Ｃ)∨(Ｂ∧Ｃ)
(Ａ∧Ｂ)∨Ｃ＝(Ａ∨Ｃ)∧(Ｂ∨Ｃ)
ド・モアブルの法則
¬(Ａ∧Ｂ)＝(¬Ａ)∨(¬Ｂ)
¬(Ａ∨Ｂ)＝(¬Ａ)∧(¬Ｂ)

方針

慣れない式変形で戸惑うかもしれませんが、上で示したように通常の＋や×と同様に交換則・分配則が成り立つので、同じように計算するだけです。＋や×の計算式を簡単にするとき、普通どのような手順で計算をしますか？

ミスをしないために

既に何人かから質問を受けたり添削っぽいことをしたりしましたが、やはりかなり基本的な部分での勘違いや理解不足による誤りが多いようです。

そのため、解けたと思って慢心せずに、必ず検算するようにしてください。具体的には、大問１ならばSchemeで実際にプログラムを組んで検証して、大問２ならば2^5=32通り全ての組み合わせで真偽値を代入して検算するのが確実です。