2. 関係 五島 正裕.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

2015 年度 有限幾何学 期末試験 次の各問に答えよ.( (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい) (1) 有向閉路が存在しない位数 4 のトーナメントを描け. (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ. (3) グラフ.
逐次ソート 2011/05/16. ソート(sort) 順序集合の要素a 1 … a n の上下関係を整 える 一般的には、整数の集合 N を考えればよ い ソートの計算量が問題となる どのような入力に対し、どのようなアル ゴリズムが最適か?
0章 数学基礎.
      ベクトル空間   実数体 体:数の集合で四則がその中で行えるもの 例)有理数全体、実数全体、複素数全体 R:実数体     C:複素数体  ベクトル空間
凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
3.2.3~3.3 D3 川原 純.
情253 「ディジタルシステム設計 」 (3)Constellation3
・力のモーメント ・角運動量 ・力のモーメントと角運動量の関係
離散数学入門 (集合論、ベン図) 情報システム学科 中田豊久.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
Akio Arimoto March 7,2011 Seminar at Tokyo City University
ソフトウェア基礎科学 授業資料: 論理関係(logical relations)のお話
曲面上のグラフの彩色 ~種数の増加,面の制限及び局所平面性~
ファジィ論理と ファジィ構造モデリング 北海道工業大学 情報デザイン学科 三田村 保.
Extremal Combinatorics 14.1 ~ 14.2
Probabilistic Method.
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
Designs M1 後藤 順一.
情報工学概論 (アルゴリズムとデータ構造)
香川大学工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之
Probabilistic Method 6-3,4
8.Intersecting Families
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
離散数学I 第6回 茨城大学工学部 佐々木稔.
集団的意思決定支援法の実験環境に関する研究
Ver.2 再掲:講義資料の所在 (URL) 下のURLは「情報数学」シラバスの「履修上の注意」に掲載されています。
Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学
線形代数学 谷津 哲平 第1章 ベクトル 1.1 ベクトル空間 1.2 ベクトルの一次独立性 1.3 部分ベクトル空間
ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
3. 束 五島 正裕.
計算の理論 I -Myhill-Nerodeの定理 と最小化-
第二回 時制論理とリアルタイムリソース.
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
【第二講義】1次元非線形写像の不変集合とエントロピー
Basic Tools B4  八田 直樹.
1. 集合 五島 正裕.
関係 (relation) 集合Aの要素aとBの要素bとが、ある条件Rを満たすとき「Rの関係にある」といい、aRb と書く。
補遺:質問への解答(1) 順序対と非順序対(1回目の授業)
計算量理論 1. マトロイドと貪欲アルゴリズム 1. Matroids and the Greedy Algorithm
レポート提出者のリスト 次のURLに掲載 ~goto/infomath.html 学内のIPアドレスからのみ閲覧 ( )
計算の理論 I -Myhill-Nerodeの定理 と最小化-
第9回 優先度つき待ち行列,ヒープ,二分探索木
レポート提出者のリスト 次のURLに掲載 ~goto/infomath.html 学内のIPアドレスからのみ閲覧 ( )
2. 関係 五島 正裕.
離散数学 07. 木 五島.
計算の理論 II -講義内容説明と 基本事項確認ー
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
Ver.2 再掲:講義資料の所在 (URL) 後にレポートを回収した時に、提出者の学籍番号を、ここに掲載する予定です。
5 Recursions 朴大地.
2007年 4 月~7 月( 合計12回予定) 講義資料: 上田 和紀 原著 後藤 滋樹 三訂
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
コードクローン間の依存関係に基づく リファクタリング支援環境の実装
B03 量子論理回路の 最適化に関する研究 西野哲朗,垂井淳,太田和夫,國廣昇 電気通信大学 情報通信工学科.
第9回 優先度つき待ち行列,ヒープ,二分探索木
離散数学 06. グラフ 序論 五島.
情報の集約 記述統計 記述統計とは、収集したデータの分布を明らかにする事により、データの示す傾向や性質を要約することです。データを収集してもそこから情報を読み取らなければ意味はありません。特に膨大な量のデータになれば読みやすい形にまとめて要約する必要があります。
地理情報システム論(総)/ 国民経済計算論(商)
地理情報システム論 第4回 コンピュータシステムおける データ表現(2)
情報工学概論 (アルゴリズムとデータ構造)
矛盾した知識 デフォルト推論 仮説を用いた推論 準無矛盾推論 デフォルト規則 デフォルト理論の拡張 → デフォルト証明 シナリオ
香川大学創造工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学創造工学部 富永浩之
卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ~アルゴリズムの改良の考察と そのプログラム作成~
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
3 分散システムのフォールトトレランス 分散システム Distributed Systems
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
Presentation transcript:

2. 関係 五島 正裕

関係 関係: いくつかのものごとの間に成り立つか否かを云々 対象とするものごとの集合の直積集合の部分集合として定義

二項関係 (binary relation) 集合 X, Y の要素 x, y について,関係 R ⊂ X × Y が成り立つ x R y ⇔ (x, y) ∈ R 例) X = {0, 1, 2, 3, 4} Y = {2, 3, 5, 7, 11} x R y = 「x は y より 2 小さい」 R = {(0, 2), (1, 3), (3, 5)} X = Y の場合, R を「X の上の関係」という

