Embed Size (px)
Citation preview
情報活用演習 Exercise in Information Literacy
冨樫 祐一 (Yuichi TOGASHI) 25 July 2018
1
∗ コンピュータ操作入門（２回） ∗ グラフを作るには（gnuplot入門）（２回） ∗ 綺麗な数式を書くには（LaTeX入門）（４回）
∗ 第１回レポート課題
∗ コンピュータはどうやって動いているか（３回） ∗ コンピュータの動作原理～歴史を遡る
∗ コンピュータをどうやって動かすか ～プログラミングの基礎（４回）
∗ やや変則的ですが、１コマ目と２コマ目で内容が変わります。 ∗ 座学と演習を１コマずつという形にします。
∗ 第２回レポート課題
今回の内容
2
∗ 少し分かりにくかったようですが ∗ 組合せ回路 ∗ 記憶（内部状態）を持たない。 ∗ nビットの入力があったら、即座かつ一意に、mビットの出力
が決まる。要するにただの関数（論理関数）。 ∗ 順序回路 ∗ 組合せ回路に加え、内部状態を保持するメモリがある。 ∗ 出力は、入力と内部状態に依存して決まる。
∗ 組合せ回路だと、入力されるデータの個数が増えればそれだけ入力を受け取る回路が必要。任意の個数なら無限の回路に。
∗ 順序回路にして途中までの結果を覚えておけば解決。例えば、２入力の加算とメモリで、任意の個数の入力の総和が求まる。
前回の補足：論理回路
3
コンピュータは どうやって動いているか
コンピュータの動作原理 ～歴史を遡る～
4
∗ 前回は、 現代の、現実のコンピュータについてでした。
∗ しかしそもそも、 なぜ、これで様々な処理ができる？
∗ コンピュータの本質は何？
∗ 実はここで、数学者が大いに活躍してきました。 ∗ 今回の講義では、その歴史を遡っていきます。
コンピュータの動作原理
5
∗ 前回の講義より ∗ 中央処理装置（CPU）＝ 演算装置 ＋ 制御装置 ∗ 現在では、これらをまとめて１つの半導体集積回路で構成：
マイクロプロセッサ（MPU: Micro Processing Unit） ∗ マイクロチップに実装されたプロセッサ＝マイクロプロセッサ
∗ マイクロプロセッサが登場して以降、コンピュータの作り方は基本的には変わっていない。 ∗ 性能は劇的に上がっていますが。
マイクロプロセッサ
6
∗ では、 今のようなつくりのコンピュータの始まりは？
∗ マイクロプロセッサは、いつ頃からあったでしょうか？ 1. 1980年代（約30年前） 2. 1970年代（約40年前） 3. 1950年代（約60年前） 4. 1930年代（約80年前） 5. 1910年代（約100年前）
計算機の歴史
7
∗ マイクロプロセッサの始まり ∗ intel 4004 （1971年） 初のシングルチップ商用MPU
∗ 電卓用に開発 ∗ 4ビット ∗ 2300トランジスタ（10μmプロセス） ∗ 動作クロック0.741MHz（※最短8クロック／命令）
∗ 比較：同じintelのサーバ用CPU Xeon E7-8890 v4（2016年） ∗ 最新世代の集積度のデータが見つからなかったので１世代前ですが。
∗ 64ビット ∗ 72億トランジスタ（14nmプロセス、24コア） ∗ 動作クロック2.2～3.4GHz ∗ つまり、45年で集積度は数百万倍、動作クロックは数千倍に。
∗ 余談：40年前と最新のCPU勝負 https://www.youtube.com/watch?v=o_JdkYJsKUo
マイクロプロセッサの登場
8
∗ 前回の講義より ∗ プログラム内蔵方式：
処理する内容をプログラムとして指示でき、 そのプログラムはコンピュータ（のメモリ）に内蔵される。 ∗ 内蔵でない例として、人が順次操作したり、パンチカードや紙
テープで与えたり。 ∗ ノイマン型コンピュータ：
プログラム内蔵方式のコンピュータのうち、プログラムとデータが同じメモリ上に置かれるもの。 ∗ プログラム内蔵方式だがノイマン型ではない（プログラムと
データが別々のメモリに分かれているなど）構成もある。
プログラム内蔵方式 ～ノイマン型コンピュータ
9
∗ では、 今のような原理のコンピュータの始まりは？
∗ ノイマン型コンピュータは、いつ頃からあったでしょうか？ 1. 1960年代（約50年前） 2. 1940年代（約70年前） 3. 1910年代（約100年前） 4. 1870年代（約140年前） 5. 1830年代（約180年前）
計算機の歴史
10
∗ マイクロプロセッサ登場前、 コンピュータは、一般にもっと大型のものでした。 ∗ この分類もすでに古典的ですが、コンピュータの世代
∗ 第四世代：MPUのような大規模集積回路(LSI, VLSI)（1980年頃～） ∗ 第三世代：集積回路(IC)（1960年代～） ∗ 第二世代：トランジスタ（1950年代～） ∗ 第一世代：真空管（1940年代～）←ノイマン型コンピュータ登場
∗ メインフレーム（大型汎用コンピュータ）は、今でも使われていますが（例えば金融機関の基幹系システム）。 ∗ 第三世代にもミニコンピュータというメインフレームよりは小さな
コンピュータがありましたが、MPUによるマイクロコンピュータに取って代わられていきました。
マイクロプロセッサ登場より前
11
計算機の歴史 写真はWikipediaより
1970年頃のミニコン (DEC PDP-11)
1950～60年代のメインフレーム (IBM 704)
12
∗ ところで、現在のも含めて、 ノイマン型コンピュータは、どんな問題でも解けるのか？ どこまでなら解けるのか？
∗ そもそもなぜこのような形を考えたのか？ ∗ もっと昔の計算機はどうだったのか？
ノイマン型コンピュータ
John von Neumann (1903-1957)
13
∗ そろばん ∗ 計算尺
∗ 1642 パスカルの機械式計算機 ∗ 歯車で足し算と引き算
∗ 1670年代 ライプニッツの計算機開発 ∗ 掛け算・割り算も ∗ ここから派生した機械式計算機は、クルタ計算機（1948年）
など、かなり後まで使われることに。 ∗ 電卓と同等の機能。プログラムはできない。
昔の計算機
Blaise Pascal (1623-1662)
Gottfried Wilhelm Leibniz (1646-1716)
14
計算機の歴史 写真はWikipediaより
1970年頃のミニコン (DEC PDP-11)
1950～60年代のメインフレーム (IBM 704)
パスカルの計算機
15
∗ 1837～1871 バベッジによる解析機関開発の試み ∗ プログラムできる
機械式汎用デジタル計算機.。 ∗ 蒸気機関で駆動。 ∗ プログラムとデータは
パンチカードで入力。 ∗ メモリを持つ。 ∗ 条件分岐命令も。 ∗ 一部は製作されたが、
製作技術や資金の問題で完成しなかった。 ∗ 「世界初のプログラマ」
解析機関
Charles Babbage (1791-1871)
Ada Lovelace (1815-1852)
16
計算機の歴史 写真はWikipediaより
1970年頃のミニコン (DEC PDP-11)
1950～60年代のメインフレーム (IBM 704)
バベッジの解析機関 （一部分の試作機）
パスカルの計算機
17
∗ 1936 Zuse Z1 ∗ 初のリレー式計算機。
∗ 1941 Zuse Z3 ∗ 初のプログラム可能な計算機（但し条件分岐なし）。リレー式。
∗ 1946 ENIAC ∗ プログラム可能な汎用電子計算機（配線をパッチパネルで変更
した。プログラム内蔵方式とはいえない）。真空管式。 ∗ 1949 EDSAC ∗ 実用的なプログラム内蔵方式の電子計算機として初。真空管式。
Zuse・ENIAC・……
18
計算機の歴史 写真はWikipediaより
1970年頃のミニコン (DEC PDP-11)
1950～60年代のメインフレーム (IBM 704)
バベッジの解析機関 （一部分の試作機）
パスカルの計算機
ENIAC
Zuse Z3（復元）
19
∗ ところで、現在のも含めて、 ノイマン型コンピュータは、どんな問題でも解けるのか？ どこまでなら解けるのか？
∗ そもそもなぜこのような形を考えたのか？ ∗ もっと昔の計算機はどうだったのか？
∗ ノイマン型コンピュータには、
理論的な原型がある → チューリング機械
ノイマン型コンピュータ
Alan M. Turing (1912-1954)
John von Neumann (1903-1957)
20
∗ ひとまず、簡単のため、 判定問題： 与えられた入力（文字列）に関して、何らかの主張の真偽を答えるような問題 について考えます。
∗ 機械Mが判定問題Lを解く、とは、 L(x) = 真 なる任意の文字列xについて、Mはxを受理し、かつ L(x) = 偽 なる任意の文字列xについて、Mはxを拒否する ことをいう。
問題を解く、とは
21
∗ 有限状態機械は、 次のものにより指定される。 ∗ 有限個の状態の集合Q
∗ 但し、始状態と呼ばれる状態 q始∈Qと 、受理状態と呼ばれる状態の集合 Q受理⊆Q が定まっている。
∗ 有限個の文字の集合Σ ∗ 遷移規則と呼ばれる関数δ: Q×Σ → Q
∗ 以下のように動作 ∗ 始状態から始めて、１文字読むごとにそれに応じて状態遷移。 ∗ 文字列の終端に達した時に、状態が受理状態であれば、機械が
その文字列を受理したといい、そうでなければ拒否したという。
有限状態機械（有限オートマトン）
22
∗ 例えば ∗ Σ={a, b} としたとき ∗ 文字列xに現れるaの個数が3の倍数であるか、判定せよ。
∗ L(x)=真（xに現れるaの個数が3の倍数であるとき） ∗ L(x)=偽（そうでないとき）
∗ これは有限状態機械で解けます。 ∗ 状態の集合Q、遷移規則δとして、どのようなものを考えたら
良いですか？ ∗ ヒント：状態を○（そのうち受理状態は◎）で、遷移を→で表して
みてください（これを状態遷移図といいます）。始状態q0として… ∗ ヒント：始状態q0の他に、あと２つの状態が必要です。 ∗ ヒント：受理状態はq0のみとできます。
有限状態機械（有限オートマトン）
23
∗ 例えば ∗ Σ={a, b} とし、文字σをn個並べた文字列をσｎで表す。 ∗ 文字列xについてあるnが存在してx=anbn であるか、判定せよ。 ∗ これは有限状態機械で解けません。 ∗ なぜなら、
∗ そのような機械Mがあるとする。 ∗ 文字列a, aa, aaa, ... をそれぞれ与えた時に至る状態を考える。 ∗ 状態は有限個なので、amを読んだ後とanを読んだ後の状態とが一致
するようなm≠nが存在する。この状態からbnを読んで至るのが ∗ 受理状態であれば、Mはambn を受理し、L(ambn )=偽（m≠n）に反する。 ∗ 受理状態でなければ、Mはanbn を拒否し、L(anbn )=真に反する。
∗ いずれにせよ矛盾するので、これを解く有限状態機械は存在しない。
有限状態機械（有限オートマトン）
24
∗ 解けない問題がある。 ∗ 今の有限状態機械では、文字列を端から順に読んでいた。 ∗ テープを左から右へ１区画ずつ移動。
∗ テープを両方向に動けることにしたらどうか。
有限状態機械の限界
25
∗ 両方向有限状態機械は、 次のものにより指定される。 ∗ 有限個の状態の集合Q
∗ 但し、始状態と呼ばれる状態 q始∈Qと 、受理状態と呼ばれる状態の集合 Q受理⊆Q が定まっている。
∗ 有限個の文字の集合Σと、これに空白文字を加えた集合Γ ∗ 遷移規則と呼ばれる関数δ: Q×Γ → （Q×{左,右}）∪ {止}
∗ つまり、読んだ文字に応じて、状態遷移するのに加えて 左右どちらかに１区画だけ動く、あるいは停止する。 ∗ 無限に長いテープに文字列が書かれていると考えます。
有限状態機械の限界
26
∗ 一見、良さそうだが、実は、 両方向にしても解ける問題は増えない。 ∗ 問題Lを解く両方向有限状態機械が存在するなら、
Lを解く（両方向でない）有限状態機械が存在する ことを証明できる。
∗ このように定義を多少変えても概念そのものが変わりにくいことを、その概念が頑健であるということがある。
有限状態機械の限界
27
∗ 文字列を読むだけだった。 ∗ 文字を書けることにしたらどうか。 ∗ チューリング機械は、次のものにより指定される。 ∗ 有限個の状態の集合Q
∗ 但し、始状態と呼ばれる状態 q始∈Qと 、受理状態と呼ばれる状態の集合 Q受理⊆Q が定まっている。
∗ 有限個の文字の集合Σと、これに空白文字を加えた集合Γ ∗ 遷移規則と呼ばれる関数δ: Q×Γ→（Q×Γ×{左,右}）∪ {止}
∗ つまり、読んだ文字に応じて、状態遷移するのに加えて 文字を書き換えてから左右どちらかに１区画だけ動く、 あるいは停止する。 ∗ 無限に長いテープに文字列が書かれていると考えます。
チューリング機械
28
∗ といっても、 そもそもどんな動作をするのか分かりにくいと思うので、やってみます。 ∗ 人力で…… ∗ ここでは見やすいように文字を {0, 1} にしましたが、
１種類の文字の集合Σ={1}と、それに空白文字を加えたΓ、 と考えても同じです。
∗ https://www.youtube.com/watch?v=FTSAiF9AHN4
チューリング機械
29
∗ 両方向有限状態機械と比べると、 文字を書く機能が与えられたことになります。 ∗ 遷移規則の行き先のΓ
∗ これによって、有限状態機械では解けなかった問題でも、 解けるようになるものがあります。 ∗ 例えば、先ほどの、
文字列xについて、あるnが存在してx=anbn であるか判定。 ∗ 同様に、aがbよりも多いか判定する問題。
∗ 後者は、 左端から右に読み進めて、初めて現れたaをcに書き換える。 右端から左に読み進めて、初めて現れたbをcに書き換える。 bが先になくなったら受理。 という形で構成できる。
チューリング機械
30
∗ 有限状態機械の場合と同様に、 チューリング機械の能力（計算可能性）も、定義の細部にはよらない頑健な概念。
∗ 例えば、チューリング機械に、 ∗ ある桁数の整数同士の加算・減算が一度にできる。 ∗ 動くのが必ず左右１文字ずつでなく、その場にとどまれたり、
指定文字数分だけジャンプできたりする。 ∗ テープが複数本ある。あるいは、２次元のマス目になっていて
上下左右に動ける。 といった機能を加えても、解けるかどうかは変わらない。
チューリング機械の能力
31
∗ それどころか、今日まで、 これを超える能力を持つ計算の仕組みは作れていない（！）
∗ チャーチ・チューリングのテーゼ： およそ明確に記述された処理手順はみなチューリング機械で書ける、という主張。 ∗ 「明確に記述された処理手順」が厳密な概念でないので、
これは数学的に証明することができるようなものではないが、今のところ、特にこれに反するような例も見つかっておらず、 広く受け入れられている。
チューリング機械の能力
32
∗ 現実の問題では ∗ 入力は単なる文字列ではないかも知れない
→ 何らかの決まった方法で文字列に符号化すれば良い。 ∗ 数値を2進数なり10進数なりで文字列として書き表す ∗ 数値が複数あったら区切り文字を挟む など。
∗ 真偽の判定でなく、何かを探し出して答える形の問題であるかも知れない。 ∗ 元の目標とは違うかも知れないが、求める（発見すべき）もの
が存在するかどうかを判定する問題を考えることはできる。 問題の難しさを考える上では、密接に関連。
∗ 例えば、与えられたグラフのハミルトン路（辺をたどって全ての頂点を一度ずつ巡る経路）を１つ求める問題。
チューリング機械の能力
33
∗ では、何でも解けるのか？ ∗ 判定不能問題：どのようなチューリング機械によっても
解けないような判定問題。 ∗ チューリング機械の停止問題：
あるチューリング機械が、ある入力に対して、有限時間で 停止するかどうか判定せよ。
→ 判定不能！ ∗ 少し長くなりますが、証明してみます。
チューリング機械の能力
34
∗ 停止問題： ∗ チューリング機械は先ほどの定義にある要素から定まるもので
あるので、文字列で表せる。 ∗ 入力文字集合Σ={0, 1}であるような機械を文字列で表す方法を
決める。 ∗ 文字や状態は、その間の関係だけが重要で、名前は何でも良いので、
2進法で名前を付けてしまえば良い。 ∗ さらに、この記述の中にある各文字を適当に符号化して、{0, 1}
上の文字列で表す。 ∗ このとき、機械Mを表す文字列をMと呼ぶことにする。
判定不能問題
35
∗ 停止問題： ∗ ここで、{0, 1}上の文字列Mとxに対して、「機械Mに文字列xを
入力すると停止する（受理または拒否する）」ことを停M(x)と書くことにする。 ∗ 文字列Mがそもそも機械の記述になっていない時は、便宜的に、
停M(x)は成り立たないとしておく。 ∗ 与えられたMとxに対して停M(x)の成否を判定する問題
L(M, x)=真（停M(x)であるとき）・偽（そうでないとき） を停止問題と呼ぶ。
∗ 以下で、これを解くチューリング機械が存在しないことを示す。
判定不能問題
36
∗ 停止問題： ∗ L(M, x)=真（停M(x)であるとき）・偽（そうでないとき）
を停止問題と呼ぶ。 ∗ ここで入力がM, xと２つの文字列になっているが、適当な区切
り文字を挟んで、例えばM#xのように書くことにする。 ∗ 上のLは{0,1,#}上の文字列を入力とする問題ということになる。
∗ この問題Lを解く機械Nが存在したとする。Nは入力M#xに対し、停M(x)なら受理し、停M(x)でなければ拒否する。
∗ この時、次のような機械Dを考える。 ∗ Dは、入力文字集合{0, 1}上の文字列xを受け取り、それを複写して
x#xに書き換えてから、これを入力とするNの動きをする。 ∗ 但し、Nが受理する時には、代わりに受理状態でないある状態に
なって、以後ずっと停止せずにその状態を繰り返す。
判定不能問題
37
∗ 停止問題： ∗ この時、次のような機械Dを考える。
∗ Dは、入力文字集合{0, 1}上の文字列xを受け取り、それを複写してx#xに書き換えてから、これを入力とするNの動きをする。
∗ 但し、Nが受理する時には、代わりに受理状態でないある状態になって、以後ずっと停止せずにその状態を繰り返す。
∗ 元の機械Nが入力M#xに対し、 停M(x)なら受理し、停M(x)でなければ拒否することを考えると、この機械Dは、入力xに対し、 停x(x)なら停止せず、停x(x)でなければ停止する。
∗ これが任意のxについて成り立つのだからx=Dでも成り立つはず。 ∗ しかし、停D(D)なら停止するので前半が成り立たない、停D(D)
でなければ停止しないので後半が成り立たないので、矛盾する。
判定不能問題
38
∗ 停止問題： ∗ ここで、縦軸に全ての文字列D、横軸に全ての文字列xを並べて、
停D(x)の真偽を表にしてみる。 ∗ 対角線上の要素が、停x(x)を表していることになる。 ∗ 先ほどの証明中で、機械Dは、入力xに対し、
停x(x)なら停止せず、停x(x)でなければ停止する。 ∗ つまり、これは、
対角線上の要素の真偽を入れ替えて横に並べたような挙動。 ∗ しかしそれは表の中のどの行とも一致しない
（どの行を考えても対角線のところが不一致になってしまう）。 すなわち、そのような機械Dは存在しない。
∗ この証明法（背理法の一種）は、表の対角線上の成分に注目 したことから、対角線論法と呼ばれます。
判定不能問題
39
∗ 先週の講義で見せた Raspberry Pi 3ですが、生協などでも扱っています。 ∗ 5000円くらいしますが、遊んでみたい人は。 ∗ ちなみに、
基板をよく見ると……
ひとやすみ
40
メモリ （メインメモリ・ ビデオメモリ兼用）
41
∗ 見覚えありませんか？
ひとやすみ
42
∗ もうひとつ。お気付きでしょうか？
ひとやすみ
43
∗ くねくねしてるのはわざと。 ∗ 信号のタイミングがずれないように、長さを揃えています。 ∗ 真空中の光速でも、1GHzなら波長30cm、3GHzなら波長10cm。
銅線の中を伝わるのは当然これより遅いので、cm単位の違いでも結構なタイミングのズレになります。
ひとやすみ
44
∗ 今日まで、 これを超える能力を持つ計算の仕組みは作れていない（！）
∗ チャーチ・チューリングのテーゼ： およそ明確に記述された処理手順はみなチューリング機械で書ける、という主張。 ∗ 「明確に記述された処理手順」が厳密な概念でないので、
これは数学的に証明することができるようなものではないが、今のところ、特にこれに反するような例も見つかっておらず、 広く受け入れられている。
チューリング機械の能力
45
∗ では、何でも解けるのか？ ∗ 判定不能問題：どのようなチューリング機械によっても
解けないような判定問題。 ∗ チューリング機械の停止問題：
あるチューリング機械が、ある入力に対して、有限時間で 停止するかどうか判定せよ。
→ 判定不能！
チューリング機械の能力
46
∗ ところで、今までの話では、 問題ごとにそれを解くチューリング機械を考えていた。
∗ 実際のコンピュータは１台で色々な問題を解ける。
∗ 任意のチューリング機械を模倣できるようなチューリング 機械があれば解決。
万能チューリング機械 (UTM)
47
∗ 実際に、 任意のチューリング機械を（以下の意味で）模倣するようなチューリング機械を作ることができる。
∗ 任意のチューリング機械Mと、任意の文字列xに対して、 ∗ Mがxを受理するとき、Uは(M, x)を受理し ∗ Mがxを拒否するとき、Uは(M, x)を拒否する
ようなチューリング機械Uが存在する。 ∗ 先ほどの証明で用いたのと同様に、{0, 1}を入力文字集合とする
機械Mを{0, 1}上の文字列として符号化、さらに(M, x)は文字列 Mとxを適当な区切り文字を挟んで並べたものとする。
∗ Mが停止するか判定することはできないが、それで構わない。 停M(x)でない入力(M, x)に対してはUも停止しなくて良い。
万能チューリング機械
48
∗ このような機械Uのことを 万能チューリング機械（Universal Turing Machine） といったりします。
∗ 実際にコンピュータを作ることを考えてみると、 機械Mそのものをハードウェアとして用意しなくても、 １つの万能機械Uを用意して、それにMを記述した文字列（すなわちプログラム）を与えることで実現できるという ことになる。 ∗ つまりこれが、プログラム内蔵方式の計算機の理論的背景に
なっています。
万能チューリング機械
49
∗ ある計算メカニズム （コンピュータの命令セット、プログラミング言語など）が 万能チューリング機械と同じ計算能力を持つとき、 チューリング完全であるという。 ∗ 時間やメモリ容量の制約については考えない。
∗ バベッジの解析機関は完成していればチューリング完全を実現
していたといわれる。 ∗ Zuse Z3は理論的には（記憶容量が無限と仮定すれば）チュー
リング完全とされる（条件分岐命令を持たないため、実際上は等価ではない）。
∗ ENIACはチューリング完全。
チューリング完全
50
計算機の歴史 写真はWikipediaより
1970年頃のミニコン (DEC PDP-11)
1950～60年代のメインフレーム (IBM 704)
バベッジの解析機関 （一部分の試作機）
パスカルの計算機
ENIAC
Zuse Z3（復元）
51
∗ 組合せ回路 ∗ 記憶（内部状態）を持たない。 ∗ nビットの入力があったら、即座かつ一意に、mビットの出力
が決まる。要するにただの関数（論理関数）。 ∗ 順序回路 ∗ 組合せ回路に加え、内部状態を保持するメモリがある。 ∗ 出力は、入力と内部状態に依存して決まる。
∗ 順序回路にすることではじめてチューリング完全にすることができる。 ∗ もちろん順序回路が全部チューリング完全なわけはない。
前回の論理回路の話との関係
52
∗ もう少し、計算の理論の話を。 ∗ チューリング機械で解けるか解けないかという話をしました
が…… ∗ 無限に長いテープを使って、無限に長い時間をかければ。
∗ 実際には、問題の難しさの程度が。
∗ 計算量：プログラムの実行時間を見積もるための指標 ∗ 入力の大きさに応じて処理時間がどのように増えるか、
計算量のオーダーという大まかな概念で考える。 ∗ 例えばN個のデータを処理する時、Nに比例かN2に比例か。 ∗ アルゴリズム（後で説明）をもとに見積もられる。
計算量の理論
53
∗ さて、実際には、 コンピュータを使って現実世界の問題を解くことを考えると、問題からプログラムを作る過程があります。
∗ 詳しくみると ∗ 問題をモデル化する。
∗ モデル化：実際の事物・事象に対応する（代替としての）何らかの単純化・抽象化されたような事物・事象・概念を構築すること。
∗ モデル化された問題に対して、それを解く計算手順を考える。 ∗ 手順通りに計算するプログラムを解く。
∗ このプログラムになる前の計算手順のことを、アルゴリズムといいます。 ∗ 必ずしもコンピュータによって実行されなくても良い
（例えばユークリッドの互除法のように、はるか昔のものも）。
問題を解く
54
∗ アルゴリズムとプログラム ∗ 実際の計算量は、アルゴリズムによって変わる。 ∗ つまり、プログラムを作る以前に、アルゴリズムの選択が、
プログラムの実行時間に大きく影響することに。 ∗ 現実のプログラムを書く際にも、アルゴリズムの考え方は大切。
∗ 最も理想的なアルゴリズムを使った場合にどれくらいかかるか、ということに関して理論があります。次回はそれを少しみていきます。
アルゴリズムと計算量
55
∗ コンピュータ操作入門（２回） ∗ グラフを作るには（gnuplot入門）（２回） ∗ 綺麗な数式を書くには（LaTeX入門）（４回）
∗ 第１回レポート課題
∗ コンピュータはどうやって動いているか（３回） ∗ アルゴリズムとプログラム
∗ コンピュータをどうやって動かすか ～プログラミングの基礎（４回）
∗ やや変則的ですが、１コマ目と２コマ目で内容が変わります。 ∗ 座学と演習を１コマずつという形にします。
∗ 第２回レポート課題
次回予告
56
