概要:
本講義は効率の良いアルゴリズムの構築を目的とする。そのため、各々の優れたアルゴリズムの考え方や、効率を解析するための方法論を解説し、情報系技術者として必要な基礎学力を身につけることを目標とする。アルゴリズムの課題の解決に取り組み、アルゴリズムの表記方法について学ぶ。
授業の進め方・方法:
到達目標の達成度を確認するために、随時演習課題を与える。
【関連科目】プログラミングⅠ、プログラミングⅡ
注意点:
計算機による演習を行うことがあるので、指示があった場合にはノートPCを持参すること。
【評価方法・評価基準】
中間試験、前期末試験、学年末試験を実施する。
前期末：中間試験(40%)、期末試験(40%)、課題(20%)
学年末：年4回の定期試験の総合(80%)、課題(20%)
成績の評価基準として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 | |
| 制御構造の概念を理解し、条件分岐や反復処理を記述できる。 | 3 | |
| 代入や演算子の概念を理解し、式を記述できる。 | 3 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 3 | |
| 主要な言語処理プロセッサの種類と特徴を説明できる。 | 2 | |
| ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 2 | |
| プログラミング言語は計算モデルによって分類されることを説明できる。 | 1 | |
| 主要な計算モデルを説明できる。 | 1 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 4 | |
| ソフトウェア | 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 4 | 前3 |
| アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| ソフトウェアを中心としたシステム開発のプロセスを説明できる。 | 3 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
| 計算機工学 | 整数・小数を2進数、10進数、16進数で表現できる。 | 4 | |
| 整数・小数をコンピュータのメモリ上でディジタル表現する方法を説明できる。 | 4 | |
| 基数が異なる数の間で相互に変換できる。 | 4 | |
| 基本的な論理演算を行うことができる。 | 3 | |
| 基本的な論理演算を組合わせて、論理関数を論理式として表現できる。 | 3 | |
| 論理式の簡単化の概念を説明できる。 | 2 | |
| 情報数学・情報理論 | コンピュータ上での数値の表現方法が誤差に関係することを説明できる。 | 4 | |
| コンピュータ上で数値計算を行う際に発生する誤差の影響を説明できる。 | 4 | |
| コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。 | 2 | |
| 分野別の工学実験・実習能力 | 情報系分野【実験・実習能力】 | 情報系【実験・実習】 | 与えられた問題に対してそれを解決するためのソースプログラムを、標準的な開発ツールや開発環境を利用して記述できる。 | 4 | |
| ソフトウェア生成に利用される標準的なツールや環境を使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | |