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