教科書："情報",川合慧(編),東京大学出版会

https://sites.google.com/site/iebtokyouniv/home/edu/information

(第1週) 情報学の考え方

「情報」の性質や表現について．表現，伝達，モデル化，問題解決，計算を概説する．

物理的な対象や事象ではなく，それらの持つ意味を扱うのが情報である．

何に着目し何を議論の対象としているかを常に考慮し，必要な部分だけを抽出(モデル化)して議論を行う．

(工場やプラントの時間当たりの出来高を知りたい→アローダイアグラムを作成する、など)

モデルに対して知りたい問題や解きたい問題があるとき、「解き方」もモデル化する必要がある。これをアルゴリズムと呼ぶ。

(アローダイアグラムからクリティカルパスを知る場合、各経路のコストを順次計算する、など)

また近年ではこれらをコンピュータで実現することが多いため、コンピュータや通信の実際についても概説する。

情報表現・ディジタル符号化

ディジタル量への変換(標本化、量子化)， 標本化定理，符号化，誤り検出．

アナログ信号 fc(t):R→R、デジタル信号 fd(k):T→Q

[標本化] fc(t)をある時間間隔ごとに抽出し時間tに関して離散化する作業。標本化後の信号はfs(k):T→R、Tは標本化された時間ステップ可算集合

[量子化] fs(k)の値を離散化する作業。量子化後の信号はfd(k):T→Q、Qは量子化された値のとる可算有限集合

[標本化定理] 元の信号fc(t)の最大周波数Wがわかっているとき、どの程度の標本化周期Tで標本化したらよいのか。

標本化周波数(1/T)が最大周波数の2倍(2W)よりも大きければよい。つまりT<=1/2W。

逆の言い方をすれば、標本化周期t0で標本化した信号は、1/2t0より大きな周波数の信号を復元できない。この上限周波数をナイキスト周波数と呼ぶ。

【宿題】

(任意の)エンジンのピストンの動きをハイスピードカメラで録画したい。

最大周波数の動きを失わないようデジタルビデオで録画する場合、標本化周期(サンプリング周期)を何秒にすればよいか。

また、1サンプリングにつき800[pixel]×600[pixel]のTrueColor画像(1pixelあたり24bit)の画像として保存すると仮定すると、

上の標本化周期で録画した1分間の動画は合計何Byteになるか。(ただし1Byte=8bitとする。)

(2週目) 情報表現・ディジタル符号化

[ハミング距離] 2つの符号において、各桁の符号が一致しているかどうかを比較した際の、一致しない桁の数。

2進符号(バイナリコード)は数値の差とハミング距離が一致せず、誤り訂正などの際に不都合がある。

グレイ符号(グレイコード)は数値の差が1の2コード間のハミング距離は1となり、

誤りが起こる可能性のある場合やコード間の類似度が重要な場合に利用される。

可逆圧縮・非可逆圧縮

[ハフマン符号化] 出現頻度の高い記号に短いビット列を割り当てる符号化。各記号の出現頻度が大きく異なる場合に有効。

[ランレングス圧縮] ビット列を各ビットの出現回数に置き換える符号化。連続して同じビットが現れる場合に有効。

tビット反転の起こる可能性のある通信路において、2つのビット列p,qのどちらかが送られたとき、

・受信したビット列から誤りの発生を検出できるための条件は、pとqのハミング距離がt+1以上であること

・受信したビット列から誤りを訂正できるための条件は、pとqのハミング距離が2t+1であること

ビット列の和が偶数になるように追加するビットを偶数パリティビットと呼び、パリティビットを付加した符号を単一パリティ検査符号と呼ぶ。

これにより、符号の全ビット和から1ビットの誤り検出が可能となる（実際、正しい符号間のハミング距離は2になっている）。

複数のパリティを追加することで誤り訂正も可能となる。

【宿題】

次のビット列 (モノクロ8×8ピクセルの画像を模したもの)

00000000 

00111100 

01000010 

00000010 

00011100 

00000010 

01000010 

00111100 

