平成14年度前期　計算論入門

授業要目

1. コンピュータによる計算のための基礎理論について講義する。
   • 「コンピュータで計算できる」とはどういうことか（計算可能性）について、Turing機械を題材に解説する。
   • 代表的なアルゴリズムと具体的な問題への適用、及び計算量の評価について解説する。
   これらは良いプログラムを作成するための基礎知識である。
2. テキストは初講時に指示する。
3. 参考書は講義時間中に指示する。
4. 計算機に関する予備知識は仮定しないが、線形代数・微積分の初歩は前提とする。
5. 数学の教職免許を取るための必須科目である。
6. 成績は学期末に行う試験（６０％）および授業の出欠やレポート（４０％）により評価する。
   

内容

かつて計算機と言えば、主に数の加減乗除を行う機械の事であった。

しかし、現在の電子計算機は、多様な作業を自動的に電気の力で高速かつ正確に行う。
今のところ電子計算機は自分で問題を解く方法を考えてくれるわけではなく、
どのような手続きの列（アルゴリズム）に沿って作業を行うか指示する必要がある
（もちろん、計算機が疑似的に考えているように見えることはあるが、
それも指示に従ってのことである）。

この講義では、次のような様々な問題について考えていくことにしよう。
これらを学ぶことによって、
計算機の良いプログラムを書く基礎知識を身につけることができるだけでなく、
計算の原理を理解することで現在の計算機でできる事柄の限界を知り、
（時間が許せば）近い将来の発展をも見る力をつけることができると期待する。

I. アルゴリズムと計算量

1. 与えられた問題に対してアルゴリズムを作成せよ。
また、それが正しいアルゴリズムであることを検証（証明）せよ。

2. アルゴリズムを解析し、計算量を評価せよ。

計算量は、計算に必要な時間や記憶領域の大きさで測る。
計算量が小さいに越したことはない。
入力データの大きさ n が大きくなるに従って計算量がどのくらいの速さで増加するか、
位数記法を用いて表わすことが多い。
代表的な指標として最大時間計算量・平均時間計算量・領域計算量などがある。

3. 与えられた問題に対して一般にアルゴリズムは複数ありうるが、それらの計算量の上限・下限を求めよ。

具体的にアルゴリズムを与えることは計算量の上限を与えることになる。
また、下限は理論的にアルゴリズムの必要計算量を詰めることによって与えられる。

\medskip
\noindent
II. 計算モデルと計算可能性
（参考書：計算論入門、渡辺治・米崎直樹共著、日本評論社、第2・3章）


4. そもそも与えられた問題に対して（ある計算モデルで）アルゴリズムが存在するか
（計算可能性）。

与えられた問題を解くアルゴリズムがあるか、
すなわち、問題が計算可能であるかについては、1930年代に様々な定式化がなされた。
実はそれらが全て同等の概念であることが示されたのであるが、
そのうちで帰納的関数とTuring機械計算可能について取り上げる。
普通の手続き型言語でプログラム可能であるということもこれらの概念と同等である。
また、準備として形式論理の初歩を学ぶ。

5. 計算可能であることは分かっていても、時間がかかりすぎて実際上は解を求めることができないと思われている問題が数多く存在する。

それぞれの問題が計算可能であるかないかは
どの（筆者の知る限りの、十分強力な）計算モデルを用いても同じ結果になるが、
計算量に関してはモデルによって
（たとえばメモリのランダムアクセスが可能かなどの様々な条件で）大きく異なる。

そこでよりおおざっぱに、与えられたデータの大きさ n が大きくなる時に、
計算時間が高々 n の多項式で書ける大きさでおさまるかどうかを問う。
計算機で解きたい大概の問題については、答の検証は多項式時間でできるのだが、
答を多項式時間で見つけるアルゴリズムが知られていない。
そんなアルゴリズムはないだろうというのが「P≠NP 予想」という
有名な問題である。
また、従来の計算機では速いアルゴリズムが知られていなかった問題で、
近年、量子計算機で多項式時間で解けるアルゴリズムが見つかったものがある。
これらの話題についても後に述べたい。

\medskip
\noindent
III. 数値解析

6. 数値計算のアルゴリズムについては、アルゴリズムの速度の他に、
どれだけ正確な（あるいは最適な）値を計算できるかも重要である。
数値積分など具体的な問題についていくつかの計算方法（と誤差）について述べる。


なお、この講義では取り扱わないが、
アルゴリズムを評価する際、入力データに関して一般性があるか（頑強性・汎用性など）という観点も重要である。
また、実際にプログラムを組むという点からは、アルゴリズムの単純性・実装の容易さ・拡張の容易さ・モジュール化のし易さ、という観点も重要である。
研究の進展のためには新規性・重要性があることも大切である。


また、内容としては関係ないが、高校数学の学習指導要領にあるので、
もし時間があれば次の内容についても触れる。

\medskip
\noindent
IV. 高校数学への計算機の援用

7. 表計算ソフトを用いた統計処理。

観測・測定・調査・実験などから得られた数字データを解析することを「統計データ解析」と呼ぶ。
母集団・頻度分布・ヒストグラム・平均値・中央値・最頻値・標準偏差・分散・変動係数・歪度・尖度・正規分布・二項分布・Poisson分布などについて学ぶ。

8. 数式処理ソフトを用いた曲線の表示。

4/15 （休講）
4/22 誤差、数値積分
5/ 7 代数方程式の数値解法
5/13 アルゴリズム（ユークリッドの互除法）、問題解法に役立つ考え方
5/20 基数の変換、位数記法、計算量（2進を用いた乗算・最大公約数・素数の列挙）
5/27 計算量の上限・下限（エラトステネスの篩、べき乗の評価、Horner法）
6/ 3 Turing機械（inc(x)、多テープTuring機械の模倣・記号数の削減、熱心なビーバー）
6/10 万能Turing機械、計算不可能な関数（Turing機械のコード化、halt(x)）
6/17 形式論理（命題論理、１階の述語論理）
6/24 帰納的関数（Ackermann関数）
7/ 1 帰納的関数とTuring機械計算可能な関数は同じ（Gödel数）
7/ 8 P≠NP問題（巡回セールスマン問題）
7/15 量子計算機
7/22 試験

研究室へ戻る