1
情報科学 第09回 前半
アルゴリズムとプログラミング
2/63
はじめに
我々は、計算機で様々なプログラムを利用しています。
では、これらのプログラムはどのようにして作られてい るのでしょうか?
また、プログラムする上で必要になる、基礎的な知識は なんでしょうか?
3/63
アルゴリズム
4/63
アルゴリズムとゲーム
アルゴリズムって?
問題を解くための手順。
ちゃんと書けていれば、誰が行っても同じ動作と同 じ結果に
身近な動作を書き下してみよう!
人の思考を書き下せれば、人工知能の完成!?
5/63
人の思考とアルゴリズム
以下の部品を適切に並べて、店屋物のカツ丼 を食べてみよう。
『食べる』『蓋を開ける』『お金を払う』『割り箸を割 る』『器を持つ』『カツ丼を受け取る』
でも、普段はこんなこ と考えながら行動して
ないしなぁ
6/63
代表的なアルゴリズム
次の値を、小さい順に並べかえてみよう。
やってよいこと:値の大小比較
値の場所の変更
3, 5, 2, 4, 1
7/63
データ処理とデータ構造
データ構造:
コンピュータにどのように組織化して格納 するか。
データ処理:
データを加工する方法や、その順番。
プログラム:
データを加工しつつ、正しい出力を求めて いくプロセスの記述。
プログラム→データ処理+データ構造
入力
データ
データ
出力 データ
…
格納
加工
加工
8/63
データ構造
コンピュータに、どのデータを、どのように格納するか。
キューの実現の仕方
Romberg積分法の、データの種類と蓄え方
data 10
0 1 5
0 1 2 3 4 5
0 0 4 tail
1 head
queue
構造体で 実現
1 ,
R1 1 ,
R2 1 ,
R3
1 ,
Rn 2 ,
R2 2 ,
R3
2 ,
Rn 3 ,
R3
3 ,
Rn
n
Rn, 1
,
R4 R4,2 R4,3 R4,3
4 ,
Rn
配列で実現 依存関係や処理順を 考慮して、全部保存 キューの内容と、
キューの先頭、
末尾が必要
9/63
データの処理
入力データを加工しつつ、正しい出力を求めていくプ ロセスの記述
キューへのデータの追加とか取り出し等
Romberg積分法で、解を出すまでの計算の順番等
data 10
0 1 5
0 1 2 3 4 5
0 0 4 tail
1 head
queue
1 ,
R1 1 ,
R2 1 ,
R3
1 ,
Rn 2 ,
R2 2 ,
R3
2 ,
Rn 3 ,
R3
3 ,
Rn
n
Rn, 1
,
R4 R4,2 R4,3 R4,3
4 ,
Rn
青い矢印、
赤い矢印の順番に 処理すれば大丈夫 キューにデータを
加えるときは、
何を、どういう順番で 行えば良い?
10/63
プログラムを書くときには...
プログラムを行うときに考えること...
データ構造:
目的を達成するためには、どのようなデータが必要 になるか。どのように保存したら良いか。
目的を達成するためには、何を行えばよいか。どの ような順番で行えばよいか。
結局の所、色々練習して、経験値を積むのが良いです 変数等の宣言に関係
処理の内容や順番等に関係
11/63
プログラミング
計算機とは
計算機は、ざっくりと言って、 CPU とメモリ、
入出力装置からなる。
CPU メモリ
入出力 装置
計算機
データを 保存する データを
処理する 外部と
データを
やりとりする
ビットとバイト
日常、人は、値(数)は10進数で、文字は文字として使 用している。
一方、計算機の内部では、すべてのデータは
0,1で管 理されている。
0,1しか取り扱うことができない!
また、計算機は、メモリにデータを蓄えている。
単位は、
bit
byte
1byte 1bitが8つ集まっている。
1bit 0
もしくは
1のどちらかを保存。
昔のプログラミング
0000 0001 0002 0003 0004
人間は、曰く
"人間語
"を話す。
計算機は
2進数しか理解できない!
昔は、人間が計算機に合わせて、2進数を話していた。
了解。
理解した。
計算機
処理
こういう処理 をやりたい
なぁ
人
10001001 01101010 10111010 11011011
上級言語
0000 0001 0002 0003 0004
人間は、2進数を会話するようにできていない!
人間が計算機に指示しやすく、つまり、プログラミング しやすくしたものが、上級言語。
了解。
理解した。
計算機
処理
こういう処理 をやりたい
なぁ
人
printf() get() put() while() 10001001
01101010 10111010 11011011
変換
16/63
種々の上級言語
色々な計算機言語があります。
C言語
:この演習であつかう言語
C++
:C言語の拡張として作られた
Java
:機種に非依存
BASIC
:昔は、パソコンで一番メジャーだった。
:構造化言語でなく、スパゲッティーなソースを
:書きがち。
forth
:基本的に、すべての命令はスタック操作命令
awkやperl
:スクリプト型の言語。手軽に書ける。
等々
他の文法の言語を勉強することは、理解や技量の幅が 広がる(と思います)
極端な話、単に
"既存のものを使うだけ
"なら、プログ ラミングを学ぶ必要は無いかもしれない。
何か、
"新しいものを作り上げる
"ことをやりたい場合、
計算機とプログラミングは、非常に強力なツールに!
プログラミングの目的
既存のものを使用する世界 新しいものを創造する世界 ソフト
知識 手法
ソフト 知識 手法
おわりに
Excelには様々な機能があります
が、それでもすべての処理をまかなえるわけではあり ません。
そのようなとき、Excelにはマクロ機能があります。