情報科学A(9月30日分)

情報科学A(9月30日分)
情報のデジタル化
アナログとデジタル
n 
アナログ
n 
n 
n 
n 
連続的な目盛りであらわす
正確な記録のためには、無限の精度が必要
複製の際に情報の劣化が発生
デジタル
n 
n 
離散的な目盛りであらわす
正確な複製が可能
n 
デジタルコンピュータ＝コンピュータ
n 
n 
n 
全ての情報をデジタルデータであらわす
コンピュータ内部では2進数
アナログコンピュータ
音とは？
n 
n 
n 
n 
空気の振動（粗密波）
音の振動を模式的に表現＝波形
空気の密なところ＝山
空気の粗なところ＝谷
サンプリング定理（標本化定理）
n 
周波数
n 
n 
量子化
n 
n 
Hz
データをある範囲の自
然数で表現
標本化
n 
n 
サンプリング
飛び飛びにデータを採
取
サンプリング定理
n 
n 
シャノンが証明（ナイキストが予想）
アナログ（連続）信号をサンプリングして信号に変換
するとき、その信号に含まれる最高の周波数の2倍
より高い周波数 でサンプリングすれば、完全に復
元することができる。 量子化
n 
n 
アナログデータ（連続量）を自然数などの離
散的な値で近似的に表すこと。
値をあらわすのに用いるビット数を量子化
ビット数と呼ぶ。
n 
これを増やして、離散値としてとりうる値の範囲
を広げると、量子化の精度が上がる。
n 
2進数の1桁：1ビット(bit)
n 
n 
n 
n 
n 
n 
n 
n 
1bit:2通り
2bit:4通り
8bit:256通り＝1バイト(byte)
10bit:1024通り
1024byte = 1Kbyte
1024Kbyte = 1Mbyte
1024Mbyte = 1Gbyte
1000byte = 1Kbyte
例えば、CD
n 
44.1KHzでサンプリング
n 
n 
n 
n 
n 
1秒間に44100回情報を採取
耳が聞こえる音は20KHzと言われている
電話：3.4KHz
ラジオ：8KHz
16ビットで量子化
n 
音の振幅を216=65536段階に分割して採取
標本化（画像の場合）
n 
n 
格子状に置かれた標本点のにおける濃
淡の平均値や最大値を利用する
標本点や小区画を画素またピクセル
モノクロ画像とカラー画像
解像度
n 
どこまで細かく画像をあらわすかの尺度
n 
n 
dpi = dots per inch
ppi = pixel per inch(Adobe的)
標本化
混色
赤(R)、緑(G)、青(B)
量子化
n 
n 
濃淡を離散的な値に変換する
画素値：量子化された濃淡の値
データの圧縮
n 
あるデータをそのデータの実質的な性質を保
ったまま、データ量を減らした別のデータに
変換すること
n 
n 
アナログの場合
n 
n 
帯域制限
デジタルの場合
n 
n 
高効率符号化、情報源符号化
情報を元の表現よりも少ないビット数で符号化する
可逆圧縮と非可逆圧縮
n 
可逆圧縮=完全に復元出来る
n 
n 
zip
非可逆圧縮＝完全には復元出来ない
n 
Jpeg,mp3
データの圧縮(jpeg)
299KB
166KB
データのコード（符号）化
n 
点字
n 
n 
n 
バーコード
n 
n 
黒いバーの集まりでデータを表現
QRコード
n 
n 
６個の点で文字を表現
1825年頃
黒い四角形の集まりでデータを表現
モールス符号
n 
n 
短点（・）と長点（ー）で文字を表現
1837年頃
点字
n 
n 
n 
ルイ・ブライユ(Louis Braille):1809-1852
2X3のマス内の凸点として、文字や記号
などをコード化する
64(=2X2X2X2X2X2)個の文字をコード化
することが出来る
○○
○○
○○
カ　キ　ク　ケ　コ　点字
母音（Ａ,Ｉ,Ｕ,Ｅ,Ｏ）
はまる憶え
n  ア　か,さ,た,な,は,ま
イ　ウ　エ　オ　行は、右下側の３
●○
●○
●●
●●
○●
○○
●○
○○
●○
●○
○○
○○
○○
○○
○○
つの点で子音（Ｋ,Ｓ,
Ｔ,Ｎ,Ｈ,Ｍ）を表わし
、母音と組み合わ
せる
n 
●○
○○
○●
●○
●○
○●
●●
○○
○●
●●
●○
○●
○●
●○
○●
サ　シ　ス　セ　ソ　●○
○●
○●
●○
●●
○●
●●
○●
○●
●●
●●
○●
○●
●●
○●
タ　チ　ツ　テ　ト　●○
○●
●○
●○
●●
●○
●●
○●
●○
●●
●●
●○
○●
●●
●○
ナ　ニ　ヌ　ネ　ノ　●○
○○
●○
●○
●○
●○
●●
○○
●○
●●
●○
●○
○●
●○
●○
ハ　ヒ　フ　ヘ　ホ　●○
○○
●●
●○
●○
●●
●●
○○
●●
●●
●○
●●
○●
●○
●●
マ　ミ　ム　メ　モ　●○
○●
●●
●○
●●
●●
●●
○●
●●
●●
●●
●●
○●
●●
●●
モールス符号
n 
n 
n 
A
D
G
J
M
P
S
V
Y
1844年にS. Morse(1791-1872)によって開発
トン（・）とツー（ー）の2つの長さの違う音の組み合わ
せで表現
文字の利用頻度を基礎にコードを決定
－・・ －－・ ・－－－ －－ ・－－・ ・・・ ・・・－ －・－－ ・－
6.3%
B
－・・・
3.1%
E
・
1.5%
H
・・・・
0.1%
K
1.9%
N
1.5%
Q
5.1%
T
0.8%
W
1.3%
Z
－・－ －・ －－・－ － ・－－ －－・・ C
10.2%
F
4.2%
I
0.5%
L
5.6%
O
0.1%
R
8.5%
U
1.4%
X
0.1%
空白
・・－・ ・・ ・－・・ －－－ ・－・ ・・－ －・・－ 1.1%
－・－・
2.3%
1.8%
5.7%
3.3%
6.1%
4.8%
2.1%
0.2%
20.3%
実はこんなところにも…
n 
n 
フィルムのパトローネ(DXコード)
銀色(1)と黒(0)のチェッカー模様（12個）
n 
n 
n 
24種類のあるフィルムの感度(5)
フィルムは何枚あるか(3)
ここはいつも銀色
フィルムの感度を表す
露光許容度(2)
1
7
2
8
3 4 5 6
9 10 11 12
露光許容度を
フィルムの枚数
表す
を表す
バーコード
n 
バーの長さ
n 
n 
n 
４種類の黒バー
n 
n 
n 
1倍,2倍,3倍,4倍
数字(0,1)の個数を表す
1の個数を表す
1ビット,2ビット,3ビット,4ビット
４種類の白バー(空白?)
n 
n 
0の個数を表す
1個,2個,3個,4個
QRコード
n 
バーコードを進化させたもの
n 
n 
縦、横方向に情報を持たせ、記憶できる情報量を
飛躍的に増加
特徴
n 
n 
n 
n 
記録データ容量：約7KB
省スペース
どの角度でも読み取りが出来る
汚れに強い
デジタル情報の圧縮
n 
n 
データの符号化を工夫して、通常よりも
少ないデータ量で表現する
可逆圧縮と非可逆圧縮
ハフマン符号化：出現頻度の多いものは少
ない情報で表す。モールス符号など
n  ランレングス圧縮：値とのその繰り返し回数
で情報をらわす。FAXなど
n  JPEG圧縮：画像データ
n 
情報科学での情報
n 
n 
不確かさを減らすもの
情報の伝達
“知識”の伝達
n  情報の量＝送り手の”知識”ー受け手の”知
識”
n 
知識の伝達＝不確かさの減少
＝予想の当たる”確率”の増加
情報のありがたさ
n 
n 
n 
情報のありがたさを測る量
ビット(bit)
1bitの情報
n 
n 
n 
硬貨の表が出るか裏が出るかを通報する
予想が当たる確率1/2(通報前)
予想が当たる確率1（通報後）
情報のありがたさ
n 
情報のありがたさ
(情報量)
− log2 (その情報を受け取る確率)
n 
“情報のありがたさ”の期待値
n 
n 
“情報のありがたさ”Xその情報を
n
もらう確率の合計
エントロピー
− ∑ pi log pi
i =1
エントロピー
n 
n 
n 
乱雑さの指標
不確かさの指標
エントロピー大
n 
n 
n 
平均的な“情報のありがたさ”大
通報される知識が“ありがたい”
送り手の知識が不確実
情報量の応用(例えば、パズル)
n 
n 
8個の玉がある。そのうち7個は重さが同
じで、1個だけ違う。そこで、天秤ばかりを
3回だけ使って、この1個を見つけて欲
しい。
8個の中の一つを通報する問題と考えら
れるから、1/8=1/(2x2x2)だから、情報量
は3bit。
答えを知らなければ
答えを知っていれば
情報量の応用（言語）
n 
n 
n 
n 
話し言葉と書き言葉
話し言葉の方が情報量が少ない
日本語の場合
書き言葉
n 
n 
n 
n 
ひらなが系77
当用漢字1850
エントロピー10.91ビット/記号
話し言葉
n 
n 
203記号
エントロピー7.66ビット/記号
1922個=1850+77
1
1 ⎞
1
1 ⎞
⎛
⎛
× ⎜ − log(
) ⎟ +
× ⎜ − log(
) ⎟ + • • •
1922 ⎝
1922 ⎠ 1922 ⎝
1922 ⎠
203個
1 ⎛
1 ⎞ 1 ⎛
1 ⎞
× ⎜ − log(
) ⎟ +
× ⎜ − log(
) ⎟ + • • •
203 ⎝
203 ⎠ 203 ⎝
203 ⎠
情報量の応用（言語）
n 
日本語、英語、中国語の情報量の観点から
の比較
日本語
英語
中国語
書き言葉
（ビット/記号）
10.91
6.17
12.20
話し言葉
（ビット/記号）
7.66
4.75
10.61
情報量の応用（言語）
n 
次のような原因でエントロピーはもう少し減る
n 
n 
n 
文字の偏り
単語
文法
unde?stand
情報理論
n 
n 
n 
n 
シャノン C. Shannon（1916-2001）
A Mathematical Theory of　Communication (1948)
情報理論の創始者
ブールの考えを電気回路に翻訳すること
も思いついた人の一人
n 
もう一人は中嶋章
計算可能性の理論
n 
n 
どんな問題が計算で解くことが出来るのか？
チャーチの提唱
n 
チューリング機械で計算できる問題が計算で解く
ことの出来る問題
アルゴリズム
n 
アルゴリズム(algorithm)
n 
n 
n 
n 
プログラム
n 
n 
問題の解法
計算のしかた
普通は終わりのある解法
アルゴリズムをコンピュータで実行できるよう
にしたもの
一つの問題にも解法はいろいろある
数字の並べ替え（その1）
n 
n 
大きさの順番に並ぶまで、デタラメに並び替える
O(n!)の計算時間がかかる
O(X2)
1200
1000
800
x*x+2*x+1
x*x
600
400
200
0
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
数字の並べ替え（その2）
13
4
4
13
4
12
4
4
12
12
4
12
12
8
12
13
8
8
6
8
6
13
6
8
8
6
13
6
この方法ではO(
n2)
11
9
3
7
くらい計算時間がか
1
11
9
3
7
かる
6
1
1
1
11
1
11
1
9
11
11
9
7
3
9
9
3
7
3
3
7
7
13
基準
数字の並べ替え（その3）
13
4
12
8
6
1
この方法では
12
8
6
1
O(n 3log4 n)くらい計
算時間がかかる
3
4
1
3
4
1
8
6
基準より小さい
6
8
11
9
3
7
11
9
13
7
12
11
9
13
7
12
11
9
13
7
基準より大きい
データの比較回数
9000
40000000
8000
35000000
7000
30000000
25000000
6000
1
2
8
16
32
1024
2048
4096
32
64
4
8
16
4
128
256
512
0
バブル
バブル
クイック
クイック
データ数
1
2
20000000
5000
15000000
4000
10000000
3000
5000000
2000
0
1000
64
128
最大公約数を求める(1)
n 
n 
n 
n 
共通の約数の中の最大のもの
1から順番に割り切れるかどうか
を調べる
最悪何回割り算を計算するか？
約2N回
小さい方
N
計算時間
10000 0.2X10-3秒
100万 0.02秒
1億
2秒
1兆
20秒
1京
5.55時間
最大公約数を求める(2)
xとyの最大公約数はx-yとyの最大公約数と同じ
n 
n 
ユークリッドの互除法
r←xをyで割ったときの余り
以下をr=0となるまで繰り返す
n 
1. 
2. 
n 
n 
3. 
xとyの最大公約数は、xをyで割った余りとyとの最大公約数
x←y,y←r
r←xをyで割ったときの余り
yが答え
最大公約数を求める
n 
n 
何回くらい割り算が必要か？
2logN+2回
N
1億
1兆
1京
単純な方法
2秒
20秒
5.55時間
1050
6.3X1034年 3.34X10-6秒
ユークリッドの互除法
0.56X10-6秒
0.82X10-6秒
1.08X10-6秒
実行時間の違い
n 
n 
アルゴリズムによって、実行時間が変わる
アルゴリズムの優劣
n 
n 
n 
実行時間が早い：優
実行時間が遅い:劣
計算量の理論
n 
n 
アルゴリズムを考え出したり、優劣の評価を行う
一番多く実行している部分の実行回数に注目
計算量の理論
n 
n 
計算の本質的な複雑さを探る
問題を解くための効率の良いアルゴリズム
n 
n 
n 
計算時間が多項式で限定されるようなアルゴリズム
log n, n, n log n, n2, n3, n4,…n100,…
計算量クラスP
n 
n 
効率良く解くことの出来る問題の集まり
P= Polynomial-time solvable
計算量の理論
n 
計算量クラスNP
n 
与えられた答えが問題の答えとして正しいかどうかを、効
率良く解くことの出来る問題
n 
n 
n 
n 
n 
答えの候補に対しては、正解かどうかを簡単にチェックできる
答えの候補を簡単に記述することができる
多くの組み合わせ最適化問題は、このクラスに属する問
題となっている
NP=Nondeterministic Polynomial-time solvable
例えば、ナンバープレート問題
n 
n 
2,4,1,6の数字を１回ずつ使って、四則演算だけで10にす
ることが出来るか？
N個の数字を１回ずつ使って、四則演算だけで10にする
ことが出来るか？
計算量の理論
12000000000
10000000000
8000000000
n^10
2^n
6000000000
4000000000
2000000000
0
1
2
3
4
5
6
7
8
9
10
1.4E+30
1.2E+30
1E+30
8E+29
n^10
2^n
6E+29
4E+29
2E+29
0
1
9
17 25 33 41 49 57 65 73 81 89 97
計算量の理論
計算不可能
計算可能
NPナンバープレート問題
巡回セールスマン問題
ナップザック詰め込み問題
P
ソーティング
線形計画法
計算量の理論
n 
多くの研究者は
P≠NP
だと信じている
NP完全性
ナンバープレート問題が効率良く解ければ、
全てのNP問題が効率良く解ける
n  P=NP?
n 
n 
P=NP問題
これが正しければ、一見解くのが面倒な問題
も効率良く解くことが出来る
n  これが間違いならば、多くの組み合わせ最適
化問題は効率良く解けない。
n 
暗号
n 
n 
n 
プライバシーを守るための暗号技術
暗号化：普通に書かれた情報（平文）を暗号
化する
復号化：暗号化された情報を普通に書かれた
情報（平文）に戻す
暗号
n 
秘密鍵方式（共通鍵方式）
n 
n 
n 
n 
送り手と受け手が同じ鍵を利用して暗号を利用する
例えば、アルファベットを一文字ずらして暗号化する
共通の鍵を奪ってしまえば簡単に暗号の解読（復号化）が出来る
公開鍵方式
n 
n 
n 
n 
暗号化するための鍵と復号化の鍵を別々にする
暗号化するための鍵だけを配ればよい
暗号化するための鍵だけでは、簡単に復号化することが出来な
い方法があるか？
これを実現するためにN≠NPが利用されている。
情報科学
n 
計算機科学(Computer Science)
n 
n 
n 
情報理論(Information theory)
n 
n 
n 
チューリング、フォンノイマンらが源流
コンピュータの発展とともに進歩
シャノンが源流
情報量を数学的に定義
制御理論(Cybernetics)
n 
n 
ウィーナーが源流
生物、社会、通信等の現象を制御系としてとらえる
プログラムを作る
n 
与えられた問題をいくつかのできるだけ独立な副問題に
分割する
n 
n 
副問題に一つ一つあたって別々に解く
n 
n 
n 
n 
これらの副問題が解けると仮定できれば、最初の問題に対する
概要が得られる
簡単なら、最終解を書く
難しければ、副問題にさらに副問題に分割する
あとに残った副問題がすべて簡単なものばかりになるま
で、この作業を繰り返す
副問題の最終解をすべて組み合わせれば、最初の問題
に対する答が完成!!
プログラムを作る
n 
n 
n 
自然言語（例えば、日本語）による文章化を行う
詳細化された文章に対応するプログラミング言語の
命令文で置き換える
すべての操作は、一連の操作か、反復か、あるい
は選択の組み合わせで書ける（構造化定理）
機械語
n 
コンピュータの中では、全ての情報が数字
（２進数）で表されている。
n 
n 
当然、プログラムも数字で表される
例えば、
n 
n 
n 
n 
+:70
-:75
*:85
データを読み込む:72
機械語
1番地にある数字と2番地
にある数字のかけ算を行
い、3番地にしまう。
85 1 2 3
主記憶
番地 内容
1
5
2
8
3
40
プログラミング言語とは
n 
n 
なるべく簡単にコンピュータに命令を出せ
るように
コンピュータが理解出来るような命令を作
るために、人工的に作られた言語
アセンブリ言語
n 
n 
85(*)の代わりに、mul(multiplyの略)など
と書けたら便利
データを記憶している場所も名前で書けた
ら便利
mul tanka suryo kingaku
もう少し人間にわかりやすく書け
ないか？
n 
Fortranが開発
n 
n 
n 
1954年にJ. W. Backusが開発
Kingaku = tanka * suryoなどと書ける
これをきっかけに色々なプログラミング言
語が作られる
Fortran
n 
n 
n 
Fortran = Formula Translator
1972年にISOがFORTRAN66を規格として
制定。その後も、改訂が繰り返される。
科学技術計算に向いているとされている
1から100までの和を計算する
10
sum=0
Do 10 I = 1,100
sum = sum + I
continue
Cobol
n 
n 
n 
n 
Common Business Oriented Language
CODASYL
英文に近い形でプログラムが書ける
事務計算向けとされている
1から100までの和を計算する
perform varifying i from 1 by 1 until i>100
compute summ = summ+I
End-perform
Pascal
n 
n 
1971年にN. Wirthにより開発される
プログラムをわかりやすくするための工夫
（構造化プログラミング）が取り入れられて
いる
1から100までの和を計算する
sum:=0
For i:=1 to 100 begin
sum := sum+i
end
BASIC
n 
n 
1964年にJ.G.Kemenyらによって開発
Beginner’s All-purpose Symbolic
Instruction Code
1から100までの和を計算する
10 let sum=0
20 for i=1 to 100
30  sum = sum+i
40 next i
C
n 
n 
n 
n 
1973年頃にD. Ritchieらが開発
UNIXというOSを開発するために作られた
色々な機種で利用できる（移植性が高い）、プログラ
ムが簡潔に書けるという特徴がある
C言語を拡張した拡張したC++も利用されている
1から100までの和を計算する
sum=0
for(i=1;i<=100;i++){
sum += i;
}
Java
n 
n 
n 
1995年にSun社から発表されたオブジェクト指
向型プログラミング言語で、Cに似ている
Webブラウザ上で動かすappletというプログラ
ムを作成できることが注目される
様々な機械で動く（移植性が高い）
1から100までの和を計算する
sum=0
for(i=1;i<=100;i++){
sum += i;
}
Lisp
n 
n 
n 
List Processor
1950年代後半に開発された関数型言語
人工知能向きと言われている
1から100までの和を計算する
(defun sum (n)
(if (zerop n)
0
(+ n (sum (- n 1)))))
(sum 100)
Prolog
n 
n 
n 
Programming in Logic
1973年にColmerauerらによって、自然言
語処理のために開発された論理型言語
人工知能向きと言われている
1から100までの和を計算する
sum(0,0).
sum(I,S) :I1 is I-1,
sum(I1,S1),
S is S1+I.
sum(100,S).
Prolog
n 
事実と規則から推論を行えるのが特徴
on(oyagame,kogame).
on(kogame,magogame).
on(magogame,himagogame).
above(X,Y) :- on(X,Y).
above(X,Y) :on(X,Y),
above(Y,Z).
?- above(oyagame,himagogame).
Yes
?- above(X,Y).
X = oyagame,Y=kogame.
X = kogame,Y = magogame
X = magogame,Y = himagogame
X = oyagame,Y=magogame
X = kogame,Y = himagogame
X = oyagame,Y = himagogame
プログラミング言語の分類
n 
n 
1980年の時点で200種類上のプログラミング言語が
利用されているといわれている
水準
n 
n 
n 
高水準：Fortran,C,Javaなど
低水準：機械語、アセンブリ言語
処理形態
n 
n 
n 
n 
手続き型言語:Fortran,Cobol,C,C++,Java
関数型言語:Lisp
論理型言語:Prolog
オブジェクト指向型言語:C++,Java,smalltalk
Forth系言語
n 
n 
n 
すべてのコマンド(WORD)は辞書で管理する
新たなコマンド(WORD)を自己定義して、これ
を辞書に登録して、機能を追加する
逆ポーランド記法
n 
n 
n 
10 + 20
10 20 +
10に 20を　足す
日本語によるプログラム例
午前？とは　←「午前？」の定義　時刻を得て　時が １２より 小さいこと。　メインとは
午前？
ならば　「おはよう」を
さもなければ
「こんにちは」を
つぎに
表示し　改行すること。　←「午前？」の引用
プログラミング処理系
n 
アセンブラ
n 
n 
コンパイラ
n 
n 
アセンブリ言語を機械語に翻訳
高水準言語を機械語に翻訳
インタプリタ
n 
プログラミング言語を逐次翻訳をしながら実行