シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
グラフとネットワーク | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Graphs and Networks | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2016年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
情報理工学部 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
情報・通信工学科 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-mail |
okamotoy の後に @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/gn/ | ||
| 更新日 /Last update |
2016/03/15 10:40:20 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
主題：離散最適化の入門として，グラフとネットワークを用いた数理モデル化，および，アルゴリズム的解法の背後にある数理を概説する． キャッチフレーズは「本当の離散数学がここから始まる」． 達成目標：以下の4項目をすべて達成することを目標とする． (1) グラフやネットワークに関する用語を正しく使うことができる． (2) 現実世界の諸問題をグラフやネットワークで表現し，数理モデルを構築できる． (3) アルゴリズム的解法の背後にある数理，特に，最小最大定理の重要性を説明でき，それを用いて最適性の証明ができる． (4) グラフとネットワークに関する簡単な数学的事実を証明できる． |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，プログラミング通論 |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
なし |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書：指定しない．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： 藤重悟，「グラフ・ネットワーク・組合せ論」，共立出版，2002 繁野麻衣子，「ネットワーク最適化とアルゴリズム」，朝倉書店，2010 R.J. ウィルソン (著)，西関隆夫，西関裕子 (訳)，「グラフ理論入門 原書第4版」，近代科学社，2001． 他 |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
(a)授業内容 第１回 グラフの定義と次数：数理 第２回 道と閉路：数理 第３回 木：数理 第４回 マッチング：数理 第５回 マッチング：モデル化 第６回 最大流：数理 第７回 最大流：モデル化 (1) 第８回 最大流：モデル化 (2) 第９回 まとめ１ 第10回 連結性：数理とモデル化 第11回 彩色：数理 第12回 彩色：モデル化 第13回 平面グラフ：数理 第14回 平面グラフ：モデル化 第15回 まとめ２ (b)授業の進め方 はじめの75分に講義を行い，最後の15分で演習を行う． |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
演習問題を解き，レポートとして提出することを推奨する．(なお，レポートは成績評価に勘案されない．) |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
評価方法：中間試験と期末試験による．試験日程は講義中に連絡する． 評価基準：以下の到達レベルをもって合格の最低基準とする． (1) グラフやネットワークに関する用語を正しく使うことができる． (2) 現実世界の諸問題をグラフやネットワークで表現し，数理モデルを構築できる． (3) アルゴリズム的解法の背後にある数理，特に，最小最大定理の重要性を説明でき，それを用いて最適性の証明ができる． (4) グラフとネットワークに関する簡単な数学的事実を証明できる． ただし，用語を暗記する必要はない． |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
初回の講義で指示する |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
3年後学期に開講される「数理計画法」は本講義の内容と深く関係している． そのため，「数理計画法」を受講する予定の学生はこの講義も受講することが強く望まれる． また，3年前学期に開講される「アルゴリズム論第一」や「オートマトン理論」，さらに，3年後学期に開講される「アルゴリズム論第二」，「離散数理工学」，「計算理論」にも関わっているので，それらを受講する予定の学生もこの講義を受講することを推奨する． |
| その他 /Others |
情報・通信工学科で開講されていた「数理解析」を履修したものは，この科目を履修できないので，注意する． |
| キーワード /Keywords |
グラフ，ネットワーク，道，閉路，木，最大流，最小カット，マッチング，頂点被覆，連結度，彩色，染色数，クリーク，平面グラフ，平面的グラフ，オイラーの公式 |