シラバス詳細

シラバスカテゴリー
科目コード
学年
開講期間
開始時限
修了時限
大学
科目名
単位数
曜日
募集時期

離散数学基礎

開設大学 豊橋技術科学大学
科目コード 290403
担当教員 増山 繁
学年配当 1年, 2年, 3年, 4年
単位数 2単位
曜日 月曜
開講期間 後期
開講時間割1 4限 14:40 ~ 16:10
教室 F1-103
募集時期 9月
開講期間 10/16~2/19
講義概要 計算機を用いた問題解決の対象となるシステムの多くは、グラフ・ネットワークなどの離散構造をしている。そこで、離散構造を持つシステムをモデル化し、分析するツールとして、グラフ・ネットワーク理論を取り上げる。

1-3週目 数学的準備と離散数学の基礎概念(集合, 写像, 関数,数学的帰納法, 背理法,鳩の巣原理(ディリクレの抽出し論法))
4-6週目 グラフの基礎概念
・路,閉路,連結性
・木、カットセット
・オイラ-路、オイラ-閉路とハミルトン路、ハミルトン閉路
7-8週目 平面グラフと双対グラフ
9-10週目 ネットワーク設計とグラフの連結性
11-12週目 最短路問題入門
・動的計画法と最短路問題
・閉路がない場合
・ダイクストラ法
13-15週目 2部グラフのマッチング
・2部グラフのマッチングとは
・完全マッチング
・最大マッチング
16週目 定期試験
テキスト・参考文献 教科書: 講義内容を記したプリントを配布します。
試験・評価方法 期末試験・レポート(80%+20%)で評価する。

評価基準:原則的にすべての講義に出席したものにつき、下記のように成績を評価する。
S:達成目標をすべて達成しており,かつテスト・レポートの合計点(100点満点)が90点以上
 A:達成目標を80%達成しており,かつテスト・レポートの合計点(100点満点)が80点以上
 B:達成目標を70%達成しており,かつテスト・レポートの合計点(100点満点)が70点以上
 C:達成目標を60%達成しており,かつテスト・レポートの合計点(100点満点)が60点以上
別途必要な経費
その他特記事項 達成目標:
1. グラフ・ネットワーク理論の基本的な知識・理解を有すること
2. 最小木問題、最短路問題、最大流問題を解くアルゴリズムを使いこなせること
3. 離散構造を持つシステムのグラフ・ネットワークによるモデル化への理解を深めること
科目名(英語) Introduction to Discrete Mathematics
使用言語 日・英

pagetop