授業の概要（ねらい）

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

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

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

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

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

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

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

ディプロマポリシー2(DP2)に関する知識、技法、態度を修得します。

授業の到達目標

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

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

レポート締切日までにすべての小テストの正解率が80%以上になるように受験してください。5つの小テストの正解率がすべて80%以上の方が科目修得試験の受験資格を得ることができます。I期のレポート締切日までに受験した小テストの点数は、III期まで有効です。たとえば、I期の締切日までに2つの小テストの正解率が80%以上だった場合は、その点数はIII期まで有効となり、III期のレポート締め切りまでに残り3つの小テストの正解率が80%以上になれば科目修得試験の受験資格を得ることができます。科目修得試験の結果で成績を評価します。EメールやLMSのツールを使ってフィードバックします。

教科書・参考文献

準備学修の内容

第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時間以上)

その他履修上の注意事項

Processingのコードを使った説明、Processingのプログラミング課題などがありますので、プログラミング1,2の復習をしてから授業にのぞんでください。

授業内容