| 本科 | 選択・必修 | 開設時期 | 単位数 | 授業形態 | 担 当 | |||
| 情報電子 | 必修 | 3年 | 2 | 講義 | 浦上美佐子 | |||
| 【授業の概要】 “アルゴリズム＋データ構造＝プログラム”（N.Wirth）という名著があるが、基本的なプログラムを書くために必要とされる代表・基礎的なアルゴリズムとデータ構造を学習する。併せて、理解を深め、かつ確認のためのJava言語プログラミングについても修得する。 | ||||||||
| 【授業の進め方】 講義での説明の後、より理解を深めるために、JAVA言語によるプログラミング実習・演習も行うので、是非、“手を動かして”修得して欲しい。なお、この際、技術職員のサポートもあるので、積極的な取り組みを期待する。 | ||||||||
| 【授業計画】 | 【授業項目】 | 【内 容】 | ||||||
| 1 回 | オリエンテーション 線形探索（１） |
オリエンテーションの後、探索アルゴリズムおよび表中のデータを探索するアルゴリズムで最も単純かつ基本である線形探索について学ぶ。 | ||||||
| 2 回 | 線形探索（２） | 線形探索における“番兵”およびデータの挿入・削除について学ぶ。 | ||||||
| 3 回 | ２分探索 | あらかじめソートされているデータに対して、効率よく探索するための手法である２分探索法について学ぶ。 | ||||||
| 4 回 | 演習 | レポート課題として、線形探索および２分探索についてのプログラミング演習を行う。（学習シート） | ||||||
| 5 回 | ハッシュ法（１） | データを効率よく探索するための代表的かつ最もよく用いられている手法であるハッシュ法について学ぶ。 | ||||||
| 6 回 | ハッシュ法（２） アルゴリズムの計算量 |
前回に引き続き、ハッシュ法について学び、さらに、アルゴリズムの計算量の説明の後、これまでに学んだ探索アルゴリズムの時間計算量について考察する。 | ||||||
| 7 回 | 演習 | レポート課題として、ハッシュ法についてのプログラミング演習を行う。（学習シート） | ||||||
| 8 回 | 再帰アルゴリズムの考え方 | 例を通じて、再帰アルゴリズムの考え方を学ぶ。 | ||||||
| 9 回 | 中間試験問題 | 第１〜７回に関しての理解を確認する。 | ||||||
| 10 回 | 中間試験問題解説及び 再帰アルゴリズムの基本 |
中間試験問題の解説の後、再帰アルゴリズムの基本について述べる。 | ||||||
| 11 回 | 再帰アルゴリズムの解析（１） | 再帰アルゴリズムの解析（トップダウン法およびボトムアップ法）について解説する。 | ||||||
| 12 回 | 再帰アルゴリズムの解析（２） バックトラッキング（１） |
前回に続き、再帰アルゴリズムの解析を学んだ後、しらみつぶしを組織的かつ効率よく行う手法としてのバックトラック法について学ぶ。 | ||||||
| 13 回 | バックトラッキング（２） | 前回に続き、バックトラック法について学ぶ。 | ||||||
| 14 回 | 演習 | レポート課題として、これまでに学んだ再帰アルゴリズムに関するプログラミング演習を行う。（学習シート） | ||||||
| 期末試験 | 第８、１０〜１４回についての理解を確認する。 | |||||||
| 15 回 | 答案返却など | 前期末試験の問題の解説をする。 | ||||||
| 16 回 | ソーティングの概念及び 単純なソート法 |
ソーティングの基本及び単純なソート法の１つである単純選択法について学ぶ。 | ||||||
| 17 回 | 単純なソート法及び クイックソート |
単純なソート法の続きとして、バブルソートについて学んだ後、代表的な再帰アルゴリズムの例ともいえるクイックソートについて学習する。 | ||||||
| 18 回 | クイックソート | 前回に続きクイックソートについて学ぶ。 | ||||||
| 19 回 | 演習 | レポート課題として、単純ソートおよびクイックソートアルゴリズムに関するプログラミング演習を行う。 | ||||||
| 20 回 | ヒープソート | ３年次の情報数学の中のグラフにおいて学んだ木構造の概念を用いたヒープソートについて学ぶ。 | ||||||
| 21 回 | ヒープソート及び ソートアルゴリズムの時間計算量 |
ヒープソートの続きとこれまでに学んだソートアルゴリズムの時間計算量について考察する。 | ||||||
| 22 回 | 演習 | レポート課題として、ヒープソートアルゴリズムに関するプログラミング演習を行う。 | ||||||
| 23 回 | 後期中間試験 | 第１６〜２２回についての理解を確認する。 | ||||||
| 24 回 | 中間試験問題解説及び 線形リスト（１） |
中間試験問題解説の後、ポインタを用いた１方向線形リストの概念及びJAVAプログラムでの実現方法について学ぶ。 | ||||||
| 25 回 | 線形リスト（２） | 線形リストにおけるデータの探索・追加・削除について学ぶ。 | ||||||
| 26 回 | 演習 | レポート課題として、ここまでに学んだ線形リストに関するプログラミング演習を行う。（学習シート） | ||||||
| 27 回 | 線形リスト（３） | 循環・重連結リストについて学ぶ。 | ||||||
| 28 回 | 線形リスト（４） | 線形リストを用いたハッシュ法について学ぶ。 | ||||||
| 29 回 | 演習 | レポート課題として、循環・重連結リストを用いたハッシュ法に関するプログラミング演習を行う。（学習シート） | ||||||
| 期末試験 | 第２４〜２９回に関する理解度をチェックする。 | |||||||
| 30 回 | 答案返却など | 後期末試験の問題の解説をする。 | ||||||
| 【到達目標】 | 探索、ソーティング、再帰、線形リストといった基本的なアルゴリズムとデータ構造の理解及びそのJava言語プログラミングによる実現手法の修得を到達目標とする。 | 【徳山高専学習・教育目標】 | B1 | 【JABEE基準】 | ||||
| 【評価法】 | 原則として、４回の試験の平均（（前期中間試験＋前期末試験＋後期中間試験＋後期末試験）／４）を８０％、レポートを２０％とし、これらの合計を最終成績とする。 | |||||||
| 【テキスト】 | 教科書：明解Javaによるアルゴリズムとデータ構造（柴田望洋）ソフトバンク | |||||||
| 【関連科目】 | 本科：基礎プログラミング（1年）、プログラミング言語（2年）、言語処理（5年） | |||||||