第４章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題

Presentation on theme: "第４章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題"— Presentation transcript:

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

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

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

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

5 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}

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

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

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

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

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

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

12 発注番号 取引ＩＤ 会社名 日付 品名 価格 492 a61 プラス 4/26 コピー紙 50 492 a61 プラス 4/26 椅子 65
発注番号 取引ＩＤ 会社名 　　日付 　 品名 価格 a プラス / コピー紙 a プラス /26　　椅子 a プラス / 本棚 a プラス / 机 c 小泉商店 7/ 机 c 小泉商店 7/ 椅子 c 小泉商店 7/ 鉛筆 c 小泉商店 7/ 消しゴム 第一正規形の例 12

13 主キーとは、データが一意に決まる属性値。
前の例では、発注番号と品名のペアが主キーになっていて、あとはそれからきまる。この２つをあわせて複合キーという。 正規形への分割では、属性を１カ所変更しても、他の属性値はそのままでしよい。 記憶領域の無駄遣いをしないですむ。 13

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