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

科目基礎情報

学校 徳山工業高等専門学校 開講年度 平成31年度 (2019年度)
授業科目 アルゴリズムとデータ構造
科目番号 0091 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 履修単位: 2
開設学科 情報電子工学科 対象学年 3
開設期 通年 週時間数 2
教科書/教材 教科書:新・明解 Javaで学ぶアルゴリズムとデータ構造 (柴田望洋) ソフトバンク(必要に応じて参考資料を配布する)
担当教員 浦上 美佐子

到達目標

1.探索,ソーティング,再帰,線形リストといった基本的なアルゴリズムとデータ構造の理解し,説明することができる.
2.様々な応用課題について、学習したアルゴリズムとデータ構造の知識を用いて,Java 言語プログラミングによる実現手法を理解し,開発を実践できる.
3.時間計算量等によってアルゴリズムを比較・評価できることを理解し、説明することができる.

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1探索,ソーティング,再帰,線形リストといった基本的なアルゴリズムとデータ構造を深く理解し、説明することができる.探索,ソーティング,再帰,線形リストといった基本的なアルゴリズムとデータ構造を理解し、説明することができる.探索,ソーティング,再帰,線形リストといった基本的なアルゴリズムとデータ構造を理解できない.
評価項目2様々な応用課題について,Javaプログラミングによる実現手法を深く理解し,開発を実践することができる.様々な応用課題について,Javaプログラミングによる実現ができ,与えられた解答例をもとに考察することができる.様々な応用課題について,Javaプログラミングによる実現ができない.
評価項目3時間計算量などによってアルゴリズムを比較・評価できることを理解し、説明することができる.時間計算量などによってアルゴリズムを比較・評価できることを理解し、簡単に説明することができる.時間計算量などによってアルゴリズムを比較・評価できることを理解できない.

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

到達目標 B 1

教育方法等

