情報学の基礎理論

  1. 代数系
  2. アルゴリズムとデータ構造
  3. 数値解析
  4. オペレーションズ・リサーチ
  5. 統計解析

　　情報学の基礎理論を構成する主要な科目の概要と他の科目との関係について述べます．他の科目との関係については，上に示してある図も参考にしてください．なお，上図において，点線の部分は，学科共通科目を表しています．ここにあげたすべての科目を理解しなければ，情報学における他の科目を理解できないというわけではありません．ほとんどの科目は数学系の科目です．どうしても数学だけは勉強したくないという人はやむを得ませんが，分野の内容を深く理解する上で大きな力になる科目が少なくありません．少なくとも，技術者として，研究者として，より高いレベルを目指そうとしたときには，必ず必要になると思います．

　　数学は，他の科目に比較して記憶すべきことは非常に少なく，万国共通の言語であり，その美しさは比類無きものであると思います．美しさ故に，現実の世界にそのまま適用できる場合は多くはありませんが，多くの学問分野の基本には必ず数学的な原理が横たわっています．数学を毛嫌いする人もいるようですが，是非，数学の面白さ，美しさを知ってもらいたいと思います．

  1. 代数系

    　　我々が通常行っている加減乗除の基礎となるのが「代数系」です．通常行っている演算体系は，代数系の立場から簡単に述べれば，実数の集合の上に加減乗除の演算を定義した体系であるといえます．一般に，どのような集合を選ぶか，又，そこにどのような演算を定義するかによってその系（代数系）の性質は異なってきます．特に，0 と 1 という 2 つの要素だけからなる集合の上に，加算（ OR 演算）と乗算（ AND 演算）などを定義した系はブール代数（ブール束）と呼ばれ，コンピュータ内で行われる 2 進数による演算の世界に対応します．従って，「計算機ハードウェア」や「計算機アーキテクチャ」などの科目と強い関係があります．

    　　また，ブール代数は，論理の世界と同じ構造を持っています．0 を「偽」，1 を「真」とみなせば，同じような構造であることが分かると思います．この論理の世界を扱うのが「論理数学」です．論理体系の一つである命題論理は「ソフトウェア」を作成する際にも重要であると共に，その発展形である述語論理と共に，「人工知能」における知識表現方法の一つとしても使用されています．勿論，数学的な論理体系だけでは，人間の知的行動の一部しか表現できませんが，例えば，命題論理を使用することによって，「 A ならば B である」，「 B ならば C である」という 2 つの事実から，「 A ならば C である」という事実を推論（三段論法）できる能力は，知的なコンピュータにとって必要不可欠なものです．

    　　さらに，「代数系」は，整数論と共に，「符号・暗号理論」の基礎にもなっています．インターネットにおいては，様々なデータが行き交います．個人情報も例外ではありません．したがって，「情報セキュリティ」や「コンピュータネットワーク」において，暗号化は避けて通れない問題です．

  2. アルゴリズムとデータ構造

    　　何らかの仕事をコンピュータで処理するため，プログラムを作成しようとしたとき，第一に考えるのはそのアルゴリズム（処理手順）です．又，同時に，必要なデータをどのような形で表現すべきかも検討する必要があります．その際，すべてのアルゴリズムを新規に考える必要はなく，多くのプログラムで頻繁に使用されるアルゴリズムやデータ構造については，数多くの研究がなされ，その結果が得られています．それらの内容に対する講義が，「アルゴリズムとデータ構造」と次に述べる「数値解析」です．

    　　アルゴリズムの例として，二次方程式の根を求めることについて考えてみます．このことをコンピュータに実行させるためには，少なくとも，以下に示す手順に従ってプログラムを書く必要があります．

      1. 二次方程式の係数の入力
      2. もし，係数 a が 0 であれば以下の処理を行う　｛
        1. もし，係数 b が 0 であれば，
          1. 解が存在しないことを出力
        2. そうでなければ，
          1. 一次方程式として解を求める
      3. ｝
      4. そうでなければ，以下の処理を行う　｛
        1. 判別式を計算する
        2. もし，判別式が 0 以上であれば，
          1. 二実根（重根を含む）を計算して出力
        3. そうでなければ，
          1. 虚根の実数部と虚数部を計算して出力
      5. ｝

    　　また，データを大きい順，小さい順，アルファベット順などに並べ替える作業（ソート）は，データ量が多くなると大変な作業になります．そのため，ソートに対する様々なアルゴリズムが提案されています．例えば，以下に示すのは，バブルソートの概念図です．この例は，上から小さい順に並べたい場合であり，赤で示す数字をすぐ上の数字と比較し，「上の数字の方が赤で示す数字より大きければそれらを入れ替える」という作業を繰り返すことによって並べ替えを行っています．データの数が多くなれば，かなり大変であるということが分かると思います．

  3. 数値解析

    　　代数方程式を解く，非線形方程式を解く，積分を行う，微分方程式を解く，など，「ソフトウェア」によっては，数学的な計算を行なわなければならない場合があります．それらのアルゴリズムについて講義するのが「数値解析」です．

    　　コンピュータで行えるのは，基本的に，数値的な計算です．例えば，x3 の 0 から 3 までの積分を，

    のように，解析的に積分を実行してから計算するわけではありません．コンピュータは，解析的な計算は不得意です．また，上のような方法をとれば，解析的に積分できない式に対応できません．そこで，コンピュータでは，積分区間（上の例では，0 から 3 ）を n 等分し，各区間の面積を台形で近似し，その和を求めるといったような方法で計算します（右図は，3 等分した例であり，赤で示した３つの台形の和になります）．この方法によれば，解析的に積分できない関数に対しても適用できますし，又，n を十分大きく取れば精度的にも問題ありません．

    　　次に，以下に示す代数方程式をコンピュータが実行する方法と似たような方法で解いてもらいます． 
    2x + 4y - 2z = 4
