第４章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題 第４章　データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題  [正] 巡回セールスマン問題 (Travelling Salesman Problem) 「NP-困難」については 6.3.1計算量の階層 p.148～p.149 で解説。 1

1.3.2 モデル化 モデル化の例：マッカロック－ピッツの神経回路網モデル (McCulloch-Pitts model) 神経回路網のモデル化---有限オートマトン理論の先駆け、論理関数の完全系をなす、「有限オートマトンと等価」、 参考：甘利俊一「神経回路網の数理」産業図書(昭和５３年) 2

・意味ネットワーク (skip可） 4.3 代表的なモデルと演算 １. 集合モデル 2. ネットワークモデル ・実体関連モデル(ERモデル）(skip可） 3. 階層モデル（木構造）(オイラー図） 　　・ 階層的ファイルシステム ・ 日本の住所 　　・ 図書の分類 十進分類法(Dewey) 3

グラフとネットワーク 階層モデル（木構造） 親を持たない要素がただ一つある。これは根(root) と呼ばれる。 グラフは点(node) と辺(arc) からなる。もしくは頂点(vertex) と枝(edge) からなるとも言う。 (ネットワークという言葉に正確な定義はなく、グラフの点や辺に属性がついていて、特にその上で最適化問題を考えるような場合に使う。) 階層モデル（木構造） 親を持たない要素がただ一つある。これは根(root) と呼ばれる。 根以外のすべては、ただ一つの親を持つ。 4

b 有向グラフ G=(V,E) V={a,b,c,d} E={(a,b),(b,a).{a,c),(b,d)} a d c (a,b)=(b,a) b 無向グラフ G=(V,E) V={a,b,c,d} E={{a,b},{a,c},{b,c},{c,d}} a d c {a,b}={b,a}

グラフ　　2通りの呼び名があって統一されていない。 　(a)　点、ノード(node) と辺(arc) (b) 頂点 (vertex) と 枝 (edge) 有向グラフと無向グラフ 単にグラフと言ったときは普通、単純無向グラフを意味する。

階層モデル（hereditary structure, tree structure 木構造） 1) 親を持たない要素がただ一つある。これは根(root) と呼ばれる。 2) 根以外のすべては、ただ一つの親を持つ。 例 (a) 階層的ファイルシステム 　　UNIX のファイルシステム。（MS-Windows ではドライブが最上位の単位で、ルートディレクトリが存在しないので木構造とは言えない。） 住所の階層構造、 インターネットのドメイン名の階層構造---インターネットの root は形式的に一意だが、実際には世界で３つの root server が動いている。 7

UNIX の階層的ファイルシステム / 絶対パス名付きファイル名 ルートディレクトリ home01/ home02/ Applications/ Library/ g934213/ g93512/ 絶対パス名付きファイル名 /home02/g93512/HTML/first.html HTML/ ファイル1 ファイル2 first.html ホームディレクトリ

階層モデル 階層モデル(木構造) 生物の分類図のような，枝分かれの構造 有向グラフの特殊なもの，と見ることもできる 生物の分類図 ファイルシステム

関係の項目のひとつに識別番号を入れると、冗長性がなくなる 正規化 関係を冗長性がなくなるように、複数の関係に分解することを正規化という 4.3.4 リレーショナルデータベース 関係の項目のひとつに識別番号を入れると、冗長性がなくなる 正規化 関係を冗長性がなくなるように、複数の関係に分解することを正規化という 番号　 名前　 所属 g456 小泉 １5組 g456 小泉 水泳部 番号　 名前　 所属 g456 小泉 {１5組,水泳部｝ 非正規型リレーション 正規型リレーション 10

関係の項目のひとつに識別番号を入れると、冗長性がなくなる 正規化 関係を冗長性がなくなるように、複数の関係に分解することを正規化という 番号　 名前　 所属 g456 小泉 １5組 g456 小泉 水泳部 番号　 名前　 所属 g456 小泉 {１5組,水泳部｝ 非正規型リレーション 正規型リレーション 11

発注番号 取引ＩＤ 会社名 日付 品名 価格 492 a61 プラス 4/26 コピー紙 50 492 a61 プラス 4/26 椅子 65 発注番号 取引ＩＤ 会社名 　　日付 　 品名 価格 492 a61 プラス 4/26 コピー紙 50 492 a61 プラス 4/26　　椅子 65 492 a61 プラス 4/26 本棚 330 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 プラス 4/26 494 c13 小泉商店 7/1 リレーショナルモデルにおける第２正規形 ナチュラルジョインを取ると元に戻る。(ドメイン名が共通な値を取る全ての組合せを作成する。) 発注番号 品名 価格 492 コピー紙 50 492 椅子 65 492 本棚 330 492 机 148 494 机 168 494 椅子 98 494 鉛筆 15 494 消しゴム 3 14