をランレングス圧縮し、圧縮前と後のビット長を比較せよ。（改行は無視し、1次元ビット列として扱ってよい）

できる限りビット長が短くなるように圧縮すること。

ビット列[01000101]と[01000111]の先頭に偶数パリティビットを追加せよ。

また、これら2つの単一パリティ検査符号間のハミング距離が2以上となり、1ビットの誤りを検出できることを示せ。

(3週目) 情報の伝達

情報量

受信前「出題範囲は日本史、東洋史、西洋史、アメリカ史のどれか」

↓メッセージ[世界史から出題]

受信後「出題範囲は東洋史、西洋史、アメリカ史のどれか」

受信前「出題範囲は日本史、東洋史、西洋史、アメリカ史のどれか」

↓メッセージ[日本史から出題]

受信後「出題範囲は日本史」

後者のメッセージの方が有益、メッセージの有益さを定量的に表したい→情報量

[受信後の場合数/受信前の場合数]の比で表現するとよさそう。

情報量の加法性が欲しい

（1つのメッセージAを受信した場合と2つのメッセージB,Cを受信したときの結果が同じならば、情報量(A)=情報量(B)+情報量(C)となってほしい）

以上から、情報量を対数 log_2(受信後の場合数/受信前の場合数) で定義

各メッセージの出現確率pがあらかじめ定義されているとき、情報量は log_2(1/p)=-log_2(p) で定義される。

平均情報量=Σ p log_2(p) はどのメッセージが送られてくるか、どの事象が発生するか全くわからない（確率に偏りがない場合）に最大となる

メッセージを伝達するには符号化が必要、符号長は短い方がいい

メッセージの符号長をlとするとき、平均符号長=Σ pl で定義される。平均符号長が短くなるような符号化を選ぶべき。

[情報源符号化定理] 平均情報量≦平均符号長 となることが知られている。等号が成り立つのは各メッセージの情報量=符号長となるとき。

【宿題】

メッセージ"優","良","可","不可"の生起確率がそれぞれ1/8,1/4,1/2,1/8であるとする。このときのメッセージ(集合)の平均情報量を求めよ。

また、平均符号長が最も小さくなるようにメッセージを符号化せよ。

暗号化方式，ネットワークトポロジー

共通鍵暗号

暗号化する側、復号する側で同じ鍵を利用する方式

共通鍵を知っている者は全員復号できるので、共通鍵の取り扱いに気を付ける

送信側 ｜ネットワーク ｜ 受信側

データ→[共通鍵:暗号化]→暗号化データ→｜→→→→→→→｜→暗号化データ→[共通鍵:復号]→データ

公開鍵暗号

暗号化する側は公開鍵、復号する側は秘密鍵を利用する方式

公開鍵と秘密鍵は1対になっており、ある公開鍵で暗号化したデータは対となる秘密鍵でしか複号できない

公開鍵では複号できないので、秘密鍵の取り扱いにのみ注意すればよい(秘密鍵はネットワークに晒さない)

送信側 ｜ネットワーク ｜ 受信側

データ→[公開鍵:暗号化]→暗号化データ→｜→→→→→→→｜→暗号化データ→[秘密鍵:復号]→データ

※厳密に言うと公開鍵を用いた復号は不可能なわけではなく、計算コストがかかるというだけである

※暗号化には素数の積計算と比較して巨大数の素因数分解が困難であることを利用したRSA暗号がよく用いられる

(RSA暗号)

素数{p,q}に対して、e*d=任意の自然数*[(p-1)(q-1)の最小公倍数]+1が成り立つようにe,dを選べば、

自然数 M<p*qに対して (M^e)^d ( mod (p*q) ) = M が成り立つことを利用した暗号方式。

公開される数n=p*qから素数{p,q}が推定されないように、素因数分解の困難な十分大きな素数を用いる。

ディジタル署名

データの改ざんを防ぐ等、データに対して(実世界の)署名を行う技術

作成者 ｜ネットワーク｜ 確認者

データ ｜→→→→→→｜ 受信データ

