シラバス参照

印刷
講義名 グラフ理論
代表ナンバリングコード BII3IT013C
講義開講時期 前期 講義区分 講義
基準単位数 2
受講定員の有無 なし
授業公開 科目等履修・聴講
履修年次 ３・４年次
2024年度カリキュラム　ナンバリング

担当教員
氏名
◎ 藤井　叙人

到達目標 グラフやネットワークの基礎と、代表的なアルゴリズムについて理解できる。
・各アルゴリズムの特長と利用目的を理解し説明できる。
・各アルゴリズムを実世界の問題に適用した事例について解説できる。
・グラフ理論を応用したシステム構築の概要設計ができる。
授業概要 グラフ理論は、頂点と辺で結ばれたグラフに関する理論であり、計算機で扱うデータ構造としても利用されている。コンピュータのネットワークのように、情報科学の様々な技術に応用されている重要な理論である。本講義では、グラフ理論の基礎から始め、最短経路問題や最大フロー問題、彩色問題などの概念と代表的なアルゴリズムについて説明する。理論の数学的な解釈や証明はほどほどにし、工学応用に重きを置いて応用事例を挙げながら解説する。
準備学習（予習・復習等）の内容とそれに必要な時間 （毎回の授業前に行うべき予習）
事前に公開（配布）する講義資料を予習。教科書の該当箇所の予習。

（毎回の授業終了後に行うべき復習）
講義資料の復習、課題レポートの作成。教科書の該当箇所の復習。

（その他）
「数学基礎Ⅱ」「線形代数」「線形計画法」で学習する知識が習得済みであることを推奨する。
評価方法（割合） 各授業における課題レポート（４０％）
期末試験（６０％）
課題（試験やレポート等）に対するフィードバックの方法 課題レポートの評価は適宜公開可とし、最終成績に反映する。期末試験の点数は採点終了後に公開可とする。
テキスト ※毎回の講義で資料を配布するが、より詳細を知りたい場合には以下の教科書を薦める。
【書名】グラフ理論入門
【著者】R.J.ウィルソン　訳：西関 隆夫、西関 裕子
【出版社】近代科学社
【出版年】2001



参考書・参考資料等 参考書が必要な場合は配布する講義資料で指示する。
メッセージ 　
教員との連絡方法 対面での面談は電子メールやSlack等で連絡をして日時調整をしてください。電子メールでの連絡は随時対応します。
備考 講義中、特段の理由がない限り私語、着帽、無断退室は慎むこと。常識的な範囲で飲料の持ち込みは可。携帯端末等は自己の責任において利用すること。授業計画の順序や学習内容の配分は変更の可能性がある。
他科目との関係性 【背景】本科目で学ぶグラフ構造とそれにかかわる諸問題の解決法が基礎理論として深く関わる科目である「プログラミング言語処理系」を学んでおきたい。
【関連】「コンピュータプログラミングⅡ」、「情報ネットワーク」、「人工知能」、「データマイニング」などで使われるので学んでおこう。「アルゴリズム論」ではグラフ理論の概念が使われている。
卒業認定・学位授与方針との関連
◎特に関係性が深い、○関係性が深い
関連性
情報学実践の基盤となる堅固な基礎学力、基礎技術力を持つ
○
地域の現実のデータを収集・分析し、地域社会の持続と発展のためのシナリオ作成と評価ができる
情報システムやアプリケーションの開発等により、地域社会を支える情報基盤を構築できる
◎
人工知能技術やエンタテインメント技術を用いて、地域社会を豊かにできる
情報学の知見や技術を応用・活用して、公共経営、企業経営、交流観光、医療福祉、防災等のまちづくりに貢献できる
評価基準
列1
秀
適切に問題点を指摘し、独自性のある現実的な解決策を論理的に提示できている。
優
指摘した問題点に対し、すぐれた解決策を論理的に提示できている。
良
指摘した問題点に対し、一応の解決策を提示できている。
可
問題点の指摘と解決策の提示が、いずれも最低限の水準を満たしている。
不可
問題点の指摘や解決策の提示ができていない。
放棄
出席回数が１０回に満たない。