到達目標
[1] 英文の専門書を読むことができる。
[2] グラフの基礎事項を説明できる。
[3] アルゴリズムの基礎事項を説明できる。
[4] 木の基礎事項を説明できる。
[5] グラフ探索アルゴリズムを説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1 | 辞書をほとんど使わずに英文の専門書を読むことができる。 | 辞書を使って英文の専門書を読むことができる。 | 英文の専門書を読むことができない。 |
| 評価項目2 | グラフの基礎事項を詳細に説明できる。 | グラフの基礎事項を説明できる。 | グラフの基礎事項を説明できない。 |
| 評価項目3 | アルゴリズムの基礎事項を詳細に説明できる。 | アルゴリズムの基礎事項を説明できる。 | アルゴリズムの基礎事項を説明できない。 |
| 評価項目4 | 木の基礎事項を詳細に説明できる。 | 木の基礎事項を説明できる。 | 木の基礎事項を説明できない。 |
| 評価項目5 | グラフ探索アルゴリズムを詳細に説明できる。 | グラフ探索アルゴリズムを説明できる。 | グラフ探索アルゴリズムを説明できない。 |
学科の到達目標項目との関係
教育方法等
概要:
グラフとグラフアルゴリズムの基礎を英文の専門書を使って学ぶ。
授業の進め方・方法:
英文の専門書を輪読する。1ページごとに教員、学生1、教員、学生2、... のように交互に和訳する。学生が和訳するとき、教員は適宜質問する。
注意点:
本科目は、授業で保証する学習時間と、予習・復習及び課題レポート作成に必要な標準的な自己学習時間の総計が、90時間に相当する学習内容である。
目標を達成するためには、講義以外に次の自己学習が必要である。
(1)次の講義で輪読する英文資料を読んでおく。
(2)2つの課題が課されるのでレポートを書く。レポートは和文でよい。
評価の対象としない欠席条件(割合) 1/3以上の欠課
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
グラフとは何か |
グラフの定義を説明できる。また、グラフが何をモデル化したものかを説明できる。
|
| 2週 |
頂点の次数、同型グラフ
|
頂点の次数に関連することがらと同型グラフについて説明できる。
|
| 3週 |
部分グラフ、次数列
|
部分グラフに関連することがらと次数列について説明できる。
|
| 4週 |
連結グラフ、切断点と切断辺
|
連結グラフに関連することがらと切断点、切断辺について説明できる。
|
| 5週 |
特別なグラフ
|
完全グラフ、二部グラフ、積グラフ、ハイパーキューブについて説明できる。
|
| 6週 |
有向グラフ
|
有向グラフに関連することがらを説明できる。
|
| 7週 |
アルゴリズムの計算量
|
アルゴリズムの計算量とオーダ表記法を説明できる。
|
| 8週 |
探索アルゴリズムとソートアルゴリズム
|
2分探索アルゴリズムとバブルソートについて説明できる。
|
| 2ndQ |
| 9週 |
NP完全の基礎
|
NP完全の基礎事項について説明できる。
|
| 10週 |
貪欲アルゴリズム、計算機におけるグラフの表し方
|
貪欲アルゴリズムについて説明できる。また、グラフの隣接行列と隣接リスト、スタック、キューを説明できる。
|
| 11週 |
木の性質
|
木の基本的な性質を説明できる。
|
| 12週 |
根付き木
|
根付き木に関連することがらを説明できる。
|
| 13週 |
深さ優先探索
|
深さ優先探索アルゴリズムについて説明できる。
|
| 14週 |
ブロックを見つけるアルゴリズム
|
ブロックを見つけるアルゴリズムを説明できる。
|
| 15週 |
幅優先探索
|
幅優先探索アルゴリズムについて説明できる。
|
| 16週 |
期末試験実施せず
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 輪読時の説明 | レポート | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 60 | 40 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 60 | 40 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |