法政大学 情報科学部 2008年度「離散数学」講義資料

Slides:



Advertisements
Similar presentations
北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・2年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー.
Advertisements

組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
コンピュータプラクティ スⅠ 比較実験 水野嘉明. 本日の予定 計算量について 「比較実験」  パラメータを変化させての比較 ⇒ 実験1  二つのプログラムの比較 ⇒ 実験2  実験レポート R3として提出 2.
0章 数学基礎.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
計算の理論 I -言語とオートマトン- 月曜3校時 大月 美佳.
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
数当てゲーム (「誤り訂正符号」に関連した話題)
第12回 順序回路の解析方法 瀬戸 順序回路から,以下を導き、解析を行えるようにする タイムチャート 状態遷移関数・出力関数 状態遷移表
セキュアネットワーク符号化構成法に関する研究
Bipartite Permutation Graphの ランダム生成と列挙
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
プログラミング入門2 第4回 配列 for文 変数宣言 初期化
数理科学コース・ 倉田 和浩 2007/11/3 大学祭オープンラボ
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
Microsoft Excel 2010 を利用した 2項分布の確率計算
第四回 線形計画法(2) 混合最大値問題 山梨大学.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
Extremal Combinatrics Chapter 4
AllReduce アルゴリズムによる QR 分解の精度について
第2回 内容 ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照
確率・統計Ⅱ 第7回.
情報数理Ⅱ 平成27年9月30日 森田 彦.
香川大学工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之
1.コンピュータと情報処理 p.14 第1章第1節 1.わたしたちの生活と情報技術 情報機器の発展 情報機器は,アナログデータから
CSP記述によるモデル設計と ツールによる検証
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
離散数学I 第6回 茨城大学工学部 佐々木稔.
担当教員:蓮池 隆(はすいけ たかし) 技術社会システム 第5回:縮小・分割統治法 担当教員:蓮池 隆(はすいけ たかし)
地理情報システム論演習 地理情報システム論演習
栗原正純 UEC Tokyo 電気通信大学 情報通信工学科
Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
新しい表現を勉強しよう! × × a dog my dog a bed dog on the bed dog ○
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
新しいリソース グループまたはサブスクリプションへのリソースの移動 microsoft
問題1: ネットワークセグメントはいくつあるか?
栗原正純 UEC Tokyo 電気通信大学 電気通信学部 情報通信工学科 2009/4/15
第9回 優先度つき待ち行列,ヒープ,二分探索木
主成分分析 Principal Component Analysis PCA
ISBN-13 and ISBN /06/12 栗原正純 電気通信大学
25. Randomized Algorithms
プログラミング言語論 第10回 練習問題解答例 情報工学科 篠埜 功.
様々な情報源(4章).
1~15までの数字の中から、 1個の数字を選び、覚えて下さい。
4. システムの安定性.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
問題作成、解説担当:中島 副担当:坪坂、松本
データ解析 静岡大学工学部 安藤和敏
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第9回 優先度つき待ち行列,ヒープ,二分探索木
計算の理論 I -数学的概念と記法- 火曜 12:50~14:20 大月 美佳 2004年4月20日.
プログラミング入門2 第13回、14回 総合演習 情報工学科 篠埜 功.
情報の集約 記述統計 記述統計とは、収集したデータの分布を明らかにする事により、データの示す傾向や性質を要約することです。データを収集してもそこから情報を読み取らなければ意味はありません。特に膨大な量のデータになれば読みやすい形にまとめて要約する必要があります。
第14回 前半:ラムダ計算(演習付) 後半:小テスト
計算の理論 I -数学的概念と記法- 月曜3校時 大月 美佳.
香川大学創造工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学創造工学部 富永浩之
1~15までの数字の中から、 1個の数字を選び、覚えて下さい。
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
4.プッシュダウンオートマトンと 文脈自由文法の等価性
栗原正純 UEC Tokyo 電気通信大学 情報通信工学科 2007/5/2(修正2008/08/21)
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
ヒープソート.
情報数理Ⅱ 平成28年9月21日 森田 彦.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Microsoft Excel 2010 を利用した 2項分布の確率計算
プログラミング入門2 第5回 配列 変数宣言、初期化について
Presentation transcript:

法政大学 情報科学部 2008年度「離散数学」講義資料 法政大学 情報科学部 2008年度「離散数学」講義資料  栗原正純 電気通信大学 情報通信工学科 kuri@ice.uec.ac.jp (2008年11月29日) 2018/11/7

クイズ(その1) 「狼と山羊とキャベツの川渡り」 クイズ(その1) 「狼と山羊とキャベツの川渡り」 栗原正純 電気通信大学 情報通信工学科 (2007.6.4) (2008/11/28修正) 2018/11/7

男、狼、山羊、キャベツ 男 狼 山羊 キャベツ 2018/11/7

男、狼、山羊、キャベツ、船、川 船 川 2018/11/7

船に乗る組合せ 2018/11/7

