到達目標
1. アルゴリズムとデータ構造の概念を理解できる。
2. 時間計算量などによってアルゴリズムを比較・評価できることを理解できる。
3. リスト構造についてその概念と操作方法、表現方法、計算量を説明できる。
4. 木構造についてその概念と操作方法、表現方法、計算量を理説明きる。
5. 代表的なソートについてその概念と計算量を理解できる。
ルーブリック
| 優 | 良 | 可 | 要改善 |
| アルゴリズムの概念 | アルゴリズムの概念を説明できる。与えられた問題を抽象化しアルゴリズムを適用できる。問題を解決するための手段としてプログラムを用いたアルゴリズムを実装し解決することができる。 | アルゴリズムの概念を説明できる。与えられた問題を抽象化しアルゴリズムを適用できる。 | アルゴリズムの概念を説明できる。 | アルゴリズムの概念を説明できない。 |
| 計算量の理解 | 計算量とは何かを説明できる。各種アルゴリズムにおける計算量を把握することができる。プログラムの記述から必要な計算量を見積もることができる。 | 計算量とは何かを説明できる。各種アルゴリズムにおける計算量を把握することができる。 | 計算量とは何かを説明できる。 | 計算量とは何かを説明できない。 |
| データ構造 | データ構造の概念を説明できる。データの並び方からデータ構造を推測できる。問題解決のためにどのようなデータ構造を用いればよいか説明できる。プログラムを用いてデータ構造を実現できる。 | データ構造の概念を説明できる。データの並び方からデータ構造を推測できる。問題解決のためにどのようなデータ構造を用いればよいか説明できる。 | データ構造の概念を説明できる。 | データ構造の概念を説明できない。 |
| 集合 | 集合の様々な表現方法を説明できる。問題を解決するためにどのような表現を用いればよいのかを理解している。プログラムを用いて集合を実現できる。 | 集合の様々な表現方法を説明できる。問題を解決するためにどの表現を用いればよいのかを理解している。 | 集合の様々な表現方法を理解している。 | 集合の様々な表現方法を理解していない。 |
| 整列 | データを整列させるための様々なソートアルゴリズムを説明できる。データの並びに適したソートアルゴリズムを選択することができる。プログラムを用いてソートアルゴリズムを実装することができる。 | データを整列させるための様々なソートアルゴリズムを説明できる。 | データを整列させるための様々なソートアルゴリズムを理解している。 | データを整列させるための様々なソートアルゴリズムを理解していない。 |
学科の到達目標項目との関係
準学士課程の教育目標 A① 数学・物理・化学などの自然科学、情報技術に関する基礎を理解できる。
準学士課程の教育目標 B② 自主的・継続的な学習を通じて、専門工学の基礎科目に関する問題を解くことができる。
専攻科教育目標、JABEE学習教育到達目標 SA① 数学・物理・化学などの自然科学、情報技術に関する共通基礎を理解できる。
専攻科教育目標、JABEE学習教育到達目標 SB② 自主的・継続的な学習を通じて、専門工学の基礎科目に関する問題を解決できる。
教育方法等
概要:
本授業では、プログラムを作成する際、どのような処理が多く行われるかを判断し、空間・時間計算量を考慮して適切なデータ構造とアルゴリズムを考えることができるようになることを目的とする。授業ではプログラムを作るために理解しておかなければならないデータ構造とアルゴリズムについて、その特徴や利点を学ぶ。
授業の進め方・方法:
教科書を解説しながら演習を行いつつ、難題についてはグループでディスカッションし発表する場を設ける。また、理解を深めるために適宜問題演習を行い、アルゴリズムの実装法をプログラムによって理解する。授業の理解度やノートの取り方を確認しながら進めていくために毎回簡単な小テストを授業の終わりに実施する。この小テストは各自のノートを参照しながら解答してよい（カメラなどで撮影された画像は除く）。
注意点:
C 言語の知識が必須である。著しく授業を妨害する行為（騒音や授業の内容とは関係のない内容の雑談等）、小テストでの不正が観察された場合には教室から退室させ、その回の授業で行う小テストや質疑応答による評価は総合成績に加算しない。
[オフィスアワー]
水曜日15:30-17:00、金曜日13:00-17:00
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス |
授業の進め方の確認、評価方法について理解してもらう。
|
| 2週 |
アルゴリズムと計算量１ |
ユークリッドの互除法、線形探索、２分探索を理解するとともに、計算量について学ぶ。
|
| 3週 |
アルゴリズムと計算量２ |
ユークリッドの互除法、線形探索、２分探索をC言語プログラミングで実装してみる。
|
| 4週 |
データ構造１ |
配列とリストの違い、スタックと待ち行列の違い、循環配列、木について概念を理解する。
|
| 5週 |
データ構造２ |
配列、リスト、スタック、待ち行列、循環配列、木をC言語プログラミングで実装してみる。
|
| 6週 |
集合の表現法１ |
ヒープ、２分探索木、2-3木による平衡木の実現について概念を理解する。
|
| 7週 |
集合の表現法２ |
ヒープ、２分探索木、2-3木による平衡木の実現についてプログラミングによる実装を行う。
|
| 8週 |
中間試験 |
|
| 2ndQ |
| 9週 |
集合の表現法３ |
ハッシュ（チェイン法と開番地法）、集合群について概念を学ぶ
|
| 10週 |
集合の表現法４ |
ハッシュ（チェイン法と開番地法）、集合群についてプログラミングによる実装を行う。
|
| 11週 |
整列１ |
バブルソート、クイックソート、マージソートについて概念を学ぶ
|
| 12週 |
整列２ |
バブルソート、クイックソート、マージソートについてプログラミングによる実装を行う。
|
| 13週 |
整列３ |
ヒープソート、バケットソート、基数ソートについて概念を学ぶ。
|
| 14週 |
整列３ |
ヒープソート、バケットソート、基数ソートについてプログラミングによる実装を行う。
|
| 15週 |
プログラミング |
アルゴリズムとデータ構造の実装に必要なプログラミングについて学ぶ
|
| 16週 |
定期試験 |
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 変数とデータ型の概念を説明できる。 | 4 | 前15 |
| 代入や演算子の概念を理解し、式を記述できる。 | 3 | 前15 |
| 制御構造の概念を理解し、条件分岐や反復処理を記述できる。 | 3 | 前15 |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | 前15 |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | 前1,前15 |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 2 | |
| 主要な言語処理プロセッサの種類と特徴を説明できる。 | 2 | |
| ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 2 | 前1,前15 |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | 前2,前3 |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | 前2,前3 |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | 前2,前3 |
| 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 3 | 前2,前3 |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | 前11,前12,前13,前14 |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 3 | 前4,前5,前6,前7,前9,前10 |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 3 | 前4,前5,前6,前7,前9,前10 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 3 | 前4,前5,前6,前7,前9,前10 |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 3 | 前2,前3,前4,前7 |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 3 | 前2,前3,前5,前7 |
評価割合
| 定期試験 | 小テスト | 質疑応答 | 取り組み姿勢 | 合計 |
| 総合評価割合 | 60 | 40 | 0 | 0 | 100 |
| 基礎的能力 | 40 | 30 | ±5 | ±40 | 70 |
| 専門的能力 | 15 | 5 | 0 | 0 | 20 |
| 分野横断的能力 | 5 | 5 | 0 | 0 | 10 |