アルゴリズムと数式の表現 コンピュータの推論

Presentation on theme: "アルゴリズムと数式の表現 コンピュータの推論"— Presentation transcript:

1 アルゴリズムと数式の表現 コンピュータの推論
授業展開＃１０ アルゴリズムと数式の表現 コンピュータの推論

2 数式の性質と解釈 四則演算 　例　12 + ( ) x 78 　・加算と乗算の結果は項の順序に依らない（可換律）。減算、除算は可換ではない。 　・２つ以上の演算を含む場合の演算順序は括弧を使って表す。 　・乗算と除算は、加算と減算に優先する。 　・三つの項の加算と乗算には結合律が成立する。　 　　１２３+（32+56）＝（123+32）+56

3 数式の性質と解釈 四則演算（続き） ・減算と除算では結合律は成立しない。 68-（18-32）は、（68-18）-32と等しくない。
　・減算と除算では結合律は成立しない。 　　68-（18-32）は、（68-18）-32と等しくない。 　・同じ優先順位の演算は左から順に評価する（数式の解釈規則）。 　　 は、（68-18）-32　を意味する。

4 数式の定義 四則演算は、2項演算。 項とは、○－○という場合の○の部分。 数式の定義 １．最も簡単な数式は、１つの数値からなる。
２．数式を項とする２項演算式も数式である。 　○、□を数式とすると、○＋□、 ○ー□、 ○×□、 ○÷□も数式。 ３．このような構造をもつものは、全て数式であり、任意の数式はこのような構成をもつ。

5 数式の構文木（こうぶんぎ） 数式の構造（演算の順序）を階層的に図示したもの 12+(34+56)×78＋９×１０の構文木は、 ＋ ＋ ×
9 10 ＋ 34 56 34 ＋ 56 = ＋ 78 34 56

6 括弧のいらない数式表現法 前置記法：演算記号を前に書く記法（ポーランド法） ２項演算を表すのに、たとえば、３３＋６２を
　２項演算を表すのに、たとえば、３３＋６２を 　＋　３３　６２　と書く記法 12+(34+56)×78＋９×１０は前置記法では 　（＋ （＋ １２ （×（＋ ３４ ５６） ７８）） （×9 10）） であり、すべての括弧を除くと、 　　＋ ＋ １２ × ＋ ３４ ５６ ７８ × 9 10　となる。 この数式は計算できる部分から順に計算を進めていけば、元の数式と同じ順序で計算される。 コンピュータで容易に扱うことができる表現。

7 ＋ ＋ １２ × ＋ ３４ ５６ ７８ × 9 10　 ＋ ＋ １２ × 90 ７８ × 9 10　 ＋ ＋ １２ 7020 × 9 10　 ＋ 7032 × 9 10　 ＋ 　 7122

8 後置記法：演算記号を後に書く記法（逆ポーランド法）
　２項演算を表すのに、たとえば、３３＋６２を 　３３　６２　＋　と書く記法 12+(34+56)×78＋９×１０は後置記法では 　（（１２ （（３４ ５６ ＋） ７８ ×） ＋ ）（9 10×）＋）であり、 　すべての括弧を除くと、 　　１２ ３４ ５６ ＋ ７８ × ＋ 9 10 × ＋　となる。 前置記法と同様、計算できる部分から順に計算を進めていけば、元の数式と同じ順序で計算される。 コンピュータでは、基本的な数式表現は後置記法。

9 １２ ３４ ５６ ＋ ７８ × ＋ 9 10 × ＋ 　 １２ 90 ７８ × ＋ 9 10 × ＋ １２ 7020 ＋ 9 10 × ＋　 × ＋ ＋　 7122

10 数式を計算するアルゴリズム 12+(34+56)×78を計算するアルゴリズムを考える。 加算と乗算の基本演算を次の基本操作として表す。
　加算　AとBを加えてCとする。 　乗算　AとBを掛けてCとする。 上の数式の計算アルゴリズムは次のようになる。 　①　３４と５６を加えてｐとする。 　②　ｐと７８を掛けてｑとする。 　③　１２とｑを加えてｒとする。

11 計算アルゴリズムと後置記法数式 12+(34+56)×78の後置記法数式は、 12 34 56 ＋ 78 × ＋
　 ＋ 78 × ＋ この後置記法数式を左から見ていったとき、最初に計算できる部分は、 　　 ＋ この結果をｐとすると、次に計算できるのは、 　　 ｐ　78 × この結果をｑとすると、次は、 　　12 ｑ ＋ 　この計算手順は、計算アルゴリズムと完全に対応している。

12 １２ ３４ ５６ ＋ ７８ × ＋ 　 １２ 　　　　　　　３４ ５６ ＋ ７８ × ＋ 　 １２ ３４ ５６ ＋ ７８ × ＋ 　 １２ ３４ ５６ ＋ ７８ × ＋ 　 １２ ７８ × ＋ 　 １２ 90 ７８ × ＋ 　 １２ ＋ 　 　

13 占星術と血液型性格判断 客観的に証明できない。判断の方法に問題がある。科学的根拠が無い。
占星術：天球上の星の配置に基づく判断基準（規則）と、生まれたときの星の配置（事実）を前提に運勢や性格などの結論を導く。 血液型性格判断：血液型から決まる性格（規則）と血液型（事実）より、その人の性格（結論）を導く。