男がそばにいないと食べ(食べられ)てしまう組合せと安全な組合せ 男がいなくても安全な組合せ 2018/11/7

左岸から右岸に渡りたい 2018/11/7

つまり、この状態にしたい 2018/11/7

問題 1/2 川の左岸から右岸へ、男が、自分自身以外に1つの荷物しか乗せられない船で、狼、山羊、キャベツを安全に運ぶには、どうしたらよいかを考えよう。 ただし、男が一緒にいないと、狼は山羊を食べてしまうし、山羊はキャベツを食べてしまう。 また、船が移動するときは、必ず、男が乗って運転する必要がある。 2018/11/7

問題 2/2 問1.どのような順番で運べばよいか、具体的な手順(方法)を示せ。 問2.少なくとも船を何回利用する必要があるかを示せ。すなわち、利用する最小回数を示せ。 問3.最小回数で実行できる手順は何通りあるかを示せ。また、その手順のすべてを示せ。 2018/11/7

それぞれを簡略しアルファベットで表す M Man 男 W Wolf 狼 G Goat 山羊 C Cabbage キャベツ 2018/11/7

組合せ(状態)の列挙 左岸 右岸 “1” いる “0” いない。“0”を省略。 各行には4個の1がたつ。 たとえば、 “1” いる “0” いない。“0”を省略。 各行には4個の1がたつ。 たとえば、 0: すべてが、左岸にいる状態。 1: 男のみが、右岸にいる状態。 2: 男とキャベツのみが、右岸にいる状態。 3: キャベツのみが右岸にある状態。 状態 2018/11/7

組合せ(状態)の列挙 左岸 右岸 状態 2018/11/7

安全性が確保される状態 左岸 右岸 状態 安全でない組合せ 2018/11/7

可能な状態遷移の表 状態 状態遷移 2018/11/7

グラフ表現(状態遷移図) 状態遷移 5 4 7 13 2 8 11 15 10 2018/11/7

手順(0 → 5 → 4 → 7 → 2 → 11 → 10 → 15) (状態) 1(0) ステップ1 2(5) ステップ2 3(4) ステップ3 4(7) ステップ4 5(2) ステップ5 6(11) ステップ6 7(10) ステップ7 8(15) 2018/11/7

行列表現 状態遷移 2018/11/7

行列   の一行目 2018/11/7

行列 のベキ乗計算の結果より ・状態0から状態15へのパスの本数を表す成分に、行列 の7乗 のときに初めて非ゼロ成分の2が出現した。 行列  のベキ乗計算の結果より ・状態0から状態15へのパスの本数を表す成分に、行列   の7乗   のときに初めて非ゼロ成分の2が出現した。 ・したがって、状態0から状態15への最短のパスの長さは7であり、その本数は2本であることが分かる。 2018/11/7

結論 問1の解答は、状態遷移図を表すグラフ表現の結果から得られる。 また、問題2,3の解答も、グラフ表現の結果から最小回数は7回であり、その手順は2通りある。手順は、問題1の解答と同様に、グラフ表現の状態遷移図から得られる。 行列表現およびそのベキ乗の結果からは、最小回数および最小回数を実現する手順が何通りあるかを計算で得られるという特徴があることが分かる。 具体的な手順を説明するには、グラフ表現を利用した方が分かりやすい。 2018/11/7

出題元 熊本県中数研のホームページ http://kumamoto.classmatch.org/dekiru/kawa/kawa.html クイズ (その2) 「犬とうさぎの川渡り」 出題元 熊本県中数研のホームページ http://kumamoto.classmatch.org/dekiru/kawa/kawa.html 栗原正純 電気通信大学 情報通信工学科 (2007.7.23) 2018/11/7

3匹の犬と、3匹のうさぎ 3匹の犬 3匹のうさぎ 2018/11/7

犬、うさぎ、船、川 船 川 2018/11/7

安全に船に乗れる組合せ 空の船はダメ 2018/11/7

安全な組合せ と 襲われてしまう組合せ (うさぎの数が犬の数より少ないと安全でない) 安全な組合せ と 襲われてしまう組合せ (うさぎの数が犬の数より少ないと安全でない) 1 2 3 4 5 2018/11/7

問題 1/2 3匹の犬と3匹のうさぎの全員が川の対岸に渡ろうとしています。 ボートには2匹しか乗れません。 犬はうさぎの数より多くなると、うさぎを襲います。 うさぎが安全に対岸に渡るためにはどのような手順で渡ればよいでしょうか。 ただし、条件として、ボートが川を渡る際には、だれも乗船しないことは許されない。すなわち、ボートが川を渡る際には、犬、うさぎのどちらか、又は両方が乗船していなければならないとする。 2018/11/7

問題 2/2 問1.どのような順番で運べばよいか、具体的な手順(方法)を示せ。 問2.少なくとも船を何回利用する必要があるかを示せ。すなわち、利用する最小回数を示せ。 問3.最小回数で実行できる手順を、すべて示せ。 2018/11/7