2016年 理工学部 シラバス - 数学科
設置情報
科目名 | アルゴリズム数理B | ||
---|---|---|---|
設置学科 | 数学科 | 学年 | 3年 |
担当者 | 今井 桂子 | 履修期 | 後期 |
単位 | 2 | 曜日時限 | 木曜2 |
校舎 | 駿河台 | 時間割CD | N42P |
クラス |
概要
学修到達目標 | グラフ・ネットワーク,計算幾何学のアルゴリズム設計を例に,効率のよいアルゴリズムを設計するための手法を学ぶ.また,構成したアルゴリズムをプログラムとして実現できる能力を養う. |
---|---|
授業形態及び 授業方法 |
板書およびスライドを用いて,講義形式で行う.講義中や宿題として演習問題を提示するので,それを解くことによって,講義内容を理解してほしい.また,実習を行うこともある. |
履修条件 | C言語とアルゴリズムの初歩を理解していること.「ソフトウェア概論A C言語プログラミング」,「ソフトウェア概論B C言語プログラミング」,「アルゴリズム数理A」を履修していることが望ましい. |
授業計画
第1回 | グラフ:定義,グラフ理論の基礎 |
---|---|
第2回 | 四色問題 |
第3回 | グラフのデータ構造 |
第4回 | グラフのデータ構造木:ヒープ,二分探索木 |
第5回 | グラフのアルゴリズム:連結性,探索 |
第6回 | ネットワークのアルゴリズム1:定義,最小全域木 |
第7回 | ネットワークのアルゴリズム2:最短経路問題 |
第8回 | ネットワークのアルゴリズム3:最大流 |
第9回 | 図形のデータ構造,線分の交差判定,多角形の面積,1次変換 |
第10回 | 凸包構成アルゴリズム:Graham のアルゴリズム |
第11回 | 平面の三角形分割 |
第12回 | Voronoi図とDelaunay三角形分割 |
第13回 | 凸多角形の三角形分割 |
第14回 | PとNP |
第15回 | 理解度確認のために平常試験及びその解説を実施する. |
その他
教科書 |
プリントを配布する予定.
|
---|---|
参考書 |
授業中に適宜提示する.
|
成績評価の方法 及び基準 |
授業中の提出物,レポート,小テストなどの提出状況および内容の評価(40%),平常試験成績の評価(60%) |
質問への対応 | 授業終了後に時間が許す限り,教室で質問を受け付ける.授業中も随時質問を受け付ける. |
研究室又は 連絡先 |
授業中に指示する. |
オフィスアワー | |
学生への メッセージ |
アルゴリズムを構成することやプログラミングすることは、人に分かりやすく解き方を説明することや数学の定理を証明をすることにつながります.論理的に効率よく問題を解く方法を考える思考力は,将来にわたって役に立つと思います. |