14 推論と推論のアルゴリズム 推論：いくつかの前提から結論を導くこと。
コンピュータの推論の方法は、前提である入力文字列を結論の出力文字列に変換するアルゴリズムである。 　　　　　コンピュータは推論機械

15 推論の一般化と推論形式 推論の枠組みの形式化。推論のアルゴリズム 占星術による占いの一例
　　・金星が知性・才能室にある時に生まれた人は、美や教養を求める。（判断基準） 　　・A氏の誕生時のホロスコープによれば、金星が知性・才能室にあった。（データ） 　　・A氏は、雑誌の編集やルポライターの適正がある。（判断結果）

16 正しい推論形式 ある推論が正しいというためには、前提が正しいことが主張できないとダメであり、推論形式が正しいことが必要である。 推論形式
　　前提１　『　P　』　ならば、『　Q　』である。 　　前提２　『　P　』　である。 　　結論　　よって、 『　Q　』である。 　　　　　P、Q　データや命題が入る。 　　　　　命題：真偽の判断ができる言明を述べた文章 2つの前提が正しければ、結論も常に正しい。 この推論形式をモダスポネンスと呼ぶ

17 推論形式 正しい推論形式 前提１ 勉強をしていれば、この試験は合格するはずだ。 前提２ Cさんは頑張って勉強したから、
　正しい推論形式 　　前提１　勉強をしていれば、この試験は合格するはずだ。 　　前提２　Cさんは頑張って勉強したから、 　　結論　　Cさんは合格したと思う。 正しくない推論形式 　　前提１　長いスピーチは退屈であるが、 　　前提２　Dさんのスピーチは短かったから、 　　結論　　Dさんのスピーチは退屈でなかった。 　　２つの前提が正しいとしても、短いスピーチが退屈でないとは限らないからこの結論は必ずしも正しくない。

18 命題の評価とあいまいな命題 推論形式が正しいかどうか判定するためには、個々の推論の前提が正しいとした上で、その結論が正しいかどうかを見る。
また、推論形式が正しいとき、全ての前提が正しいことを示せば、結論の正当性は保証される。 ある命題が正しいかどうか判断することを命題の評価と呼ぶ。 命題の評価は、二律背反の命題か、あいまいな命題かといった命題の性格に依存する。 あいまいな命題を対象に論理を組み立てると誤った結論を導く

19 コンピュータの推論アルゴリズム コンピュータの処理を推論とみたとき、その命題としての性格は二律背反である。
二律背反の推論形式の代表的なものは三段論法と呼ばれているものである。 　　三段論法 　　前提１　P　ならば、Q　である。 　　前提２　Q　ならば、R　である。 　　結論　　よって、 P　ならば、R　である。 　　　P,Q,Rは任意の二律背反的命題を表す変数

20 コンピュータの推論 推論形式を解釈することは、P、Q、Rの変数に適当な命題を代入することである。
コンピュータによる「１ビットの加算」は、以下の推論形式である。 前提１　(X,Y)=(0,0) ならば、(S,C)=(0,0) である。（規則1） 前提２　(X,Y)=(0,1) ならば、(S,C)=(1,0) である。（規則2） 前提３　(X,Y)=(1,0) ならば、(S,C)=(1,0) である。（規則3） 前提４　(X,Y)=(1,1) ならば、(S,C)=(0,1) である。（規則4） 前提５　(X,Y)=(1,0) である。（データ） 結論　　(S,C)=(1,0) である。（結論）

21 推論形式の階層性 ある推論の結果を前提に加えて、次の推論を進めていくことで、多段の推論ができる。

22 あいまいな命題 確率的あいまいさ 　個々の事象については、二律背反的に正しいか明確であるが、集合全体でみると二律背反ではなく、ある割合で正しかったり、正しくなかったりすること。 ファジィ理論では、数学的に明確な性質をもったあいまいさとして定義され、扱うことができる。

23 あいまいな命題の評価 重要な３つの視点 １．命題が正しいかどうか判断するに足りる質を有していること。
「A薬品を投与するとB症は軽快する」という命題を正しく評価するためは・・・ ・薬剤を投与しなかった場合と比較する。 ・プラセボ効果（薬を飲んでいるというだけで本来薬効がないのに病気が軽快すること）を排除する。 ・期待効果（検査結果を判断する人が期待される方を有利に解釈してしまうこと）を排除する。

24 ２．正しいと判断する基準と正しくないと判断する基準を明確にすること。
・二律背反でない命題では、互いに矛盾しない基準がそれぞれに必要である。 ３．それらの基準と解釈によって「あと知恵」としないこと。 ・得られた結果にあうように基準を決めたりしてはならない。 これらの点について、占星術や血液型性格判断は多くの問題がある。

25 占いの推論アルゴリズム 前提１ A型であるならば、社会正義派で保守的である。 前提２ B氏はA型である。
前提２は正しいとしても、前提１は正しいとは限らない。 前提１を二律背反な命題と考えるならば、前提１は間違っているので、この推論はほとんど意味がないということになる。