授業の概要（ねらい）

よいプログラムを作るにはデータ構造とアルゴリズムの知識が必要です。そのために次に示す内容を学修します。

(1) 計算量
アルゴリズムの良し悪しの評価指標の1つである計算量について学びます。

(2) 文字列アルゴリズム
文字列の探索はもっともよく使われるアルゴリズムの1つです。どのような探索アルゴリズムがあり、計算量がどの程度異なるのかを学びます。

(3) 整列アルゴリズム
データを大きい順または小さい順への整列ももっともよく使われるアルゴリズムの1つです。どのような整列アルゴリズムがあり、計算量がどの程度異なるのかを学びます。

(4) 基本データ構造
アルゴリズムを設計するには、データ構造が重要です。代表的なデータ構造について学びます。

(5) 最短経路アルゴリズム
グラフ上の最短経路を解くアルゴリズムを学びます。適切なデータ構造を用いることで、アルゴリズムの計算量が大幅に短縮できることを学びます。

(6) 最小全域木アルゴリズム
データ構造の違いにより、最小全域木アルゴリズムの計算量が大きく異なることを学びます。

本科目は、DP4C、DP4Mに関する知識、技法、態度を修得します。

授業の到達目標

授業の到達目標は次の4つです。
(a)基本的なデータ構造を理解し、適切に使うことができる。
(b)基本的なアルゴリズムを理解し、適切に使うことができる。
(c)計算量を用いてアルゴリズムの良し悪しが評価できる。
(d)問題に対して、適切なアルゴリズムとデータ構造が選択できる。

成績評価の方法および基準

復習状況確認レポート(3～4通)30%、理解度確認小テスト(2～3回)30%、期末試験40%の割合で評価し、全体で60%以上の評価点を得たものを合格とします。再試験では、再試験の評価が60%以上のものを合格とします。小テストの解説、レポートにコメントを入れて返却等によりフィードバックをします。

教科書・参考文献

準備学修の内容

第1回 授業概要と計算量
予習：教科書第1章を精読して、計算量の概念について確認してください。(1.5時間)
復習：第1章の章末問題を解いてください。(1.5時間)

第2回 文字列アルゴリズム-文字列照合問題
予習：教科書2.1～2.2を精読してきて、文字列照合問題の各種アルゴリズムを確認してください。(1.5時間)
復習：第2章の章末問題を解いてください。(1.5時間)

第3回 文字列アルゴリズム-KMP法
予習：教科書2.3～2.4を精読してきて、KMP法の処理手順を確認してください。(1.5時間)
復習：第2章の章末問題を解いてください。また教科書Algorithm2.4のプログラミングをしてください。(1.5時間)

第4回 整列アルゴリズム-選択ソート、挿入ソート
予習：教科書3.1～3.3を精読して、選択ソート、挿入ソートのアルゴリズムを確認してきてください。(1.5時間)
復習：第3章の章末問題を解いてください。(1.5時間)

第5回 整列アルゴリズム-分割統治法、クイックソート
予習：教科書3.4～3.5を精読してきて、分割統治法、クイックソートのアルゴリズムを確認してきてください。(1.5時間)
復習：教科書Algorithm3.4のプログラミングをしてください。(1.5時間)

第6回 整列アルゴリズム-マージソート、基数ソート
予習：教科書3.6～3.7を精読してきて、マージソート、基数ソートのアルゴリズムを確認してきてください。(1.5時間)
復習：第3章の章末問題を解いてください。また教科書Algorithm3.5のプログラミングをしてください。(1.5時間)

第7回 基本データ構造-キュー、スタック
予習：教科書4.1～4.2を精読してきて、キュー、スタックの概要を確認してきてください。(1.5時間)
復習：線形リストおよびスタックのプログラミングをしてください。(1.5時間)

第8回 基本データ構造-二分探索木、平衡木
予習：教科書4.3～4.4を精読して、二分探索木、平衡木のアルゴリズムを確認してきてください。(1.5時間)
復習：二分探索木のプログラミングをしてください。(1.5時間)

第9回 基本データ構造-ヒープ、素集合データ構造
予習：教科書4.5～4.6を精読してきて、ヒープ、素集合データ構造のアルゴリズムを確認してきてください。(1.5時間)
復習：4章の章末問題を解いてください。またヒープのプログラミングをしてください。(1.5時間)

第10回 最短経路アルゴリズム-グラフの表現方法
予習：教科書5.1～5.2を精読してきて、グラフの表現方法の概要を確認してきてください。(1.5時間)
復習：5章の章末問題を解いてください。(1.5時間)

第11回 最短経路アルゴリズム-ダイクストラ法
予習：教科書5.3を精読してきて、ダイクストラ法のアルゴリズムを確認してきてください。(1.5時間)
復習：5章の章末問題を解いてください。(1.5時間)

第12回 最短経路アルゴリズム-ベルマン・フォード法
予習：教科書5.4を精読してきて、ベルマン・フォード法のアルゴリズムを確認してきてください。(1.5時間)
復習：5章の章末問題を解いてください。(1.5時間)

第13回 最小全域木アルゴリズム-最良優先探索法
予習：教科書6.1～6.2を精読してきて、最良優先探索法のアルゴリズムを確認してきてください。(1.5時間)
復習：6章の章末問題を解いてください。(1.5時間)

第14回 最小全域木アルゴリズム-クラスカル法、プリム法
予習：教科書6.3～6.4を精読して、クラスカル法、プリム法のアルゴリズムを確認してきてください。(1.5時間)
復習：6章の章末問題を解いてください。(1.5時間)

第15回 テスト、まとめ
試験勉強をしてきてください。(少なくとも3時間以上)

その他履修上の注意事項

演習、実習でプログラミングをすることがありますので、プログラミング1、2の復習をして授業にのぞむとともに、Processingがインストールされた自分のPCを必ず持参してください。授業の資料をLMSはアップしますので、予習、復習に使ってください。この科目はJABEE対応プログラムの必修科目で、学習・教育到達目標中項目4-2に対応しています。

授業内容