第4章 データ構造
p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題
p.82,83 [誤] セールスパーソン問題
 [正] 巡回セールスマン問題 (Travelling Salesman Problem)
「NP-困難」については 6.3.1計算量の階層 p.148~p.149 で解説。
1
1.3.2 モデル化
モデル化の例:マッカロック-ピッツの神経回
路網モデル (McCulloch-Pitts model)
– 神経回路網のモデル化---有限オートマト
ン理論の先駆け、論理関数の完全系をな
す、「有限オートマトンと等価」、
– 参考:甘利俊一「神経回路網の数理」産
業図書(昭和53年)
2
4.3 代表的なモデルと演算
1. 集合モデル
2. ネットワークモデル
・意味ネットワーク (skip可)
・実体関連モデル(ERモデル)(skip可)
3. 階層モデル(木構造)(オイラー図)
・ 階層的ファイルシステム
・ 日本の住所
・ 図書の分類 十進分類法(Dewey)
3
グラフとネットワーク
グラフは点(node) と辺(arc) からなる。もしくは頂点
(vertex) と枝(edge) からなるとも言う。
(ネットワークという言葉に正確な定義はなく、グラフ
の点や辺に属性がついていて、特にその上で最適
化問題を考えるような場合に使う。)
階層モデル(木構造)
1.親を持たない要素がただ一つある。これは根
(root) と呼ばれる。
2.根以外のすべては、ただ一つの親を持つ。
4
階層モデル (Hereditary Structure, Tree 構造)
の例
(a) 階層的ファイルシステム
UNIX のファイルシステム。(Windows ではドライブが最上
位の単位で、ルートディレクトリが存在しないので木構造と
は言えない。)
(b) 住所の階層構造、
(c) インターネットのドメイン名の階層構造---インターネットの
root は形式的に一意だが、実際には世界で3つの root
server が動いている。
5
UNIX の階層的ファイルシステム
/
home01/
g934213
home02/
ルートディレクトリ
Applications/
Library/
g93512
絶対パス名付きファイル名
/home02/g93512/first.html
ファイル1
ホームディレクトリ
ファイル2
HTML
first.html
ネットワーク上の最適化問題 (skip可)
1.最短路問題
2.ハミルトン閉路問題 (NP完全)
3.巡回セールスマン問題 (NP完全)
http://www.tsp.gatech.edu/
7
集合E上の関係Rの定義
・集合 Eの直積とは
E  E  (a, b) : a  E, b  E

・その部分集合 R  E  Eを関係と呼ぶ
例 E={a,b,c} R={(a,b),(b,c),(a,c)}
8
4.3.4 関係モデル
2項関係を多項(n項)関係に一般化して考
える
n項関係の定義 D  S1  S2      Sn
対象をn項関係の要素aとみなす
a  D  S1  S2      Sn
関係代数、関係論理への道を開く
9
例
N:名前の集合
S={男、女}性別
T: 電話番号の集合
この多項関係の要素のひとつ
a  N  S T
は、たとえば以下のようになる
a=(山田太郎、男、03-546-7890)
10
リレーショナルデータベース
• 関係の項目のひとつに識別番号を入れ
ると、冗長性がなくなる
正規化
• 関係を冗長性がなくなるように、複数の
関係に分解することを正規化という
番号 名前 所属
番号 名前 所属
g456 小泉 {15組,水泳部}
g456 小泉 15組
非正規型リレーション
g456 小泉 水泳部
正規型リレーション
11
表(クロステーブル)の直積
2つの表の直積の定義 
これを逆にもとの2つに分解すると、便利にな
る
吉田茂
自民党
マッカーサー 米陸軍
葉巻
ステーキ
吉田茂
吉田茂
自民党
自民党
葉巻
ステーキ
マッカーサー
米陸軍
葉巻
マッカーサー
米陸軍
ステーキ
注文主 品番
個数
小泉
安部
福田
ハ
イ
イ
9
3
5
麻生
ロ
5
品番
イ
ロ
品名
もりそば
カレーそば
単価
500
700
ハ
天ぷらそば
1000
ドメインが共通なもののすべて
の組合せを取る
自然結合
(ナチュラルジョイン)
注文主
品番
品名
個数
単価
小泉
ハ
天ぷらそば
9
1000
安部
イ
もりそば
3
500
福田
イ
もりそば
5
500
麻生
ロ
カレーそば
5
700
発注番号 取引ID 会社名
日付
品名
価格
492
a61
プラス
3/22
コピー紙
3500
492
a61
プラス
3/22
椅子
35000
492
a61
プラス
3/22
本棚
93000
492
a61
プラス
3/22
机
48000
494
c13
小泉商店
7/1
机
16800
494
c13
小泉商店
7/1
椅子
29800
494
c13
小泉商店
7/1
鉛筆
800
494
c13
小泉商店
7/1
消しゴム
第一正規形の例
30
• 主キーとは、データが一意に決まる属性値。
• 前の例では、発注番号と品名のペアが主キー
になっていて、あとはそれからきまる。この2つ
をあわせて複合キーという。
• 正規形への分割では、属性を1カ所変更して
も、他の属性値はそのままでよい。
• 記憶領域の無駄遣いをしないですむ。
15
発注番号 取引ID 会社名
492
a61
プラス
494
c13
小泉商店
発注番号
492
492
492
492
494
494
494
494
品名
コピー紙
椅子
本棚
机
机
椅子
鉛筆
消しゴム
日付
3/22
7/1
価格
3500
35000
93000
48000
16800
29800
800
30
リレーショナ
ルモデルにお
ける第2正規
形
ナチュラル
ジョインを取
ると元に戻る。
(ドメイン名が
共通な値を取
る全ての組
合せを作成
する。)
16
発注番号
取引 ID
日付
492
a61
3/22
494
c13
7/1
取引 ID
リレーショナルモデルに
おける第3正規形
会社名
a61
プラス
C13
小泉商店
発注番号
492
492
492
492
494
494
494
494
品名
コピー紙
椅子
本棚
机
机
椅子
鉛筆
消しゴム
価格
3500
35000
93000
48000
16800
29800
800
30
ダウンロード

第4章