第４章 データ構造
p.82 [誤] ハミルトニアン経路問題 [正] ハミルトン閉路問題
p.82,83 [誤] セールスパーソン問題
[正] 巡回セールスマン問題 (Travelling Salesman Problem)
「NP-困難」については 6.3.1計算量の階層 p.148～p.149 で解説。
1
1.3.2 モデル化
モデル化の例：マッカロック－ピッツの神経回
路網モデル (McCulloch-Pitts model)
– 神経回路網のモデル化---有限オートマト
ン理論の先駆け、論理関数の完全系をな
す、「有限オートマトンと等価」、
– 参考：甘利俊一「神経回路網の数理」産
業図書(昭和５３年)
2
4.3 代表的なモデルと演算
１. 集合モデル
2. ネットワークモデル
・意味ネットワーク (skip可）
・実体関連モデル(ERモデル）(skip可）
3. 階層モデル（木構造）(オイラー図）
・ 階層的ファイルシステム
・ 日本の住所
・ 図書の分類 十進分類法(Dewey)
3
グラフとネットワーク
グラフは点(node) と辺(arc) からなる。もしくは頂点
(vertex) と枝(edge) からなるとも言う。
(ネットワークという言葉に正確な定義はなく、グラフの点
や辺に属性がついていて、特にその上で最適化問題を
考えるような場合に使う。)
階層モデル（木構造）
1.親を持たない要素がただ一つある。これは
根(root) と呼ばれる。
2.根以外のすべては、ただ一つの親を持つ。
4
有向グラフ
G=(V,E)
V={a,b,c,d}
E={(a,b),(b,a).{a,c),(b,d)}
b
a
d
c
(a,b)=(b,a)
無向グラフ
G=(V,E)
V={a,b,c,d}
E={{a,b},{a,c},{b,c},{c,d}}
{a,b}={b,a}
b
a
c
d
• グラフ 2通りの呼び名があって統一されてい
ない。
(a) 点、ノード(node) と辺(arc)
(b) 頂点 (vertex) と 枝 (edge)
• 有向グラフと無向グラフ
単にグラフと言ったときは普通、単純無向グラフ
を意味する。
階層モデル（hereditary structure, tree structure 木構造）
1) 親を持たない要素がただ一つある。これは根(root) と呼ばれる。
2) 根以外のすべては、ただ一つの親を持つ。
例
(a) 階層的ファイルシステム
UNIX のファイルシステム。（MS-Windows ではドライブが最
上位の単位で、ルートディレクトリが存在しないので木構造
とは言えない。）
(b) 住所の階層構造、
(c) インターネットのドメイン名の階層構造---インターネットの
root は形式的に一意だが、実際には世界で３つの root
server が動いている。
7
UNIX の階層的ファイルシステム
/
home01/
g934213/
home02/
ルートディレクトリ
Applications/
Library/
g93512/
絶対パス名付きファイル名
ファイル1
ホームディレクトリ
ファイル2
HTML/
/home02/g93512/HTML/first.
html
first.html
階層モデル
• 階層モデル(木構造)
– 生物の分類図のような，枝分かれの構造
– 有向グラフの特殊なもの，と見ることもできる
生物の分類図
ファイルシステム
4.3.4 リレーショナルデータベース
• 関係の項目のひとつに識別番号を入れ
ると、冗長性がなくなる
正規化
• 関係を冗長性がなくなるように、複数の
関係に分解することを正規化という
番号 名前 所属
番号 名前 所属
g456 小泉 {１5組,水泳部｝
g456 小泉 １5組
非正規型リレーション
g456 小泉 水泳部
正規型リレーション
10
識別番号
• 関係の項目のひとつに識別番号を入れ
ると、冗長性がなくなる
正規化
• 関係を冗長性がなくなるように、複数の
関係に分解することを正規化という
番号 名前 所属
番号 名前 所属
g456 小泉 {１5組,水泳部｝
g456 小泉 １5組
非正規型リレーション
g456 小泉 水泳部
正規型リレーション
11
発注番号 取引ＩＤ 会社名
日付
品名
価格
492
a61
プラス
4/26
コピー紙
50
492
a61
プラス
4/26
椅子
65
492
a61
プラス
4/26
本棚
330
492
a61
プラス
4/26
机
148
494
c13
小泉商店
7/1
机
168
494
c13
小泉商店
7/1
椅子
98
494
c13
小泉商店
7/1
鉛筆
15
494
c13
小泉商店
7/1
消しゴム
第一正規形の例
3
12
• 主キーとは、データが一意に決まる属性値。
• 前の例では、発注番号と品名のペアが主キー
になっていて、あとはそれからきまる。この２つ
をあわせて複合キーという。
• 正規形への分割では、属性を１カ所変更して
も、他の属性値はそのままでしよい。
• 記憶領域の無駄遣いをしないですむ。
13
発注番号 取引ＩＤ 会社名
492
a61
プラス
494
c13
小泉商店
発注番号
492
492
492
492
494
494
494
494
品名
コピー紙
椅子
本棚
机
机
椅子
鉛筆
消しゴム
日付
4/26
7/1
価格
50
65
330
148
168
98
15
3
リレーショナ
ルモデルにお
ける第２正規
形
ナチュラル
ジョインを取
ると元に戻る。
(ドメイン名が
共通な値を取
る全ての組
合せを作成
する。)
14
© Copyright 2024 ExpyDoc