↓[ハッシュ関数]｜ ｜ ↓[ハッシュ関数]

指紋 ｜ ｜ 同一の指紋が計算されるか？を調べることでデータと署名の真偽を確認

↓[秘密鍵暗号化]｜ ｜ ↑[公開鍵複号]

署名 ｜→→→→→→｜ 受信署名

ネットワークトポロジー(通信機器の接続形態・構造)

(フル)メッシュ、リング、バス、スター、など

機器の物理的な接続形態を物理トポロジー、データの論理的な流れ構造を論理トポロジーと呼ぶ

例えばイーサネットでは、スター型物理トポロジーとバス型論理トポロジーを成す。

ネットワークの性能指標

レイテンシ：送信元のデータの送信(開始)から受信先での受信(開始)までにかかる時間 (単位はsecなど)

スループット：単位時間あたりに通信できるデータ量 (単位はbit/sなど)

【宿題】

(1) RSA暗号では（例えば）、平文Mを C = M^e mod n で暗号文Cへ暗号化し、暗号文Cを M' = C^d mod n で平文M’へ復号する。

（この例では暗号化に用いる{e,n}が公開鍵、復号に用いる{d}が秘密鍵である。）

ここで X mod n はXをnで割った余りを示す。

e=3,n=55,d=7であるとき、文字"!"(アスキーコード0x21,10進数標記で33)を暗号化および復号しながら公開鍵暗号方式を説明せよ。

(4週目) 情報通信

プロトコル(P.46)、インターネット，OSI参照モデル，TCP/IP

プロトコル

(通信)データ列の組立・解釈に関する決め事

(例) HTTP (hypertext transfer protocol)

クライアント ｜→[ GET http://www.google.com HTTP/2.0 ]→｜ サーバ

[WEBブラウザ]｜←[ HTTP/2.0 200 OK Date: Tue 以下本文 ]←｜ [WEBサーバソフトウェア]

それぞれの階層(物理、通信制御、アプリケーション、など)にそれぞれプロトコルがある

→OSI参照モデル

・アプリケーション層

具体的な通信サービスを提供する。HTTPなど。

・プレゼンテーション層

エンコード/デコード、暗号化、圧縮などを行う。

・セッション層

通信セッションの開始/終了、回復再開を扱う。

・トランスポート層

通信の管理や制御を行う。TCPやUDPなど。ポート番号(HTTPの場合は80番)はこのレイヤで管理される。

・ネットワーク層

通信の経路選択(ルーティング)や中継を行う。IPなど。

・データリンク層

フロー制御やデータの転送を行う。Ethernet(のデータリンク層)など。

・物理層

物理的な信号の受け渡しを行う。100BASE-T(有線、Ethernetの物理層)、IEEE802.11(無線)など。

[DNS (Domain Name Server)]

ホスト名(URL)とIPアドレスの関連付けを行うサーバ。ホスト名からIPアドレスを得ることを名前の解決と言う事がある。

ホスト名→IPアドレスの順引きとIPアドレス→ホスト名の逆引きが可能。

WEBブラウザがWEBサイトの内容をWEBサーバへ要求するときの流れ例

1) DNSへホスト名の解決を要求し、宛先IPアドレスを得る。

2) ブラウザが、宛先IPアドレスの対象TCPポート(HTTP80番)に対してHTTPの要求"GET url HTTP/1.1"を送ろうとする。

3) TCPがコネクションの確立を行う。データを適切なサイズに分割しTCPヘッダを付ける。

4) 宛先IPアドレスを基に、ネットワーク内のどのコンピュータにデータを転送するか決定する。

a) 宛先IPアドレスが自身が所属するネットワーク内のコンピュータのものである場合、そのコンピュータへデータを直接転送する。

b) 宛先IPアドレスが自身の所属するネットワーク外の場合、適切なルータを選択し、そのルータへデータを転送する。

これは、自身のIPアドレス(2進表記)とIPアドレス(2進表記)のうち、サブネットマスク(2進表記)が1ビットとなる桁を比較して、

一致しているかどうかを確認することで確かめられる。

※同一ネットワーク内のIPアドレスについて、先頭のIPアドレスをネットワークアドレス、最後のIPアドレスをブロードキャストアドレスと呼ぶ。

例えば、ネットワーク172.16.0.0/24については172.16.0.0はネットワークアドレス、172.16.0.255はブロードキャストアドレスとなる。

また、転送データには送信元や宛先のIPアドレスが含まれるIPヘッダがつけられる。

5) 上記のデータの転送を受けたルータは、4)と同一の作業を行う。宛先IPが同一ネットワーク内の場合、

IPアドレスからコンピュータの識別子となるMACアドレスを利用して宛先へデータを転送する(データリンク層、Ethernet)。

【宿題】

(1) TCPとUDPの違いを、それぞれどのようなデータの通信に適しているか例を挙げながら説明せよ。

(2) 192.168.1.0/26のネットワーク内で有効なIPアドレスの数（ホストアドレス数）はいくつか。また、このネットワークに対するネットワークアドレス・ブロードキャストアドレス・サブネットマスクを答えよ。

(5週目) データと計算の表現

データモデル，計算，プログラム

データをコンピュータで体系的に扱うためのモデル

[データモデルの例]

集合モデル・ネットワークモデル(グラフ)・階層モデル・関係モデル・論理モデル・オブジェクト指向モデル

【宿題】

授業で紹介した各データモデルについて、どのような場面で利用されているか具体例を調査せよ。

[計算モデルの例]

手続き型(C言語,pythonなど)・関数型(Haskel,LISPなど)・宣言型(論理型:prologなど)

プログラム言語と処理系

コンパイラ・インタプリタ・仮想機械

【宿題】

関数 f(n) = Π_{i=0}^{n}(1/i) = (1/1)*(1/2)*...*(1/n) を計算するプログラムを逐次処理および再帰処理の2通りで示せ。

(6週目) 計算方法

計算機で問題を解くために行うこと

(1) 問題をモデル化する

(2) 解き方(計算手法)を考察・モデル化する ※この「解き方」をアルゴリズムと呼ぶ

(3) プログラムとして実装する

同じ問題を解くアルゴリズムでも、繰り返し回数や手続きの量、計算にかかる時間が異なる可能性がある。

この大きさを計算量と呼び、最も支配的な部分で見積もる(オーダー)。記号O(・)を使うことが多い。

【宿題】

教科書中のフィボナッチ数を求めるアルゴリズム(アルゴリズム4およびアルゴリズム5)を実装し、

iが大きくなるにつれて計算時間に差が出ることを確認せよ。

可能であればそれぞれのアルゴリズムについて、計算量のオーダーと実際の計算時間が合致しているか考察せよ。

(7週目) コンピュータ

演算回路，メモリ，実際のコンピュータ

論理関数の完備性

加算器・負数の2の補数表現と減算器

フリップフロップ

【宿題】

(1) x-yを計算する4ビット減算器について、yが負の値の場合でも計算が機能するか確認せよ。

(2) (マスタスレーブ型)RSFFの問題として、禁止入力s=1,r=1がある。これを解決するため、s=1,r=1のときに保持状態の反転を行うMS-RSFF回路をNAND素子のみで実現せよ（教科書章末問題[7.4]の改変）

(8週目) 社会における情報システム

情報技術の社会的影響，問題，倫理

ユーザインタフェースの二重接面性、ユーザ行為の7段階モデル

情報技術によってもたらされたメリットと情報技術に固有の問題

【宿題】

情報に関わる近年の事件に対して、何が問題であったか、社会的および技術的に「何を」解決する必要があるのか論ぜよ。

問題の解決手法(どのように解決するか)は書かなくても良い。

A4用紙1~2枚程度、(1)事件の概要、(2)具体的に何が問題なのか、(3)何が原因で発生した事件であると考えられるか、(4)社会的および技術的に何を解決すれば事件が防げると考えられるか、を記述すること。