読者です 読者をやめる 読者になる 読者になる

mrasu’s blog

読んだ物の内容など

「入門 コンピュータ科学」 10章 - 最終章

「入門 コンピュータ科学」の10章から12章(最終章)までです。
CG, AI, 計算理論について

入門 コンピュータ科学 ITを支える技術と理論の基礎知識

入門 コンピュータ科学 ITを支える技術と理論の基礎知識


10章 コンピュータグラフィックス

10.1 コンピュータグラフィックスの範囲

2Dと3D

1.2 3Dグラフィックスの概要

投射投影と平行投影

10.3 モデリング

  1. 平面パッチ: 多角形で切り出す
  2. ベジェ曲線: 終端2点と曲線を決める2点を使用して決まる曲線
  3. 手続きモデル: 複雑で手や幾何学的に表せないものは、自動的に形状を描き出すようにする

テクスチャマッピング

10.4 レンダリング

光の反射は鏡面光が有名だが、実際には大部分が拡散光や環境光がある
透明な場合には、屈折も考える

視体積に含まれない部分木を排除→ラスタライズ→隠面消去

シェーディング

10.5 グローバルライティングの処理

  1. レイトレーシング
  2. ラジオシティ

10.6 アニメーション

11章 人工知能

11.1 知能とマシン

エージェントは環境からの刺激に反応する必要がある。

  1. 反射動作(入力データから事前の取り組みを実行する)
  2. 現在の環境を理解して動作する
  3. 目標のために最適に動く

人工知能

  1. 実践(開発目的、工学指向)
  2. 理論(理解目的、理論指向)

チューリングテストは、知性が無くとも、それらしきものを作る事が出来てしまったから。(心理療法における対話など)

11.2 認識

画像理解の方法

  1. テンプレートに照合する
  2. 幾何学的特徴と照合する

画像理解のステップ

  1. 画像処理 (エッジ強調、領域発見、平滑化)
  2. 画像分析

言語処理

  • 文の理解
    1. 構文解析
    2. 意味解析
    3. 文脈解析
  • 文書の理解
    1. 情報検索
    2. 情報抽出

11.3 推論

推論に必要なプロダクションシステム

  1. 状態
  2. プロダクション (状態を遷移するための操作)
  3. 制御システム (目標を達成するための適用するプロダクションの決定)

推論戦略
0. 探索木
0. ヒューリスティック

11.4 その他の研究領域

  1. 知識の表現と操作: 文脈理解、回答表現の適格性、閉世界仮説
  2. 学習: 模倣、教師あり学習、強化学習
  3. 遺伝的アルゴリズム

11.5 人口ニューラルネットワーク

12章 計算の理論

12.1 関数とその計算

入力値に基づいて出力を決定できない関数が存在する。
それを計算不能と呼び、できるものは計算可能という

12.2 チューリングマシン

チャーチ・チューリングの提唱

チューリング計算可能な関数は計算可能な関数と等しい。  
チューリングマシンの計算能力は、いかなるアルゴリズムシステムをも内包する。  
あるいは、チューリングマシンの概念は全ての計算可能な関数を表現する解法を与える文脈を提供する  

12.3 万能プログラミング言語

万能プログラミング言語の作成

  1. clear
  2. incr
  3. decr
  4. while-end

以上

例えば、 X * Yは、

clear Z;  
while X not 0 do;  
    clear W;  
    while Y not 0 do;  
        incr Z;  
        incr W;  
        decr Y;  
    end;  
      
    while W not 0 do;  
        incr Y;  
        decr W;  
    end;  
      
    decr X;  
end;  

12.4 計算不能関数

停止問題 (プログラムが停止するか)を解くことはできない。

「出力Xが1であれば停止する。0なら、停止しない」としたとき

while X not 0 do;  
end;  

というプログラムには、どうしようもない。反例は示された。

12.5 問題の複雑さ

計算量とNP問題、NP完全問題

12.6 公開鍵暗号

任意のkについて、p,qが素数で、0<m<p*q とすると
1 = m^(k(p-1)(q-1))
が成立することを基に、

e*d = k(p-1)(q-1) + 1
となる値を考える

(e,n)が暗号化鍵, (d,n)が複合鍵, 平文をm, 暗号文をcとする

暗号化式: c=m^e(mod n)
複合化式: c^d(mod n)

c^d(mod n) = m^(e*d) (mod n)
= m^(k(p-1)(q-1) + 1) (mod n)
= m * m^(k(p-1)(q-1)) (mod n)
= m (mod n)
= m

となり、mを複合できた


以上が「入門 コンピュータ科学」。appendix部分は省きます