2x +  y +  z = 7
 x +  y +  z = 6
    次に示す表（行列）は，上の方程式の係数だけを並べたものです．以下，この表を対象として，以下に示すような処理を行ってみてください．

      1. 1 行目の各要素を 2 で割る
      2. 2 行目の各要素から，1 行目の各要素を 2 倍したものを引く
      3. 3 行目の各要素から，1 行目の各要素を引く
      4. 2 行目の各要素を -3 で割る
      5. 1 行目の各要素から，2 行目の各要素を 2 倍したものを引く
      6. 3 行目の各要素に，2 行目の各要素を加える
      7. 1 行目の各要素から，3 行目の各要素を引く
      8. 2 行目の各要素に，3 行目の各要素を加える

    　　たとえば，a，及び，b の手続きを実行すると，行列は以下のように変化していきます．最終的に，すべての手続きを終了した後における行列の最後の列が方程式の解になります．実際に解になっていることを確認してください．

  4. オペレーションズ・リサーチ

    　　「オペレーションズ・リサーチ」は，第二次大戦中に始まった兵器システムに対する運用研究に端を発しています．今日では，以下に示すように，コンピュータシステム，経営システムなど，様々なシステムに対する運用方法や問題解決手法を含んでいます．「ソフトウェア」開発者は，問題にもよりますが，これらの手法を十分理解し，使いこなせる必要があります．そのためには，「線形代数」や「微分積分」，場合によっては，「確率・統計」に対する知識も必要です．

    1. 数理計画法：　システムの最適化を行うために使用する手法です．最適化問題では，目的関数の最大値または最小値をある条件（制約条件）の基で求めることになりますが，目的関数や制約条件の性質によっていくつかの手法に分類されます．目的関数と制約条件がすべて線形関数で表現される「線形計画法」，目的関数や制約条件の一部に非線形関数が含まれる「非線形計画法」，変数の取り得る値が離散的である目的関数や制約条件が含まれる「組み合わせ最適化」などです．

    2. 動的計画法：　時間的または空間的に，多段階の決定問題として表現可能なシステムの最適化問題を解くための手法です．

    3. 待ち行列：　例えば，駅に切符の自動販売機を設置したいとします．お客さんの数に比較して台数が少なければ，切符を買うために並ぶ列が長くなりお客さんの評判が悪くなります．台数を多くすれば，評判はよくなりますが，費用がかかります．このような問題を扱うのが「待ち行列」です．「待ち行列」は，コンピュータシステムにとっても非常に重要です．コンピュータやプリンタなどの台数・能力を決めるためには，切符の自動販売機と同様のことを検討しなければなりません．

    4. 在庫管理：　商品に対する在庫を大量に持てば品切れの心配はなくなります．しかし，在庫に要する費用の増加，品物の劣化などの問題が生じます．逆に，在庫を少なくすれば，在庫に要する費用は少なくなりますが，品切れによる損失が生じます．このような問題を取り扱うのが「在庫管理」です．

    5. スケジューリング：　工場（ショップ：shop）において，所要時間や納期遅れが最小になるように，各仕事（ジョブ：job）を各機械でどのような順序で加工すべきかを決めることは，非常に重要な問題です．仕事がすべて同じ機械順序で加工を受ける場合をフローショップ（flow shop）問題，また，仕事によって機械の処理順序が変化して良い場合をジョブショップ（job shop）問題と呼びます．

      　　また，プロジェクトスケジューリングの手法には，PERT と CPM という２つの有名な方法があります．ここでは，簡単な例を使用して，PERT について説明します．A～L の作業から成るプロジェクトがあり，各作業の所要時間（単位：日），及び，それらの先行関係は以下の通りであるとします．

      作業 所要時間 先行作業 作業 所要時間 先行作業
      A 5 - G 4 D
      B 3 - H 3 D, E
      C 2 - I 5 H
      D 2 A J 1 G, I
      E 8 B, C K 2 H
      F 5 C L 2 F

      　　この例に対して PERT ネットワークを作成すると，以下のようになります．矢印上に書かれたアルファベットは作業，また，カッコ内の数字は作業時間です．

      　　この図に対して，下に示す 2 つの値を計算すると，その下に示す図のようになります．

      1. 最早開始時刻（Earlist Start Time; ES）：　時刻 0 にプロジェクトを開始したとき，ある結合点に最も早く到達可能な時刻（四角の上の段に記入）．

        • 作業 A，B，及び，C は，先行作業がありませんのですぐ開始できます．従って，① の左の四角の上段には 0 が入ります．

        • 作業 D は，作業 A が終わらないと開始できません．作業 A には 5 日かかりますので，② の上の四角の上段には 5 が入ります．同様に，④ の下の四角の上段には 2 が入ります．

        • 作業 E の先行作業は B と C ですが，作業 B の方が時間がかかりますので（ 3 日），③ の上の四角の上段には 3 が入ります．

      2. 最遅完了時刻（Latest Finish Time; LF）：　結合点 i を始点とする作業 pij によって結合されているすべての結合点 j へ，最早開始時刻前に到達するために，結合点 i に到達していなければならない時刻（プロジェクトの終了を表す結合点から順に計算．四角の下の段に記入）．

        • 最早開始時刻の計算によって，最終的に，⑩ の右の四角の上段に 50 という数値が入ったとして，以下，説明を行います．この 50 という数値は，すべての作業が完了するまでに，最も早くても 50 日かかることを意味しています．まず，⑧ の上の四角の下段について考えてみます．作業 J は 1 日かかりますので，すべての作業を 50 日で終了するためには，遅くとも 49 日目には作業 J を開始しなければなりません．したがって，ここには 49 が入ります．同様に，⑦ の下の四角の下段には 48 が入ります．

        • 次に，⑨ の下の四角の下段について考えてみます．作業 K だけのことを考えれば，48 日目に開始すればよいのですが，作業 I のことを考えるとそうはいきません．⑧ の四角の下段の値より，作業 J は，遅くとも 49 日目には開始しなければなりません．もし，作業 I を 48 日目に開始すると，作業 I に 5 日かかるため，作業 J を 49 日目に開始できなくなります．作業 J を 49 日目に開始するためには，遅くとも，作業 I を 44 日目に開始しなければなりません．したがって，⑨ の下の四角の下段には 44 が入ります．

  5. 統計解析

    　　情報学の様々な分野で確率や統計に関する知識が必要になります．「統計解析」は，それに対応するための科目です．先に述べた「オペレーションズ・リサーチ」における「待ち行列」は，「待ち行列」という確率的事象を対象としています．切符の自動販売機の例を考えてみても，「何時何分にお客さんが来る」などということを前もって知ることはできません．「ランダム（何らかの規則性はありますが）にお客さんが来る」と考え，確率・統計的な手法で解析せざるを得ません．

    　　また，心理学的な実験やアンケートなどに対する結果の解析には，必ず統計的な処理が必要になります．例えば，得られた平均値などの値が信頼できるものなのか（統計的検定），変数間にはどのような関係があるのか（多変量解析）といった疑問に答えるためには，どうしても確率や統計に対する知識が必要です．

    　　例として，仮説検定を取り上げてみます．仮説検定を定義すれば以下のようになります．

    　　「 1 つの仮説 Ｈ0（帰無仮説と呼ぶ）をたてて，実験・調査によって得られた標本の測定値の結果がその仮説のもとで起こる確率を計算する．その確率が一定基準より小さいとき仮説 Ｈ0 は正しくないものとして棄却する．この方法を仮説検定という．仮説を棄却する基準として，普通，5 ％または 1 ％が用いられ，これを有意水準という．仮説 Ｈ0 が有意水準αで棄却されたとき，検定結果は水準αで有意差があるという．また，仮説を棄却する範囲のことを棄却域という．」

    　　　第一種の誤り：仮説が正しいのに，それを棄却する誤り
    　　　第二種の誤り：仮説が正しくないのに，それを棄却しない誤り

    　　では，実際に，仮説検定を実際に行ってみましょう．ある仕事に対する男性と女性の適正を判断するため，適性検査を行ったところ以下に示すような結果が得られました．

    男性　人数：n1 = 10 人，　平均点：x1 = 70.0，　標準偏差：s1 = 9.5
    女性　人数：n2 = 7 人，　平均点：x2 = 80.0，　標準偏差：s2 = 10.5

    点数が高いほど適性があることを示している場合，以上の結果から，「男性より女性の方がその仕事に適している」ということが言えるでしょうか．この疑問に対して答えるために，仮説検定を行ってみます．まず，帰無仮説

    帰無仮説： 「男性及び女性の平均点が等しい（適性に差がない）」

    を設定します．今，男性及び女性に対する適性検査の結果が正規分布をし，かつ，その標準偏差が等しいとすると，平均点の差，

    は，自由度（ n1 + n2 - 2 ）の ｔ 分布をします．なお，ｔ 分布とは，以下に示すような分布です．

    得られたデータに基づいて，t0 の値を計算すると，以下のようになります．

    ( 9 × 9.52 ＋ 6 × 10.52) ／ ( 10 ＋ 7 － 2 ) = 98.25
    (98.25 × (10 + 7) / 70)0.5 = (23.86)0.5 = 4.885
    t0 = 10 / 4.885 = 2.047

    ここで，自由度 15 の ｔ 分布における 5 ％値を求めると，1.75 になります．5 ％値とは，この値より大きくなる確率が 0.05 となるような値です（図の斜線部分の面積が 0.05 ）．上で計算した t0 の値は 2.047 であり，5 ％値 1.75 より大きくなります．したがって，このような値になる確率は 0.05 以下であり，滅多に起こらないことであることを示しています．このようなことになった原因は，2 つの平均値が等しいとした仮説にあり，その仮説が間違っていたことになります（仮説を棄却する）．つまり，「男性より女性の方がその仕事に適している」と言えることになります．勿論，これは，確率的な結論であり，2 つの平均値が等しいにもかかわらず，今回のような検査結果になる確率も 5 ％程度存在します（第一種の誤り）．

    　　それでは，同じ条件下で，男性の人数が 5 であった場合はどのようになるでしょうか．帰無仮説をたて，t0 の値を計算し，結論を導いてください．なお，自由度 10 の ｔ 分布における 5 ％値は，1.81 になります．

目次