アルゴリズムとデータ構造

科目基礎情報

学校 長野工業高等専門学校 開講年度 平成31年度 (2019年度)
授業科目 アルゴリズムとデータ構造
科目番号 0040 科目区分 専門 / 必修
授業形態 授業 単位の種別と単位数 履修単位: 2
開設学科 電子情報工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 教科書:紀平拓男・春日伸弥「プログラミングの宝箱 アルゴリズムとデータ構造」ソフトバンククリエイティブ,教員が用意するテキスト
担当教員 伊藤 祥一

到達目標

各種アルゴリズムの計算量を計算できること,数値計算の誤差要因について説明できること,学習したアルゴリズムをC言語で実装できることで,学習・教育目標(D-1)および(D-2)の達成とする.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
理論各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができ,計算量の削減や計算誤差の縮小について述べることができる.各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができる.各種アルゴリズムの計算量の計算・数値計算の誤差要因の説明ができない.
実装学習したアルゴリズムのC言語による実装ができ,高速化などの工夫を盛り込める.学習したアルゴリズムのC言語による実装が概ねできる.学習したアルゴリズムのC言語による実装ができない.

学科の到達目標項目との関係

(D-1)

教育方法等

概要:
優れたプログラムを作成するうえで必須の知識であるアルゴリズムとデータ構造について,計算量を中心にその基本概念を学習する.学習したアルゴリズムを実際にC言語により実装する.
授業の進め方と授業内容・方法:
・授業方法は演習を中心とする.
・適宜,レポート課題を課すので,期限に遅れず提出すること.
注意点:
<成績評価>レポート(100%)の100点満点で(D-1)及び(D-2)を総合的に評価する.6割以上獲得した者をこの科目の合格者とする.
<オフィスアワー>月曜日16:00 ~ 17:00,電子情報工学科棟第4教員室.
<先修科目・後修科目>先修科目は情報処理,後修科目はシミュレーション・オブジェクト指向となる.
<備考>ノートPCを使用する.

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 アルゴリズムの基本概念 アルゴリズムにおける計算量を理解することができる.
2週 データ構造の基本概念1 配列,リスト,スタック,キューを理解することができる.
3週 データ構造の基本概念2 配列,リスト,スタック,キューを理解することができる.
4週 木構造とヒープ1 木構造について理解し,その計算量が計算できる.
5週 木構造とヒープ2 木構造について理解し,その計算量が計算できる.
6週 演習1 ヒープを実装することができる.
7週 ヒープソート ヒープソートを実装することができる.
8週 選択ソートとバブルソート 2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
9週 挿入ソートとシェルソート1 2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
10週 挿入ソートとシェルソート2 2つのアルゴリズムについて学習し,アルゴリズムの特徴が説明できる.
11週 クイックソート クイックソートについて学習し,アルゴリズムの特徴が説明できる.
12週 演習2 クイックソートを実装することができる.
13週 ハッシュ関数 ハッシュ関数について学習し,線形探索への応用やハッシュ値の衝突について説明できる.
14週 文字列探索アルゴリズム 文字列探索における単純な探索方法とBoyer-Moore法について学習し,アルゴリズムの特徴が説明できる.
15週 演習3 Boyer-Moore法を実装することができる.
16週
後期
1週 数の内部表現 IEEE754による数の内部表現について理解することができる.
2週 数値計算の誤差 種々の誤差要因について理解することができる.
3週 数値計算の誤差 種々の誤差要因について理解することができる.
4週 多倍長演算1 多倍長演算に必要なデータ構造を設計できる.
5週 多倍長演算2 多倍長演算に必要な周辺ルーチンを作成できる.
6週 多倍長演算3 多倍長演算に必要な周辺ルーチンを作成できる.
7週 多倍長演算4 多倍長演算に必要な加算と減算のルーチンを作成できる.
8週 多倍長演算5 多倍長演算に必要な加算と減算のルーチンを作成できる.
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週

評価割合

試験小テスト平常点レポートその他合計
総合評価割合0001000100
配点0001000100