AJ161：情報数理C

AJ161：情報数理Ｃ
科目番号、科目名
AJ161、情報数理Ｃ（Information Theory C）
科目区分、必修・選択、授業の方法、単位数
専門基礎教育科目、選択、講義、2単位
履修年次、実施学期、曜時限、使用教室
2年次、1学期、火曜3限、520・521室
受講対象
システム工学専攻
担当教員（オフィスアワー）
新井孝昭（水曜12：00～12：30木曜17：30～19：30）
井上正之（月・水曜12:00～13:00、17:30～18:30）
授業における配慮
視覚的な教材を活用すると共に、例題を多く取り入れ理解を深める。
履修条件
数学に関する基本的な知識を有すること
学習に必要な知識・技能等
高等学校数学Ａ「集合と論理」
教科書・教材・参考文献・配布資料等
参考書：「プログラマの数学」(結城浩、ソフトバンククリエイティブ)
科目の到達目標
通信ネットワークに関わる情報処理技術において必要とされる数学的理論の説明ができるよう
になる。
通信システムにかかわる様々な問題をグラフ理論的・ネットワーク理論的問題としてモデル化
し，解くことができる。
単に問題の解き方を覚えるだけでなく，物事の本質を理解する。
学習の項目別目標
１．グラフの構造
点集合・枝集合からなるグラフの基本的定義が理解できる。
２．グラフ理論の基本的概念
パス・ループ・カットセット・木・双対性の概念が理解できる。
３．グラフのデータ構造
グラフを計算機で取り扱うためのデータ構造が理解できる。
４．グラフの基本算法
縦型探索・横型探索の基本的なグラフの探索手法が理解できる。
５．ネットワーク的手法
最小木問題・マッチング問題・最短路問題・最大流問題の定義と解き方が理解できる。
６．工学的応用
グラフ理論が通信網の信頼設計・インターネット経路設計・ナーススケジューリング等
の工学的問題に適用されることを理解できる。
授業概要
情報科学系やシステム工学系の後半以降の専門科目の修得に必要となる数学を学習する。また
知識を確実にし，応用力を高めるために演習を行う。
授業計画
第１回 ガイダンス、離散数学とは何か
キーワード
／ 離散数学、グラフ理論、一筆書き問題
予
習
／ 情報数理に興味を持って授業に臨む
復
習
／ ガイダンスと授業概要の把握
第２回 グラフの構造
キーワード
／ グラフ、点集合、枝集合
予
習
／ グラフの構造について（予習プリント）
復
習
／ グラフの構造の理解（次回確認テスト）
第３回 グラフ理論における基礎概念（１）パス・ループ・カットセット
キーワード
／ パス、ループ、カットセット
予
習
／ パス・ループ・カットセットとは（予習プリント）
復
習
／ パス・ループ・カットセットの理解（次回確認テスト）
第４回 グラフ構造における基本概念(2)木と双対性
キーワード
／ 木、双対性
予
習
／ 木とは（予習プリント）
復
習
／ 木と双対性の理解（次回確認テスト）
第５回 グラフ構造における基本概念(3)連結度と直径
キーワード
／ 連結度、直径
予
習
／ 連結度、直径とは（予習プリント）
復
習
／ 連結度、直径の理解（次回確認テスト）
第６回 グラフのデータ構造
キーワード
／ データ構造、接続行列、隣接行列、リスト
予
習
／ データ構造とは（予習プリント）
復
習
／ 接続行列、隣接行列、リストの理解（次回確認テスト）
第７回 グラフの基本算法(1)縦型探索
キーワード
／ 縦型探索
予
習
／ 縦型探索とは（予習プリント）
復
習
／ 縦型探索の理解（次回確認テスト）
第８回 グラフの基本算法(2)横型探索
キーワード
／ 横型探索
予
習
／ 横型探索とは（予習プリント）
復
習
／ 横型探索の理解（次回確認テスト）
第９回 ネットワーク的手法(1)最小木問題
キーワード
／ 最小木問題、貪欲算法
予
習
／ 最小木問題とは（予習プリント）
復
習
／ 貪欲算法の理解（次回確認テスト）
第１０回 ネットワーク的手法(2)マッチング問題
キーワード
／ マッチング問題
予
習
／ マッチング問題とは（予習プリント）
復
習
／ マッチング問題の解き方の理解（次回確認テスト）
第１１回 ネットワーク的手法(3)最短路問題
キーワード
／ 最短路問題
予
習
／ 最短路問題とは（予習プリント）
復
習
／ 最短路問題の解き方の理解（次回確認テスト）
第１２回 ネットワーク的手法(4)最大流問題
キーワード
／ ネットワーク的手法(4)最大流問題
予
習
／ 最大流問題とは（予習プリント）
復
習
／ ラべリング法の理解（次回確認テスト）
第１３回 通信網の信頼性評価への応用
キーワード
／ 信頼性
予
習
／ 信頼性とは（予習プリント）
復
習
／ 信頼性評価問題の解き方の理解（次回確認テスト）
第１４回 工学的応用（2）インターネットの経路設計への応用
キーワード
／ インターネット経路設計
予
習
／ インターネット経路設計とは（予習プリント）
復
習
／ インターネット経路設計問題の解き方の理解（次回確認テスト）
第１５回 工学的応用(3)ナース・スケジューリング問題への応用
キーワード
／ ナーススケジューリング問題
予
習
／ ナーススケジューリング問題とは（予習プリント）
復
習
／ ナーススケジューリング問題の解き方の理解
成績評価方法
期末試験 小テスト レポート
発表
作品
学習計画
その他
総合評価
60
30
知識
40
20
60
技能
10
5
15
応用
10
5
15
総
合
10
合計
100
力
指
標
表現
協調
意欲
10
10
*知識：知識を取り込む力
*技能：技能を習得する力
*応用：想起・解釈・問題解決能力、思考・推論・想像する力
*表現：プレゼンテーション力（提示・発表・伝達する能力）、コミュニケーション力（思考・感情を伝達する能力）
*協調：コラボレーション力（共同・協調する能力）、リーダーシップ力（統率力・指導力）
*意欲：自ら考え行動する力(学習に取り組む姿勢・意欲、チャレンジ精神、自己管理能力)
成績評価規準
知識 ／ グラフ理論の基本的な知識を正確に理解できる。
技能 ／ グラフ理論にかかわる基本的な計算ができる。
応用 ／ グラフ理論の基本的な知識を様々な問題に応用できる。
表現 ／ ―
協調 ／ ―
意欲 ／ 新しい知識を積極的に学ぶ意欲を持っている。
留意事項（受講生に望むこと、その他）
受け身にならず，式の意味や考え方を納得するまで考えることで，工学的に応用範囲の広いグ
ラフ理論・ネットワーク的アルゴリズムの手法をよく理解するように望みます。