第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 有向グラフ 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 は形式的に一意だが、実際には世界で3つの root server が動いている。 7 UNIX の階層的ファイルシステム / home01/ g934213/ home02/ ルートディレクトリ Applications/ Library/ g93512/ 絶対パス名付きファイル名 ファイル1 ホームディレクトリ ファイル2 HTML/ /home02/g93512/HTML/first. html first.html 階層モデル • 階層モデル(木構造) – 生物の分類図のような,枝分かれの構造 – 有向グラフの特殊なもの,と見ることもできる 生物の分類図 ファイルシステム 4.3.4 リレーショナルデータベース • 関係の項目のひとつに識別番号を入れ ると、冗長性がなくなる 正規化 • 関係を冗長性がなくなるように、複数の 関係に分解することを正規化という 番号 名前 所属 番号 名前 所属 g456 小泉 {15組,水泳部} g456 小泉 15組 非正規型リレーション g456 小泉 水泳部 正規型リレーション 10 識別番号 • 関係の項目のひとつに識別番号を入れ ると、冗長性がなくなる 正規化 • 関係を冗長性がなくなるように、複数の 関係に分解することを正規化という 番号 名前 所属 番号 名前 所属 g456 小泉 {15組,水泳部} g456 小泉 15組 非正規型リレーション g456 小泉 水泳部 正規型リレーション 11 発注番号 取引ID 会社名 日付 品名 価格 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 • 主キーとは、データが一意に決まる属性値。 • 前の例では、発注番号と品名のペアが主キー になっていて、あとはそれからきまる。この2つ をあわせて複合キーという。 • 正規形への分割では、属性を1カ所変更して も、他の属性値はそのままでしよい。 • 記憶領域の無駄遣いをしないですむ。 13 発注番号 取引ID 会社名 492 a61 プラス 494 c13 小泉商店 発注番号 492 492 492 492 494 494 494 494 品名 コピー紙 椅子 本棚 机 机 椅子 鉛筆 消しゴム 日付 4/26 7/1 価格 50 65 330 148 168 98 15 3 リレーショナ ルモデルにお ける第2正規 形 ナチュラル ジョインを取 ると元に戻る。 (ドメイン名が 共通な値を取 る全ての組 合せを作成 する。) 14
© Copyright 2024 ExpyDoc