到達目標
基本的なデータ構造であるリスト,スタック,キュー,ツリーなどの実現方法を解説する.続いて,これらデータ構造を使った探索方法とソートアルゴリズムについて学ぶ。具体的な学習到達目標は以下の通りである。
(1)アルゴリズムの概念を説明できるとともに、コンピュータ内部でデータを表現する方法にはバリエーションがあることを理解している。
(2)与えられたアルゴリズムが問題を解決していく過程を説明できるとともに、計算時間やデータ領域サイズによりアルゴリズムを比較・評価できることを理解している。
(3)同一の問題に対し、それを解決できる複数のアルゴリズムが存在し、選択したデータ構造によってアルゴリズムが変化しうることを理解している。
(4)整列、探索などの基本アルゴリズムをプログラムを説明できるとともに、リスト、スタック、キューなどの基本データ構造を使って表現したデータを操作するプログラムを理解している。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | び動的なメモリ確保を使ったリストにたいして挿入、削除のプログラムを書くことが出来る。 | び動的なメモリ確保を使ったリストにたいして挿入、削除のプログラムを資料を見ながら作成することが出来る。 | 動的なメモリ確保を使ったリスト構造によりデータを表現が理解できない |
評価項目2 | 線形探索及び二分探索のプログラムを作成し、計算量について説明できる。 | 線形探索及び二分探索のプログラムを資料を見ながら作成できる。 | 線形探索及び二分探索のアルゴリズムが理解できない。 |
評価項目3 | 力まかせ法、BM法を使った文字列検索のプログラムを書くことが出来る。 | 力まかせ法、BM法を使った文字列検索のプログラムを資料を見ながら書くことが出来る。 | 力まかせ法、BM法を使った文字列検索のアルゴリズムが理解できない。 |
評価項目4 | 各種ソート法、ハッシュ関数を使った複数リストを作成するプログラムを書くことが出来る。 | 各種ソート法、ハッシュ関数を使った複数リストを作成するプログラムを資料を見ながら書くことが出来る。 | 各種ソート法、ハッシュ関数を使った複数リストのアルゴリズムが理解できない。 |
学科の到達目標項目との関係
JABEE J(05)
説明
閉じる
本校 (1)-a
説明
閉じる
情報 (4)-a
説明
閉じる
教育方法等
概要:
基本的なデータ構造であるリスト,スタック,キュー,ツリーなどの実現方法を解説する.続いて,これらデータ構造を使った探索方法とソートアルゴリズムについて学ぶ、このアルゴリズムを実現するプログラムをC++言語で作成できるようにする。更に、各種アルゴリズムの計算時間に関しても理解できるようにする。
この科目は,企業にてICの論理回路設計とそのテスト工程に従事していた教員が,その時作成したテストプログラムのアルゴリズム,実行時間,実行コストなどの使用経験に基づき,プログラムのアルゴリズムと計算量の関係を講義形式で説明する。
授業の進め方・方法:
基本的な部分を講義で説明し、15回の自学自修時間にて配布するプリントを完成させて全てを提出することで理解を深める。
注意点:
(1)履修にはC言語によるプログラミング作成能力が不可欠になる。1~3年次にあった「プログラミング1,2,3」の単位は必ず取得しておくこと。
(2)授業は一方的な講義ではなく,学生への質問とそれに対する答えを参考に進める。この質問に対する返答内容も評価の対象になる。(3)授業時間割に組み込まれた自修時間と家庭学習(毎週、最低週2時間)を使って、自修時間に渡す課題プリントを完成させ、定期試験終了直後に提出すること。なお、一部の問題は実際にコンピュータ上で作成し、結果とともに決められた日時までに提出する必要がある(具体的な指示はその都度行う)。これらの学習状況及び提出状況を、提出物として評価する。
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
後期 |
3rdQ |
1週 |
シラバス説明とアルゴリズムと計算量~O記法 |
線形探索、2分探索の計算量を説明し、O記法を理解できる
|
2週 |
配列による順配と2分探索 |
配列データに対して2分探索プログラムを書くことが出来る
|
3週 |
ポインターによるリスト表現 |
自己参照型の構造体を用いてリストを作成し、要素を検索削除するプログラムを書くことが出来る
|
4週 |
ポインターポインターによるリスト表現 |
スタックに関する基本的さ操作をプログラムできポインター・ポインターを用いてリストを作成し、要素を検索削除するプログラムを書くことが出来る
|
5週 |
スタック
|
スタックに関する基本的さ操作をプログラムできる
|
6週 |
キューとリングバッファ
|
キューとリングバッファに関する基本的さ操作をプログラムできる
|
7週 |
ヒープツリー
|
配列を使ってヒープツリーを作成するプログラムをC++言語で書くことが出来る
|
8週 |
中間試験 |
1週から7週の内容を理解する。
|
4thQ |
9週 |
ツリ-1 |
2分木の表現と操作方法、数式を表す構文木を理解できる
|
10週 |
ツリ-2
|
2分木の操作を理解できる
|
11週 |
ハッシュ関数1 |
ハッシュ関数を使った複数リスト構造を理解できる
|
12週 |
ハッシュ関数2
|
ハッシュ関数を使った複数リスト構造をプログラムできる
|
13週 |
文字列の検索 |
力まかせの方法、BM法を使った文字列検索をプログラムできる
|
14週 |
ソート1
|
選択ソート、バブルソート、クイックソートの時間量をもともることが出来るとともに、プログラムを書くことが出来る
|
15週 |
ソート2
|
クイックソートの時間量をもともることが出来るとともに、プログラムを書くことが出来る
|
16週 |
|
|
評価割合
| 定期試験 | 提出物 | 授業参加度 | 合計 |
総合評価割合 | 60 | 30 | 10 | 100 |
基礎的能力 | 0 | 0 | 0 | 0 |
専門的能力 | 60 | 30 | 10 | 100 |
分野横断的能力 | 0 | 0 | 0 | 0 |