コンピュータサイエンス入門第6回

情報量の計算方法と単位
情報量
コンピュータサイエンス入門
第６回
沖縄で雪が降った
宝くじで１等に当選
明日は講師急病で
休講です
＞北海道で雪が降った
＞宝くじで７等に当選
＞明日はいつもどおり
授業です
 log 2
log10 10
1
1
 log 2 10 
≒
≒ 3.32 （ビット）
10
log10 2
0.301
アナログ・ディジタル変換（Ａ/Ｄ変換）
標本化
量子化
（サンプリング）
 log 2 P( E )
今年は北海道で降雪
ビット（シャノン）
 log 2 1  0
（ビット）
今年は沖縄で降雪
 log 2
＞
情報量の計算方法と単位
宝くじで７等当選
情報量＝
1
  log 2 64 1  log 2 64  6
（ビット）
64
５分の曲を保存するのに何MB必要？
1秒に44100回
サンプリング周波数44.1KHz
ビット数／サンプル
量子化ビット数 16bit
⇔モノラル
ステレオ
宝くじで１等当選
 log 2
log 10
1
7
 log 2 107  7 10 ≒
≒ 23.26
7
10
log10 2
0.301
（ビット）
５分の曲を保存するのに何MB必要？約53MB
1秒に44100回
サンプリング周波数44.1KHz
ビット数／サンプル
量子化ビット数 16bit
⇔モノラル
ステレオ
符号化
ランレングス圧縮
文字コード
あ → 0001
→ 00001001
い → 0010
90
可逆圧縮
AAAAABBBBBAAACDD
→ 11111001
→
10101 →
113
→
A5B5A3C1D2
同じデータが連続するとき効果大
６
３
１
５
４
１
１
２
７
４
６
５
５
７
２
1
ハフマン符号
可逆圧縮
I␣am␣a␣man
I
␣
1110
1111
1100
1101
1110
1111
→
000 001 010 011 001 010 001 011 010 100
1110 10 0 110 10 0 10 110 0 1111
ISO7 (J I S7)
７ビット
p
r
S
c
s
¥
l
|
<
L
-
= M ] m }
.
> N ^ n
/
? O _ o
~
EBCDIC
８ビット
0 1 2 3 4 5 6 7 8 9 A B C D E F
0
1
2
3
␣
& /
|
<
= M ] m }
L
.
> N ^ n
/
? O _ o
1100
1101
1110
1111
~
８ビット全角１６ビット
0
1
2
3
␣
C
D
E
F
,
<
p
ーﾀ
!
1 A Q a q
ｱﾁ
“
2 B R b
0 @ P
`
r
ｲﾂ
S
c
s
ｳﾃ
¥
l
|
ｼﾌ
-
= M ] m }
ｽﾍ
.
> N ^ n
ｾﾎ
/
? O _ o
# 3 C
{
}
0
a
j
~
A
J
1
b
k
s
B K
S
c
l
t
C
T 3
L
UNICODE
L
~
* % @
(
)
_
‘
+
;
>
=
|
┐
?
“
‘
¡ ± Á Ñ á ñ
2 B R b
r
‚
’
¢
²
Â Ò â ò
3 C
c
s
ƒ
“
£
³
Ã Ó ã ó
l
| Œ œ ¬ ¼
S
,
<
-
= M ] m }
L
.
> N ^ n
/
? O _ o
~
Ž
Ì
Ü
ì
½
Í
Ý
í
ý
ž
® ¾
Î
Þ
î
þ
Ÿ
¯
Ï
ß
Ï
ÿ
¿
ü
８ビット全角１６ビット
41
54
30
エスケープ
シーケンス
42
30
26
47 2D
ｿﾏ
（UCS-2 , UCS-4）
２byte
４ｂｙｔｅ
2
0
1
2
3
ーﾀ
ﾐ
。ｱﾁﾑ
43
「ｲﾂﾒ
41
54
30
88 A4 94
4C
」ｳﾃﾓ
C
D
E
F
ﾔｼﾌﾜ
ｭｽﾍﾝ
半角未定義のコードを
全角の上位に使う
ョｾﾎ゛
ｯ
ｿﾏ
“
EUC （拡張UNIXコード）
８ビット全角１６ビット
0 1 2 3 4 5 6 7 8 9 A B C D E F
0
1
2
3
␣
0 @ P
‘
p
!
1 A Q a q
“
2 B R b
# 3 C
S
r
c
s
l
|
～
<
° À Ð à ð
p €
0 ～8 9 A B C D E F
1B 28 4A 43
1B 24
‘
1 A Q a q
シフトJIS
～
～
C
D
E
F
l
,
-
～
～
,
s
0 1 2 3 4 5 6 7 ～ B C～F
Q a q
R b
c
0 @ P
～
1100
1101
1110
1111
`
r
S
～
C
D
E
F
P
R b
ISO-2022-JIS
111
～
0
1
2
3
000
～
␣ 0 @
0000
! 1 A
0001
“ 2 B
0010
# 3 C
0011
p
～
n
100
110
‘
1111
～
I
011
10
P
Q a q
８ビット
～
0000
␣
0000
!
0001
“
0010
#
0011
～
→
010
出現数順に短いコード
を割り当てる
0
ISO-8859-1（Latin-1）
111
～
m
n
␣
m
001
７ビット
000
～
␣ 0 @
0000
! 1 A
0001
“ 2 B
0010
# 3 C
0011
～
a
a
000
ＡＳＣＩＩコード
C
D
E
F
コード配置に
自由度がある
,
<
-
= M ] m }
L
.
> N ^ n
/
? O _ o
~
文字一覧は多摩ソフトウエア有限会社様のサイトより http://www.tamasoft.co.jp/ja/general-info/unicode.html
2
述語論理
正規表現
動物（ｘ）「ｘは動物である」
死亡（ｘ）「ｘは死ぬ」
∀x（動物（ｘ）→死亡（ｘ））
動物（スカシカシパン）
死亡（スカシカシパン）
構文図式
＜数字＞：：＝ 0｜1｜2｜3｜…｜9
＜年２＞：：＝＜年号＞｜＜年２＞＜数字＞
M
T
S
H
＜年号＞：：＝M｜T｜S｜H
英小文字１文字、数字１文字
＜数字＞：：＝ 0｜1｜2｜3｜…｜9
a＊
＜年１＞：：＝＜年号＞＜数字＞＜数字＞
ａで始まる文字列
a??
ａで始まる３文字の文字列
＜年２＞：：＝＜年号＞｜＜年２＞＜数字＞
メタ言語・・・言語のルールを書くための言語
次の規則から生成可能な式は？
<式>::＝<変数>｜( <式>＋<式> )｜<式>＊<式>
<変数> ::＝A｜B｜C｜D
<式>::＝<変数>｜( <式>＋<式> )｜<式>＊<式>
<変数> ::＝A｜B｜C｜D
逆ポーランド表記法（後置表記法）で次の式は？
逆ポーランド表記法（後置表記法）で次の式は？
数字
逆ポーランド記法
１＋２
１２＋
１＋２＋３
１２＋３＋
（１
[a-z][0-9]
次の規則から生成可能な式は？
＜年号＞：：＝M｜T｜S｜H
BNF
）（
＋２ × ３＋４
EF－G÷CD－AB＋÷＋
EF－G÷CD－AB＋÷＋
）
１２＋３４＋×
3
逆ポーランド表記法（後置表記法）で次の式は？
245
状態遷移図
EF－G÷CD－AB＋÷ ＋
入出力
処理開始
実行可能
状態
時間切れ
待ち
状態
①
②
③
小 00
↑ 02
03
ＣＰＵ割当
実行
状態
逐次探索法
二分探索法
①
③
②
入出力
処理終了
00
02
03
最大比較回数
最大比較回数
log 2 n  1
↓
大ｎ
ｎ
n
計算量
アセンブリ言語
機械語（マシン語）
結果を出すまでの手順と繰り返しの最大数
二分探索法 log 2 n 
逐次探索法 n 
 
