到達目標
(ア)アルゴリズムの概念、計算量の概念を理解しており、O記法を使って計算量を表すことができる。
(イ)リスト構造を利用したデータ操作ができる。
(ウ)根つき木における基本操作ができる。
(エ)ハッシュの概念を理解しており、ハッシュ表を作成することができる。
(オ)グラフの表現方法とその特徴を理解している。
(カ)グラフの探索手順を説明することができる。
(キ)選択したデータ構造によってアルゴリズムが変化しうることを理解している。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 計算量の概念を理解しており、応用課題のアルゴリズムに対して、O記法を使って計算量を表すことができる。 | 計算量の概念を理解しており、例題のアルゴリズムに対して、O記法を使って計算量を表すことができる。 | 計算量の概念を理解しておらず、例題のアルゴリズムに対しても、O記法による計算量を表すことができない。 |
| リスト構造を利用した各種のデータ操作を説明することができる。さらに、根つき木を自由自在に辿る機能を実装することができる。 | リスト構造を利用した各種のデータ操作を説明することができる。 | リスト構造を利用した各種のデータ操作を説明することができない。 |
| グラフの表現方法（行列表現とリスト表現）ならびにそれぞれの長所・短所を説明できる。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを、データ構造の違いと関連づけて説明することができる。 | グラフの表現方法（行列表現とリスト表現）を説明できる。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを説明することができる。 | グラフの表現方法（行列表現とリスト表現）を説明できない。また、グラフ探索アルゴリズム（幅優先・深さ優先）の流れを説明することもできない。 |
学科の到達目標項目との関係
教育方法等
概要:
現代の情報化社会においては、大規模なコンピュータシステムを開発するためのソフトウェア技術が非常に重要な役割を果たしている。この技術の基盤となっているのが、情報数学をはじめとする計算機科学である。本講義では、効率的なシステム開発を行なう上で特に大切であると思われる数理的手法を取り上げ、わかりやすく解説する。
授業の進め方・方法:
授業の前半で、スライドを使って、基礎的な理論の説明をし、その後、後半の時間を使って、知識を確認し自分のものにするため、毎回演習を行なう。内容としては、「上級Ｃプログラミング A,B」で習ったデータ構造の基礎知識をさらに深めていくことを目指したテーマが多い。
注意点:
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
シラバスを用いた授業内容の説明、授業を受けるにあたっての心構え |
授業の進め方を理解し、半年後のゴールをイメージする。
|
| 2週 |
アルゴリズムの概念、計算量の概念、O記法による計算量の記述、オーダーを考えることの重要性 |
計算量の概念を理解し、演習を通して、その重要性を実感する。
|
| 3週 |
計算量の求め方、問題自体の計算量とは |
O記法を使って、各種のアルゴリズムの計算量を算出することができる。
|
| 4週 |
リスト構造とは、リスト構造におけるデータの追加・削除 |
リスト構造を説明できる。さらに、リスト構造における基本操作の手順を示すことができる。
|
| 5週 |
根つき木とは、根つき木を表すデータ構造 |
根つき木の定義を示すことができる。また、それを表す効果的なデータ構造を説明できる。
|
| 6週 |
根つき木のたどり方 |
根つき木を自由自在にたどるプログラムを作成することができる。
|
| 7週 |
2進木とは、2進木を利用したソート方法、平衡2進木とは |
２進木を利用したソートプログラムの処理の流れを説明することができる。
|
| 8週 |
ここまでの総復習 |
リスト構造・木構造を使った基本的なプログラムの処理の流れを説明できる。
|
| 2ndQ |
| 9週 |
ヒープとは、ヒープの作り方、ヒープソートのアルゴリズム |
ヒープを使ったソートアルゴリズムの流れを説明することができる。
|
| 10週 |
検索問題とは、2分探索アルゴリズム、ハッシュ法の考え方、ハッシュ表の作成 |
リストを使ったハッシュテーブルを作成することができる。
|
| 11週 |
開番地法によるハッシュ表の作成（線形探索法と二重ハッシュ法） |
開番地法によるハッシュテーブルを作成することができる。
|
| 12週 |
グラフとは、オイラーグラフの性質 |
グラフの定義を説明することができる。さらに、オイラーグラフの性質を説明することができる。
|
| 13週 |
グラフの表現方法（行列表現とリスト表現） |
グラフを表す２種類の方法を説明することができる。さらに、それぞれの特徴を示すことができる。
|
| 14週 |
グラフの探索（幅優先探索と深さ優先探索） |
２種類のグラフ探索アルゴリズムの動作の違いを説明することができる。
|
| 15週 |
分割統治法の概念とその適用例、マージソートのアルゴリズム |
分割統治法の概念を理解し、マージソートのアルゴリズムの流れを説明することができる。
|
| 16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
評価割合
| 中間試験 | 定期試験 | 合計 |
| 総合評価割合 | 40 | 60 | 100 |
| 専門的能力 | 40 | 60 | 100 |