数理情報学3, 4 (柳浦)

• 注．必ず数理情報学3と4の両方を履修すること．
• 2023年度春1期 木曜日3, 4限(13:00–14:30, 14:45–16:15)
• 初回4月13日
• 講義室: 第4講義室(注． 第4講義室は情報学研究科棟1階にあります． 時間割にはSIS2とありますが変更しました． 初回使ったSIS5も今後は使いません)
• 担当教員: 柳浦睦憲
• 講義目的: グラフ理論は， 情報通信や最適化をはじめとする情報科学の諸分野における 基礎理論として広く応用されている． 本講義では，グラフに関するさまざまな基本概念を学び， グラフ理論における基礎的な問題を解決するアルゴリズムを修得することを目標とする．
• 授業内容:
  1. グラフとは何か: グラフの定義や基礎的な用語，および歴史的背景について概説する．
  2. 連結性: グラフの連結性と，それを判定するアルゴリズムについて解説する． 2連結性や強連結性についても言及する．
  3. 最短路問題: 最短路問題に対するダイクストラ法について解説する．
  4. 最小木問題: 最小木問題に対するプリム法とクラスカル法について解説する．
  5. 最大流問題: 最大流問題に対するフォード・ファルカーソン法について解説する．
• 期末試験: 期末試験を行うか期末レポート課題(オンラインで提出)を課すかのいずれかの予定です． どちらにするかについては，事態の推移を見て判断します．
• 単位取得基準: 主として期末試験または期末レポートのうち実施した方(以下「期末課題」と呼ぶ)の成績により評価するが， 演習課題を課した場合はそれらの成績も考慮して総合的に評価する． 期末課題の答案を提出しない者は「W (評価対象外)」(2019年度以前入学者は「欠席」)とする．
• 休講
• 諸連絡
• 参考書
  • 茨木, Cによるアルゴリズムとデータ構造, オーム社, 2014.
  • 滝根, 伊藤, 西尾, ネットワーク設計理論, 岩波講座インターネット, 5, 岩波書店, 2001.
  • R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
• 補足

柳浦のホームページ