概要:
本講義は効率の良いアルゴリズムの構築を目的とする。そのため、各々の優れたアルゴリズムの考え方や、効率を解析するための方法論を解説し、情報系技術者として必要な基礎学力を身につけることを目標とする。アルゴリズムの課題の解決に取り組み、アルゴリズムの表記方法について学ぶ。
授業の進め方・方法:
到達目標の達成度を確認するために、随時演習課題を与える。
【関連科目】プログラミング基礎Ⅰ、プログラミング基礎Ⅱ
【MCC対応】Ⅳ-C 情報リテラシー、Ⅴ-D-2 ソフトウェア、情報教育対応科目
注意点:
計算機による演習を行うことがあるので、指示があった場合にはノートPCを持参すること。
【評価方法・評価基準】
前期中間試験、前期末試験、後期中間試験、学年末試験を実施する。 成績の評価基準として50点以上を合格とする。
前期末評価：中間試験(40%)、前期末試験(40%)、課題(20%)
後期末評価：中間試験(40%)、学年末試験(40%)、課題(20%)
学年末評価：前期末評価（50%）、後期末評価（50％）
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
アルゴリズムの基礎(1) - アルゴリズムとは？ |
アルゴリズムの概念を説明できる。
|
| 2週 |
アルゴリズムの基礎(2) - アルゴリズムの評価基準 |
与えられたアルゴリズムが問題を解決していく過程を説明できる。
|
| 3週 |
計算量の漸近的評価(1) |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることや、時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。
|
| 4週 |
計算量の漸近的評価(2) |
同じ問題を解決する複数のプログラムを計算量等の観点から比較でき、ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。
|
| 5週 |
基本データ構造(1) - 配列、連結リスト |
配列、リスト構造の基本的なデータ構造の概念と操作を説明できる。
|
| 6週 |
基本データ構造(2) - スタック、キュー |
スタック、キューの基本的なデータ構造の概念と操作を説明できる。
|
| 7週 |
計算機演習 |
配列、連結リスト、スタック、キューのデータ構造を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 8週 |
基本データ構造(3) - 木
|
木の基本的なデータ構造の概念と操作を説明できる。
|
| 2ndQ |
| 9週 |
基本データ構造(4) - 再帰 |
再帰処理の概念を説明できる。
|
| 10週 |
計算機演習 |
木のデータ構造、および、再帰処理を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 11週 |
データの探索(1) - 探索の定義とアルゴリズム |
探索アルゴリズムの概念を説明できる。
|
| 12週 |
データの探索(2) - 線形探索、2分探索 |
線形探索、2分探索のアルゴリズムについて説明できる。
|
| 13週 |
データの探索(3) - ハッシュ法 |
ハッシュ法のアルゴリズムについて説明できる。
|
| 14週 |
計算機演習
|
線形探索、2分探索、ハッシュ法を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 15週 |
前期復習 |
|
| 16週 |
|
|
| 後期 |
| 3rdQ |
| 1週 |
ソートアルゴリズム(1) - ソートの考え方、挿入ソート |
ソート（整列）アルゴリズムの概念を説明できる。
|
| 2週 |
ソートアルゴリズム(2) - 選択ソート、交換ソート、安定性について |
選択ソート、交換ソートのアルゴリズムの概念、および、ソートアルゴリズムの安定性について説明できる。
|
| 3週 |
ソートアルゴリズム(3) - ヒープソート |
ヒープソートのアルゴリズムについて説明できる。
|
| 4週 |
ソートアルゴリズム(4) - クイックソート |
クイックソートのアルゴリズムについて説明できる。
|
| 5週 |
アルゴリズムの設計手法(1) - 分割統治法、グリーディー法 |
アルゴリズムの設計手法である分割統治法、グリーディー法について説明できる。
|
| 6週 |
アルゴリズムの設計手法(2) - 動的計画法 |
アルゴリズムの設計手法である動的計画法について説明できる。
|
| 7週 |
計算機演習 |
分割統治統治法、グリーディー法、動的計画法を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 8週 |
アルゴリズムの設計手法(3) - バックトラック法、分岐限定法 |
アルゴリズムの設計手法であるバックトラック法、分枝限定法について説明できる。
|
| 4thQ |
| 9週 |
グラフアルゴリズム(1) - グラフとは？ |
グラフアルゴリズムについて説明できる。
|
| 10週 |
グラフアルゴリズム(2) - 最短経路問題
|
グラフを利用した最短経路問題について説明できる。
|
| 11週 |
文字列照合(1) - 文字列照合の基本アルゴリズム |
文字列照合の基本アルゴリズムについて説明できる。
|
| 12週 |
文字列照合(2) - ボイヤー・ムーア法 |
文字列照合におけるボイヤー・ムーア法について説明できる。
|
| 13週 |
アルゴリズムの限界 |
アルゴリズムの計算量の限界について概念を説明できる。
|
| 14週 |
計算機演習 |
グラフアルゴリズム、文字列照合を扱うソースプログラムを記述でき、要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。
|
| 15週 |
後期復習 |
|
| 16週 |
|
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 基礎的能力 | 工学基礎 | 情報リテラシー | 情報リテラシー | 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。 | 3 | |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |