シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
グラフとネットワーク | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Graphs and Networks | ||
| 科目番号 /Code |
INS501c INS501d | ||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講学科・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
武永 康彦 | ||
| 居室 /Office |
西9-535 | ||
| 公開E-Mail |
takenaga@cs.uec.ac.jp | ||
| 授業関連Webページ /Course website |
なし | ||
| 更新日 /Last updated |
2020/03/02 14:44:02 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
グラフやネットワークの関する基本的な概念とそれらに関する性質、代表的な問題のアルゴリズムについて概説する。 グラフやネットワークに関する基本的概念を理解し、様々な問題をグラフを用いて表現できること、グラフやネットワークに関する簡単な証明を行うことができるようになることを目標とする。 |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
離散数学、プログラミング通論、アルゴリズム論第一 |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
オペレーションズ・リサーチ基礎 |
| 教科書等 /Course textbooks and materials |
参考書： R.J. ウィルソン (著)，西関隆夫，西関裕子 (訳), 「グラフ理論入門 原書第4版」, 近代科学社 惠羅博,土屋守正,「増補改訂版 グラフ理論」, 産業図書 藤重悟,「グラフ・ネットワーク・組合せ論」, 共立出版 繁野麻衣子, 「ネットワーク最適化とアルゴリズム」, 朝倉書店 他 |
| 授業内容と その進め方 /Course outline and weekly schedule |
(a)授業内容 第１回 グラフの基本概念 第２回 種々のグラフ、次数 第３回 道と閉路 第４回 周遊性 第５回 木 第６回 平面グラフ 第７回 前半のまとめ 第８回 連結性 第９回 グラフの彩色 第10回 彩色と独立集合 第11回 マッチング 第12回 辺彩色とマッチング 第13回 最大流とカット 第14回 最大流、様々なグラフ族 第15回 後半のまとめ (b)授業の進め方 講義形式で行う。演習問題を解かせることもある。 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
予習、復習を行い、課題を与えた場合はそれに取り組むこと。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
評価方法：主に中間試験、期末試験の成績に基づいて評価を行う。 レポートについても一部考慮する。 評価基準：達成目標を一定の水準以上満たすことを合格の基準とする。 |
| オフィスアワー： 授業相談 /Office hours |
なるべく講義終了後に講義室にて。 それ以外はメールでアポイントを取ること。 |
| 学生へのメッセージ /Message for students |
グラフ、ネットワークは情報科学の様々な分野で非常に大きな役割を果たしています。この分野の重要な概念を理解し、活用できるようになりましょう。 |
| その他 /Others |
なし |
| キーワード /Keyword(s) |
グラフ、ネットワーク、道、閉路、木、平面グラフ、彩色、辺彩色、マッチング、最大流 |