到達目標
学習目的：代表的なアルゴリズムやデータ構造の仕組みについて説明できる、または説明を読めばその名称が答えられる。アルゴリズムの効率を考える際に重要となる時間計算量などの基本的概念や用語を説明できる。
到達目標
１．アルゴリズムとは何かを説明できる。
２．ソート，探索に関する代表的なアルゴリズムを説明できる。
３．スタック，キュー，二分木などのデータ構造を説明できる。
４．情報のグラフ表現を使える。
ルーブリック
| 優 | 良 | 可 | 不可 |
| 評価項目1 | 計算量の表記とその定義を何も見ずに書くことができ，その意味を説明できる。 | 計算量の表記とその定義を，ノートを見ながら書くことができ，その意味を説明できる。 | 計算量の表記とその定義を，ノートを見ながら書くことができる。 | 計算量の表記とその定義を知らない。 |
| 評価項目2 | ソート，探索のアルゴリズムを実装できる。かつそのプログラムに不備があった場合に修正できる。 | ソート，探索のアルゴリズムを実装できる。 | ソート，探索に関する代表的なアルゴリズムアルゴリズムを説明できる。 | ソート，探索に関する代表的なアルゴリズムアルゴリズムを説明できない。 |
| 評価項目3 | スタック，キュー，２分木などのデータ構造を必要に応じて利用したプログラムが実装できる。 | スタック，キュー，２分木などのデータ構造を利用したプログラムが実装できる。 | スタック，キュー，２分岐などのデータ構造を説明できる。 | スタック，キュー，２分岐などのデータ構造を説明できない。 |
| 評価項目4 | グラフ構造を用いたアルゴリズムを説明でき，その計算量を求めることができる。 | グラフ構造を用いたアルゴリズムを説明できる。 | 情報のグラフ表現を使える。 | グラフ構造を知らない。 |
学科の到達目標項目との関係
教育方法等
概要:
一般・専門の別：専門 学習の分野：情報・制御
必修・履修・履修選択・選択の別：必修
基礎となる学問分野：総合系／情報学／計算基盤／ソフトウェア
学科学習目標との関連：本科目は情報工学科学習目標「（２）情報・制御ならびに電気・電子の分野に関する専門技術分野の知識を修得し，情報・通信等の分野に応用できる能力を身につける。」に相当する科目である。
技術者教育プログラムとの関連：本科目が主体とする学習・教育目標は「（Ａ）技術に関する基礎知識の深化，Ａ－２:｢電気・電子｣，｢情報・制御｣に関する専門技術分野の知識を修得し，説明できること」である。
授業の概要：コンピュータを使って問題解決をする場合，使用するアルゴリズムとデータ構造が異なると問題解決の効率が違ってくる。本科目では，これらの選択能力や設計能力の基礎を修得するため，代表的なアルゴリズムとデータ構造を題材にそれらの仕組み等を学習する。
授業の進め方・方法:
授業の方法：板書を中心に授業を進めるが，できるだけ学生に質問し，学生の理解度を確かめながら授業を進める。また学生による発表も取り入れる。理解が深まるよう，演習などを課す。
成績評価方法：4回の定期試験の結果に重みを付け評価する（100%）。再試験は原則行わない。ただし，定期試験の結果をもって単位認定を正当に結論できないと判断した場合には再試験を行う。定期試験の結果に対する重みはレポートの内容，授業発表の内容による。
注意点:
履修上の注意：本科目は「授業時間外の学習を必修とする科目」である。授業時間として３０単位時間開講するが，これ以外に３０単位時間の学習が必修となる。これらの学習については担当教員の指示に従うこと。
履修のアドバイス：本科目はこれまでに履修してきた数学やプログラミングに関する科目と深く関連している。必要に応じて復習を行うこと。
基礎科目：プログラミングⅠ（１年），プログラミングⅡ（２），プログラミング言語（３） 関連科目：データベース（５年），プログラミング特論（５），情報数理Ⅱ（５）
受講上のアドバイス：授業開始前に行う出席確認に遅れた者は遅刻として扱う。遅刻は1時限分の欠課として扱う。授業開始から５０分を経過しての遅刻については2時限分の欠課として扱う。BlackBoardに授業の進行状況を適宜掲載するので参考にすること。
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス〔科目の概要，目的，評価方法，注意事項等〕 |
本科目の位置づけを理解する。
|
| 2週 |
アルゴリズムと計算量 １ |
実社会の問題を数理モデルとして定式化できる例を挙げられる。
|
| 3週 |
基本的なデータ構造 １ |
問題を数理モデルとして定式化するときにデータ構造を2つ以上候補として挙げられる。
|
| 4週 |
基本的なデータ構造 ２ |
問題を数理モデルとして定式化するときに適切なデータ構造を設計できる。
|
| 5週 |
演習 |
基本的なデータ構造での各種処理の計算時間を説明できる。
|
| 6週 |
ソート・アルゴリズ １ |
バブルソート、インサーションソートを説明できる。
|
| 7週 |
ソート・アルゴリズ ２ |
クインクソート、マージソートなどを説明できる。
|
| 8週 |
演習 |
ソートのアルゴリズムを5つ以上挙げられ、その挙動について説明できる。
|
| 2ndQ |
| 9週 |
（前期中間試験） |
自分の知識を確認する。
|
| 10週 |
答案返却と解説，演習 |
自分の知識で不足している箇所を認識し、改善する。
|
| 11週 |
木のデータ構造 １ |
2分探索木、平衡木について説明できる。
|
| 12週 |
木のデータ構造 ２ |
B木について説明できる。
|
| 13週 |
演習 |
自分の知識を確認する。
|
| 14週 |
グラフ・アルゴリズム １ |
グラフを数理モデルとして使うことができる。
|
| 15週 |
（前期末試験） |
自分の知識を確認する。
|
| 16週 |
前期末試験の答案返却と試験解説 |
自分の知識で不足している箇所を認識し、改善する。
|
| 後期 |
| 3rdQ |
| 1週 |
後期の説明〔ガイダンス〕 |
自分の知識を確認する。
|
| 2週 |
グラフ・アルゴリズム ２ |
ダイクストラ法を説明できる。
|
| 3週 |
演習 |
自分の知識を確認する。
|
| 4週 |
文字列アルゴリズム １ |
文字列照合という問題を数理モデルとして定式化できる。
|
| 5週 |
文字列アルゴリズム ２ |
ラビン・カープ法について説明できる。
|
| 6週 |
演習 |
ラビン・カープ法以外の文字列照合アルゴリズムについて名前は知っている。
|
| 7週 |
（後期中間試験） |
自分の知識を確認する。
|
| 8週 |
答案返却と解説 |
自分の知識で不足している箇所を認識し、改善する。
|
| 4thQ |
| 9週 |
アルゴリズムの設計戦略 １ |
分割統治法の考えを用いたアルゴリズムを1つ以上挙げられる。
|
| 10週 |
アルゴリズムの設計戦略 ２ |
分割統治法の考えを用いたアルゴリズムを2つ以上挙げられる。
|
| 11週 |
演習 |
自分の知識を確認する。
|
| 12週 |
組合せ最適化 １ |
組合せ最適化問題の例を1つ以上挙げられる。
|
| 13週 |
組合せ最適化 ２ |
組合せ最適化問題の例とそれに対するアルゴリズムを挙げられる。
|
| 14週 |
演習 |
自分の知識を確認する。
|
| 15週 |
（後期末試験） |
自分の知識で不足している箇所を認識し、改善する。
|
| 16週 |
後期末試験の答案返却と試験解説 |
自分の知識を確認する。
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
評価割合
| 試験 | 発表 | 相互評価 | 自己評価 | 課題 | 小テスト | 合計 |
| 総合評価割合 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 100 | 0 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |