早稲田大学 理工学術院 基幹理工学部 情報理工学科 後藤滋樹 情報通信を支える論理 早稲田大学　理工学術院 基幹理工学部　情報理工学科 後藤滋樹

本日の内容 情報の検索と論理記号 Googleのページランクと行列 イーサネットと多項式 いずれも実際の授業に基づいた内容です

情報の検索 最近の広告の仕方 検索サイト、検索エンジン http://www.yahoo.co.jp/ テクトロニクス 検索 検索サイト、検索エンジン http://www.yahoo.co.jp/ テクトロニクス 検索 http://www.google.co.jp/

能率の良い検索 キーワードを複数使う 情報理工学科 早稲田大学 情報理工学科 早稲田大学 AND 情報理工学科 ＡＮＤ の他に OR がある 早稲田大学 OR 情報理工学科 AND, OR の他にもある （Googleの例） すべてのキーワードを含む 　AND フレーズを含む （注：　語順を含めて一致） いずれかのキーワードを含む 　OR キーワードを含めない 　NOT

ベン図, 命題 Ｘ Ｙ X　ＡＮＤ　Ｙ

AND, OR, NOT は基本的な論理記号 論理回路（ろんりかいろ）は、ブール代数(論理演算)を行う回路、およびデジタル信号を記憶する回路。 (出典: フリー百科事典『ウィキペディア（Wikipedia）』) AND Ａ・Ｂ ＯＲ　Ａ＋Ｂ ＮＯＴ　Ａ 論理回路の設計をする技術者は、数学の論理演算記号とは違う記号を用いて論理式を記述することが多い。(同上）

半加算器の論理回路 ２進数の加算の演算 http://takaosuda.hp.infoseek.co.jp/homepage/electronics/circuit/calc02.html X（入力１） Y（入力２） S （和） C　（桁上がり） 1

検索結果の表示 順番を決める方法 ページランク

Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 基本的な仕組は数学的 グラフの行列による表現 　隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 S学部 C学科 G研究室 WEBページのリンクの関係 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

隣接行列を転置する 隣接行列　　　　　　　を転置する リンクを「出す」側から「受ける」側へ W大学 S学部 C学科 G研究室 WEBページのリンクの関係

隣接行列から推移確率行列へ 列(column)の総和が１または０になるように調整 ページの評価値をリンク先に渡す W大学 S学部 C学科 G研究室 WEBページのリンクの関係 １ 1/3

推移確率行列の固有値と固有ベクトル 固有値λと固有ベクトルｒ 行列 M を掛ける（乗算）ということは、グラフの 辺に沿って（確率的に）推移するということである 固有ベクトルの各要素は M を掛けても定数倍 しか変化しない。（安定している） 固有ベクトルの各要素がランクになる （ただし要素の和が１となるように正規化する）

固有ベクトルの具体例 GNU Octaveを使って計算する。固有値λ＝１が最大の固有値であり、固有ベクトルは下の左のようになる。 これを正規化したページランクは上の右である。 W大学 S学部 C学科 G研究室 １ 1/3 2/9 ページランクを記入した図 1/9

Googleにおける工夫 サイズの大きな 疎(sparse)行列の 固有ベクトルの計算 ユーザがランダムにページを渡り歩くと仮定 W大学 C学科 G研究室

Googleにおけるページランク 次の行列の固有ベクトルを求めて、要素の和が１になるように正規化する。 W大学 S学部 C学科 G研究室

より深く調べるために 本資料の例題は簡単にするために４つのサイトに閉じていた。 現実のPageRankは早稲田大学（8/10）、理工学部（6/10）、CS学科（5/10）、後藤研（4/10）。 次の資料が参考になる http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html 本資料は上記を参考にした。ただしOctaveのスクリプトは若干改良した。 Googleの創始者による論文も入手できる。 Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998, http://www-db.stanford.edu/~backrub/pageranksub.ps Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999, http://dbpubs.stanford.edu:8090/pub/1999-31

ネットワークの測定 オシロスコープ 電気信号を観測 アナライザ パケットを収集 通信

イーサネットの電気信号を観測 実験　　デジタル・ストレージ・オシロスコープ テクトロニクス

デジタル信号として解釈する

イーサネットのフレーム フレーム frame をパケット packet ともいう ２種類の標準 standard がある 先頭（ヘッダ）と末尾（トレーラ）にデータ以外の情報がある

イーサネットによる通信の基礎 Ver.2 FCS (Frame Check Sequence) 4オクテット 誤り検出のために使用。生成多項式は以下の通り。 受信側で同様のアルゴリズムによりCRC値を計算し、フレームチェックシーケンスの値と異なった 場合には、終端装置でフレーム誤りとして破棄。 「ワイドＬＡＮサービスのインタフェース 第1 版」 西日本電信電話株式会社 p.43 より引用

CRC (Cyclic Redundancy Check) 桁数が少ない例題 CRC (Cyclic Redundancy Check) 送信ビット列を多項式と見なしたものＰ(Ｘ)、生成多項式Ｇ(Ｘ)、生成多項式の最高次数をnとした時、 Ｐ(Ｘ)・Ｘn / Ｇ(Ｘ)　の余りをCRC符号とする。 【例】 送信ビット列 11001000 (Ｐ(Ｘ)＝Ｘ7＋Ｘ6＋Ｘ3) 生成多項式Ｇ(Ｘ)＝Ｘ6＋Ｘ2 Ｐ(Ｘ)・Ｘ6 / Ｇ(Ｘ) ＝ Ｘ7＋Ｘ6＋Ｘ2 　　　　　　　　　　余り Ｘ4 このとき、CRC符号は 010000 となる。 必ず5次以下になる 6ビットで表現可能 引用）　http://www.netlaputa.ne.jp/~hijk/study/nw/glossary.htm 　　　　　「ネットワーク・スペシャリスト・用語集」を一部修正して引用した。

イーサネットの CRC の計算法 CRC-32で33bitの定数ビット列から32bitのCRCを得る 実際の桁数 イーサネットの CRC の計算法 CRC-32で33bitの定数ビット列から32bitのCRCを得る ビット列– 100000100110000010001110110110111 生成多項式 (Generation Polynomial ) で書けば下記の通り 計算の手順 生成多項式を G(x) とする 送信するデータに32ビットの0をパディングして多項式表現したもの M(x) CRC値は割算 R(x) = M(x)÷G(x) の剰余である 送信するフレームは F(x) = M(x) + R(x) 誤りの検出 正しい受信データでは、F(x)がG(x)で割り切れる

まとめ 情報検索を論理的に効率化できる 論理回路は電子回路で実現されている 検索結果の順番はページランクによる 情報通信は数学的に構成されている