到達目標
各種アルゴリズムの計算量を計算できること,数値計算の誤差要因について説明できること,学習したアルゴリズムをC言語で実装できることで,学習・教育目標(D-1)および(D-2)の達成とする.
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
理論 | 各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができ,計算量の削減や計算誤差の縮小について述べることができる. | 各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができる. | 各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができない. |
実装 | 学習したアルゴリズムのC言語による実装ができ,高速化などの工夫を盛り込める. | 学習したアルゴリズムのC言語による実装が概ねできる. | 学習したアルゴリズムのC言語による実装ができない. |
学科の到達目標項目との関係
(D-1)
説明
閉じる
(D-2)
説明
閉じる
教育方法等
概要:
優れたプログラムを作成するうえで必須の知識であるアルゴリズムとデータ構造について,計算量を中心にその基本概念を学習する.学習したアルゴリズムを実際にC言語により実装する.
授業の進め方・方法:
・授業方法は演習を中心とする.
・適宜,レポート課題を課すので,期限に遅れず提出すること.
注意点:
<成績評価>レポート(100%)の100点満点で(D-1)および(D-2)を総合的に評価する.6割以上獲得した者をこの科目の合格者とする.
<オフィスアワー>月曜日16:00 ~ 17:00,電子情報工学科棟第4教員室.
<先修科目・後修科目>先修科目は情報処理,後修科目はシミュレーション・オブジェクト指向となる.
<備考>本科目ではBYODパソコンを持参すること.
授業の属性・履修上の区分
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
アルゴリズムの基本概念 |
アルゴリズムにおける計算量を理解することができる.
|
2週 |
データ構造の基本概念1 |
配列,リスト,スタック,キューを理解することができる.
|
3週 |
データ構造の基本概念2 |
配列,リスト,スタック,キューを理解することができる.
|
4週 |
木構造とヒープ1 |
木構造について理解し,その計算量が計算できる.
|
5週 |
木構造とヒープ2 |
木構造について理解し,その計算量が計算できる.
|
6週 |
演習1 |
ヒープを実装することができる.
|
7週 |
ヒープソート |
ヒープソートを実装することができる.
|
8週 |
選択ソートとバブルソート |
2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
|
2ndQ |
9週 |
挿入ソートとシェルソート1 |
2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
|
10週 |
挿入ソートとシェルソート2 |
2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
|
11週 |
クイックソート |
クイックソートについて学習し,アルゴリズムの特徴が説明できる.
|
12週 |
演習2 |
クイックソートを実装することができる.
|
13週 |
ハッシュ関数 |
ハッシュ関数について学習し,線形探索への応用やハッシュ値の衝突について説明できる.
|
14週 |
文字列探索アルゴリズム |
文字列探索における単純な探索方法とBoyer-Moore法について学習し,アルゴリズムの特徴が説明できる.
|
15週 |
演習3 |
Boyer-Moore法を実装することができる.
|
16週 |
|
|
後期 |
3rdQ |
1週 |
数の内部表現 |
IEEE754による数の内部表現について理解することができる.
|
2週 |
数値計算の誤差 |
種々の誤差要因について理解することができる.
|
3週 |
数値計算の誤差 |
種々の誤差要因について理解することができる.
|
4週 |
多倍長演算1 |
多倍長演算に必要なデータ構造を設計できる.
|
5週 |
多倍長演算2 |
多倍長演算に必要な周辺ルーチンを作成できる.
|
6週 |
多倍長演算3 |
多倍長演算に必要な周辺ルーチンを作成できる.
|
7週 |
多倍長演算4 |
多倍長演算に必要な加算と減算のルーチンを作成できる.
|
8週 |
多倍長演算5 |
多倍長演算に必要な加算と減算のルーチンを作成できる.
|
4thQ |
9週 |
多倍長演算6 |
多倍長演算に必要な乗算と除算のルーチンを作成できる.
|
10週 |
多倍長演算7 |
多倍長演算に必要な乗算と除算のルーチンを作成できる.
|
11週 |
多倍長演算8 |
四則演算ルーチンを使って平方根や三角関数などの数学関数を作成できる.
|
12週 |
Newton法と二分法1 |
方程式f(x)=0を反復解法によって解くことができる.
|
13週 |
Newton法と二分法2 |
方程式f(x)=0を反復解法によって解くことができる.
|
14週 |
無理数の多倍長計算と性能評価1 |
多倍長演算ルーチンによりeやπなどの値を計算し,精度や速度について評価することができる.
|
15週 |
無理数の多倍長計算と性能評価2 |
多倍長演算ルーチンによりeやπなどの値を計算し,精度や速度について評価することができる.
|
16週 |
|
|
評価割合
| 試験 | 小テスト | 平常点 | レポート | その他 | 合計 |
総合評価割合 | 0 | 0 | 0 | 100 | 0 | 100 |
配点 | 0 | 0 | 0 | 100 | 0 | 100 |