科目名[英文名]
離散数学入門ｂ[Introduction to Discrete Mathematics b]
担当教員[ローマ字表記]
小原 功任
[
OHARA, Katsuyoshi
]
科目ナンバー
COMS2364A
科目ナンバリングとは
時間割番号
11064.001
科目区分
-----
講義形態
-----
開講学域等
理工学域
適正人数
「計算科学」または「計算機実験序論１」を履修済の受講生を優先します。
開講学期
Q4
曜日・時限
月2
単位数
1単位
授業形態
60単位上限
対象学生
-----
キーワード
[ハイフレックス授業型] グラフ理論, プログラミング
講義室情報
自然科学５号館Ｂ 大講義室
開放科目
-----
備考
EMI科目（英語で行われる授業科目）
授業の主題
計算数理の基礎分野の一つであるグラフ理論の基礎を学び、実際的問題を解決するアルゴリズムを習得する。
授業の目標
グラフ理論の基礎を学習する：構造をグラフで表現し、実際的問題を効率よく解くためのアルゴリズムをプログラミング実習を通して理解する。数学の問題解決に計算機は道具として有効であることを学び、実際に計算機実習を行い理解を深める。実習を行うことによって、与えられた課題に対して自ら考察し解決することを学ぶ。
学生の学修目標
グラフ理論の基礎を理解して実際的な問題を具体的にグラフで表現する技法を習得し、さらにプログラミング実習を通じて計算機を用いた数学の問題解決へのアプローチの手法を身につける。
授業概要
グラフの概念と基礎、グラフの基本的性質を学び、そのうえで各種のアルゴリズムを学ぶ。
さらには実際に計算機実習によってそのアルゴリズムを実装する。
1. グラフの連結度、辺連結度
2. プログラミング実習：グラフの連結度
3. 最短経路問題
4. プログラミング実習：ダイクストラの最短経路アルゴリズム
5. オイラー回路とその応用 (1)
6. オイラー回路とその応用 (2)
7. プログラミング実習：オイラー回路の発見
8. ハミルトン閉路
評価方法と割合
評価方法
次項の項目及び割合で総合評価し、次のとおり判定する。
「Ｓ（達成度90％～100％）」、「Ａ（同80％～90％未満）」、
「Ｂ（同70％～80％未満）」、「Ｃ（同60％～70％未満）」を合格とし、
「不可（同60％未満）」を不合格とする。（標準評価方法）
評価の割合
レポートもしくは試験による
授業時間外の学修に関する指示
予習に関する指示
予習に関する教材
復習に関する指示
学生は自宅での学習やプログラミング実習の時間を3時間確保することが期待される。
復習に関する教材
教科書・参考書
教科書
教科書
書名
情報科学のためのグラフ理論
ISBN
978-4254114249
著者名
加納幹雄著
出版社
朝倉書店
出版年
2001
教科書・参考書補足
オフィスアワー等（学生からの質問への対応方法等）
講義終了後
履修条件
CまたはFortranプログラムをコンパイルし実行できること。
また、そのプログラミング環境を自分のノートパソコンに持っていること。
適正人数
「計算科学」または「計算機実験序論１」を履修済の受講生を優先します。
その他履修上の注意事項や学習上の助言
理論と実践（プログラミング）の両方が求められる科目です。
どちらも手を動かして主体的に学んでください。
特記事項
カリキュラムの中の位置づけ
高校数学では学ばない種類の数学である「離散数学」への入門としてこの科目はある。
特記事項
講義は英語で行う。
ページの先頭へ