概要:
“アルゴリズム+データ構造=プログラム”(N.Wirth)という名著があるが,基本的なプログラムを書くために必要とされる代表・基礎的なアルゴリズムとデータ構造を学習する.併せて,理解を深め,かつ確認のためのJava言語プログラミングについても修得する.
授業の進め方と授業内容・方法:
各回の授業では,講義による説明の後,JAVA言語によるプログラミング実習・演習を行う.理解度を確認するために,項目毎に学習シートで課題を与え,JAVA言語によるプログラム開発の実践力,結果からの考察を行うプログラミング実習・演習も行う.なお,この際,技術職員のサポートもあるので,積極的な取り組みを期待する.
定期試験は主に学習シートの例題,演習課題から出題する.
事前事後学習として,授業中に配布した学習シートによる演習およびプログラム作成演習を計約30時間行う.
注意点:
本科:基礎プログラミング(1 年),プログラミング言語(2 年),言語処理(5 年)

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 オリエンテーション,データ構造とアルゴリズムの基本
【事前事後学習の内容(1時間)】学習シート
オリエンテーションの後,アルゴリズムとプログラムの違い,各種データ構造,アルゴリズムの基本
2週 線形探索(1)
【事前事後学習の内容(1時間)】学習シート
探索アルゴリズムおよび表中のデータを探索するアルゴリズムで最も単純かつ基本である線形探索について説明できる.加えて,線形探索における“番兵”およびデータの挿入・削除について説明できる.
3週 二分探索
【事前事後学習の内容(1時間)】学習シート
あらかじめソートされているデータに対して,効率よく探索するための手法である2分探索法について説明できる.
4週 演習
【事前事後学習の内容(1時間)】学習シート
レポート課題として,線形探索および2分探索についてのプログラミング演習を行う.
5週 ハッシュ法(1)
【事前事後学習の内容(1時間)】学習シート
データを効率よく探索するための代表的かつ最もよく用いられている手法であるハッシュ法についてプログラムを記述できる.
6週 ハッシュ法(2),アルゴリズムの計算量
【事前事後学習の内容(1時間)】学習シート
前回に引き続き,ハッシュ法について学び,さらに,アルゴリズムの計算量の説明の後,これまでに学んだ探索アルゴリズムの時間計算量について考察することができる.
7週 演習
【事前事後学習の内容(2時間)】学習シート
ハッシュ法により動作するプログラムを設計・実装し、考察することができる.
8週 中間試験 第1~7回に関しての理解を確認する.
9週 再帰アルゴリズムの考え方
【事前事後学習の内容(1時間)】学習シート
例を通じて,再帰アルゴリズムについて理解し、説明できる.
10週 試験問題解説,再帰アルゴリズムの基本
【事前事後学習の内容(1時間)】学習シート
中間試験問題の解説.再帰アルゴリズムの基本について説明できる.
11週 再帰アルゴリズムの解析(1)
【事前事後学習の内容(1時間)】学習シート
再帰アルゴリズムの解析(トップダウン法およびボトムアップ法)について説明できる.
12週 再帰アルゴリズムの解析(2),バックトラッキング(1)
【事前事後学習の内容(1時間)】学習シート
前回に続き,再帰アルゴリズムの解析を学んだ後,しらみつぶしを組織的かつ効率よく行う手法としてのバックトラック法について理解できる.
13週 バックトラッキング(2)
【事前事後学習の内容(1時間)】学習シート
前回に続き,バックトラック法について理解し、説明できる.
14週 演習
【事前事後学習の内容(2時間)】学習シート
レポート課題として,これまでに学んだ再帰アルゴリズムに関するプログラムを設計・実装し、考察することができる.
15週 期末試験 第8,10~14回についての理解を確認する.
16週 試験問題解説 試験の解答と解説を行う.
後期
1週 ソーティングの概念及び単純なソート法
【事前事後学習の内容(1時間)】学習シート
ソーティングの基本及び単純なソート法の1つである単純選択法について説明できる.
2週 単純なソート法及びクイックソート
【事前事後学習の内容(1時間)】学習シート
単純なソート法の続きとして,バブルソートについて学んだ後,代表的な再帰アルゴリズムの例ともいえるクイックソートについて理解し、説明できる.
3週 クイックソート
【事前事後学習の内容(1時間)】学習シート
前回に続きクイックソートについて学ぶ.
4週 演習
【事前事後学習の内容(1時間)】学習シート
レポート課題として,単純ソートおよびクイックソートアルゴリズムに関するプログラミング演習を行う.
5週 ヒープソート
【事前事後学習の内容(1時間)】学習シート
3年次の情報数学の中のグラフにおいて学んだ木構造の概念を用いたヒープソートについて理解し、説明できる.
6週 ヒープソート及びソートアルゴリズムの時間計算量
【事前事後学習の内容(1時間)】学習シート
ヒープソートの続きとこれまでに学んだソートアルゴリズムの時間計算量によって比較・評価できることを説明できる.
7週 演習
【事前事後学習の内容(2時間)】学習シート
レポート課題として,ヒープソートアルゴリズムに関するプログラムを設計・実装し、考察することができる.
8週 中間試験 第16~22回についての理解を確認する.
9週 試験問題解説,線形リスト(1)
【事前事後学習の内容(1時間)】学習シート
試験問題の解答と解説.ポインタを用いた1方向線形リストの概念及びJAVA プログラムでの実現方法を説明できる.
10週 線形リスト(2)
【事前事後学習の内容(1時間)】学習シート
線形リストにおけるデータの探索・追加・削除について説明出来る.
11週 演習
【事前事後学習の内容(1時間)】学習シート
レポート課題として,ここまでに学んだ線形リストに関するプログラミムを設計・実装し、考察できる.
12週 線形リスト(3)
【事前事後学習の内容(1時間)】学習シート
循環・重連結リストについて説明できる.
13週 線形リスト(4)
【事前事後学習の内容(1時間)】学習シート
線形リストを用いたハッシュ法について説明できる.
14週 演習
【事前事後学習の内容(2時間)】学習シート
レポート課題として,循環・重連結リストを用いたハッシュ法に関するプログラムを設計・実装し、考察できる.
15週 期末試験 第24~29回に関する理解度を確認する.
16週 試験問題解説など 試験の解答と解説を行う.

評価割合

試験課題レポート講義ノート演習合計
総合評価割合802000100
基礎的能力0000
専門的能力802000100
分野横断的能力00000