多項間の関係 集合 X1, X2, ..., Xn について,x1, x2, ... , xn の間に 関係 R ⊂ X1× X2 × ... × Xn が成り立つ R(x1, x2, ... , xn) ⇔ (x1, x2, ... , xn) ∈ R

同値関係

同値関係 (equivalence relation) 反射的 (reflexive) x R x 対称的 (symmetric) x R y ⇒ y R x 推移的 (transitive) x R y and y R z ⇒ x R z 例) x = y 複素数の実部が同じ, 虚部が同じ, 原点からの距離が同じ, ... 同じ国の国民 (二重国籍がなければ)

同値関係の写像 X から Y への写像 f : X → Y があるとき x R y ⇔ f (x) = f (y) 例) f (x) = x mod 7

同値類 (equivalence class) R[x] = { y | x R y } ⊂ X x : 代表元 (representative) x R y ⇒ R[x] = R[y] ⇒ 同値類は代表元の選び方によらない 異なる同値類は共通要素を持たない 例) 偶数 奇数 7 で割った余りが同じ

類別 と 商集合 類別 (classification):元の集合 X をその同値類の直和に分割すること X1 ∪ X2 ∪ … ∪ Xn = X i ≠ j ならば Xi ∩ Xj = φ 商集合 (quotient set):類別の結果得られる部分集合の集合 X/R = {X1, X2, … , Xn}

同値関係の強弱 X の上のふたつの同値関係 R1, R2 について R1 は R2 より強い ⇔ R1 ⊂ R2 (より細かく類別) 例) modulo 21 の類別は, modulo 7 の類別より細かい

順序関係

順序関係 (order relation) 反射的 x R x 反対称的 x R y and y R x ⇒ x = y 推移的 x R y and y R z ⇒ x R z 例) 数の大小関係 集合の包含関係 ≦ で表すこともある

全順序 全順序 (total order), 線型順序 (linear order) すべての x, y ∈ X について x ≦ y または y ≦ x 例) 数の大小関係

半順序 半順序 (partial order) 全順序ではない一般の順序 半順序集合 (partially ordered set, po-set) 例) 集合 A = {a, b, c} の巾集合 2A の要素の包含関係 {a, b, c} {a, b} {c, a} {b, c} {a} {b} {c} {}

擬順序 (pseudo-order) 反射的, 推移的だが反対称的でないもの x R y かつ y R x かつ x ≠ y なる x, y が存在 例) x – y 平面上の点の原点からの距離

ハッセ (線) 図 (Hasse’s diagram) DAG (Directed Acyclic Graph) 推移律からわかる余分なarcの除去 平面グラフとは限らない ― 例: 3次元立方体 a b c d e f g h i j k l m n o X p

極大元,極小元 上 界,下 界 最大元,最小元 上 限,下 限

極大元/極小元 極大元 (maximal element)/極小元 (minimal element) x ∈ X に対し, x ≦ y かつ x ≠ y という y ∈ X が存在しないとき, x を X の極大元という

上界/下界 上界 (upper bound)/下界 (lower bound) 半順序 ≦ が定義されている集合 S の部分集合 X で、 任意の x ∈ X に対し x ≦ a であるような a ∈ S があるとき X は上に有界 a を X の上界という 例) { 0, 1, 2, 3, 4, 5, 6 } の部分集合 {1, 2, 4} の上界は 4, 5, 6 (π, ∞) は下に有界, 上に有界でない

最大元/最小元 最大元 (maximum)/最小元 (minimum) 上界/下界 a が X に属するとき,a を最大限/最小限という max(X)/min(X) 例) [0, π] の最大元は π (0, π) には π は属さないので,最大元はない 集合全体の最大元/最小元 (あれば) T: トップ / ⊥: ボトム

上限/下限 上限(supremum, minimum upper bound :最小上界) 下限(infimum, maximum lower bound :最大下界) 部分集合 X の上界/下界の集合の最小元/最大元を,上限/下限という sup(X), inf(X) 例) (0, π) の上限は π 上限, 下限は存在するとは限らない

実数 極小元 極大元 最小元 最大元 下限 上限 [0, 1] 下界 上界 下限 上限 (0, 1) 下界 上界

例題 部分集合 X の 極大元、極小元 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ X a b c d e f g h 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ a b c d e f g h i j k l m n o X p

答え 極大元:d, g;極小元:i, j 上界:b;下界: m, o, p X のどの要素 x についても x ≦ b m ≦ x, o ≦ x, p ≦ x 最大元 :なし;最小元:なし 上界,下界はいずれも X の元ではない 上限:b;下限:m 上界の集合 {b} の最小限は b 下界の集合 {m, o, p} の最大元は m a b c d e f g h i j k l m n o X p

例題 2 部分集合 X の 極大元、極小元 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ X a b c d e f g 上 界、下 界 最大元、最小元 上 限、下 限 をすべて挙げよ a b c d e f g h i j k l m n o X p