数理情報学8 (柳浦)

• 2018年度後期 金曜日2限(10:30–12:00)
• 初回10月5日
• 講義室: 情報科学研究科棟第4講義室
• 担当教員: 柳浦睦憲
• 講義目的: グラフ理論は， 情報通信や最適化をはじめとする情報科学の諸分野における 基礎理論として広く応用されている． 本講義では，グラフに関するさまざまな基本概念を学び， グラフ理論における基礎的な問題を解決するアルゴリズムを修得することを目標とする．
• 授業内容:
  1. グラフとは何か: グラフの定義や基礎的な用語，および歴史的背景について概説する．
  2. 連結性: グラフの連結性と，それを判定するアルゴリズムについて解説する． 2連結性や強連結性についても言及する．
  3. 最短路問題: 最短路問題に対するダイクストラ法について解説する．
  4. 最小木問題: 最小木問題に対するプリム法とクラスカル法について解説する．
  5. 最大流問題: 最大流問題に対するフォード・ファルカーソン法について解説する．
• シラバスのページ
• 単位取得基準: 主として筆記試験の成績により評価するが， 演習・レポートを課した場合はそれらの成績も考慮して総合的に評価する． 期末試験を受験しない者は「欠席」とする．
• 期末試験: 試験期間中に実施予定． 手書きのノート持ち込み可． ノートの内容は問わない．
  1. コピーや印刷物は一切不可 （ノートに挟んだり貼り付けるのももちろん不可）． 手書き以外の資料を試験中に机の上や引き出しの中などに置いていた場合は， たとえ試験中にその資料を見ていなくても不正行為と見做す．
  2. ルーズリーフなど（2枚以上）は1冊にまとめること （リングファイル等で綴るかホッチキスで止めるなど）． 1冊にまとめていない2枚以上の資料を持ち込んだ場合は不正行為と見做す．
• 休講
  • 1月18日: センター試験前日のため
• 諸連絡
  • 1月の講義は1/11に開始，最終回は1/25の予定.
• 参考書
  • 茨木, Cによるアルゴリズムとデータ構造, オーム社, 2014.
  • 滝根, 伊藤, 西尾, ネットワーク設計理論, 岩波講座インターネット, 5, 岩波書店, 2001.
  • R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
• 補足
  • 用語「生成部分グラフ」について

柳浦のホームページ