直径ｎの円を塗りつぶす手順  n
2
01001011
LD １，TEIHEN
１行づつ対応
11010110
MUL１，TAKASA
インタプリタ
0101010111110101
アセンブラ
翻訳
1 N = 3
翻訳
2 K = N + 10
実行
0101010101111101
アセンブルする
（翻訳する）
インタプリタ型言語
というソフトで
実行
というソフトで
0111110101010101
翻訳 3 PRINT "Hello"
実行
コンパイルの処理工程
機械語（マシン語）
1010111110001111
0101111001010101
0111101101010101
0111110101010101
コンパイラ言語
main(void){
printf("hello,world¥n");}
目的（オブジェクト）原始（ソース）プログラム
プログラム
コンパイルするコンパイラ
というソフトで
（翻訳する）
Int a; a = 5;
a = 10;
Int a; a = 5;
a = 10;
Int a; a = 5;
a = 10;
Int a; a = 5;
a = 10;
0111101101010101
0111110101010101
Windows
1010111110001111
0101011111110000
翻訳
MacOS
0011110101011110
1011111011110000
翻訳
Linux
1111010101111111
1010111110000000
翻訳
System.out.println
("Hello, world!");
CPUが違えば
機械語も違う
OSが違いを吸収するが
OS間でもコードが違う
4
手続き型言語
Windows
1010111110001111
0101011111110000
仮想 System.out.println
マシン ("Hello, world!");
#include <stdio.h>
仮想
マシン
int main(void)
{
printf("Hello, world!");
return 0;
}
MacOS
0011110101011110
1011111011110000
Linux
1111010101111111
1010111110000000
関数型言語
仮想
マシン
Dsfherimxqoqwe;w
e39234jdjdfnlsnjgef
中間コード
論理型言語
オブジェクト指向型言語
親子(舟,サザエ).
親子(サザエ,タラ).
?- 親子(舟,ｘ).
ｘ＝サザエ.
孫(_祖母,_孫) :親子(_祖母,A),
親子(A,_孫).
?- 孫(舟,Y).
Y＝タラ.
public class Hello {
public static void main
(String [] args) {
System.out.println
("Hello, world!");
}
}
(format t "Hello, World¥n")
(+ 10 20)
(setq a 999)
(+ a 1 20)
(setq b nil)
(if nil 0 1)
スクリプト言語
#!/usr/bin/perl
print "Hello, world!¥n";
print <<"_HTML_";
<body>Hello world</body>
_HTML_
マークアップ言語
<顧客>
<氏名>山田太郎</氏名>
<宛先>
<郵便番号>001-0001</郵便番号>
<住所>札幌市白石区菊水</住所>
</宛先>
</顧客>
5

Download Report