概要:
「データ構造」と「アルゴリズム」はプログラムを学習する上で，必ず学ばなければならない基礎の一つである．コンピュータを用いた「問題解決のための考え方」を理解し，与えられた制約を満たすための解を導くための手法を理解し，どのプログラミング言語「問題を解決する能力」を身に付けることを目的とする．本講では、基本的なアルゴリズムを深く理解することが必要となる．
厳選されたアルゴリズムを通して，問題に対するアプローチの方法，プログラミングのテクニック，計算時間に対する感覚などを養っていく．
授業の進め方・方法:
座学であるが，講義項目ごとに演習や課題に取り組み，各自の理解度を確認する．また，定期試験返却時には，解説を行い，理解が不十分な点を解消する．
注意点:
関連科目
基本的なプログラミング能力を前提としており，プログラミング科目と密接に関係している．また，情報科学分野の基礎科目であり問題を解決するための必須分野であるため，3年次以降情報系専門科目を履修する上で学習内容の理解が前提条件となる科目である．
学習指針
講義中は，内容を理解するように努めること．事前に教科書で予習しておき，講義中にノートをとり，配布する事業資料に書き込むやり方が有効である．
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
アルゴリズムとデータ構造 |
アルゴリズム，データ構造とは何か，重要性について理解できる．
|
| 2週 |
計算量 |
アルゴリズムの評価方法，計算量の定義，O記法について理解できる．
|
| 3週 |
基本データ構造1 |
配列，連結リストについて理解できる．
|
| 4週 |
基本データ構造2 |
スタック，キューについて理解できる．
|
| 5週 |
木構造１ |
木の概念について理解できる．
|
| 6週 |
木構造2 |
2分木について理解できる．
|
| 7週 |
前期中間試験 |
講義内容を理解し，試験問題に対して正しく解答することができる．
|
| 8週 |
試験返却・解答
再帰 |
試験問題を見直し，理解が不十分な点を解消する．
再帰アルゴリズムの基本，利用例について理解できる．
|
| 2ndQ |
| 9週 |
データ探索１ |
探索の定義と簡単な探索アルゴリズムについて理解できる．
|
| 10週 |
データ探索2 |
2分探索法，ハッシュ法について理解できる．
|
| 11週 |
データ探索3 |
探索アルゴリズムの実行速度の比較ができる．
|
| 12週 |
ソート１ |
ソートの定義と基本的なアルゴリズムについて理解できる．
|
| 13週 |
ソート2 |
挿入ソート，ヒープソート，クイックソートについて理解できる．
|
| 14週 |
ソート3 |
安定なソートを理解し，ソートアルゴリズムの性能比較ができる．
|
| 15週 |
前期末試験 |
授業内容を理解し，試験問題に対して正しく解答することができる．
|
| 16週 |
試験返却・解答 |
試験問題を見直し，理解が不十分な点を解消する．
|
| 後期 |
| 3rdQ |
| 1週 |
アルゴリズム設計１ |
分割統治法について理解できる．
|
| 2週 |
アルゴリズム設計2 |
貪欲法について理解できる．
|
| 3週 |
アルゴリズム設計3 |
動的計画法について理解できる．
|
| 4週 |
アルゴリズム設計4 |
バックトラック法について理解できる．
|
| 5週 |
アルゴリズム設計5 |
分枝限定法について理解できる．
|
| 6週 |
グラフアルゴリズム1 |
グラフの概念，グラフを格納するデータ構造について理解できる．
|
| 7週 |
後期中間試験 |
講義内容を理解し，試験問題に対して正しく解答することができる．
|
| 8週 |
試験返却・解答
グラフアルゴリズム2 |
試験問題を見直し，理解が不十分な点を解消する．
最短経路問題について理解できる．
|
| 4thQ |
| 9週 |
文字列処理・探索１ |
文字列処理，文字列の探索アルゴリズムについて理解できる．
|
| 10週 |
文字列処理・探索2 |
文字列処理，文字列の探索アルゴリズムについて理解できる．
|
| 11週 |
アルゴリズムの限界1 |
アルゴリズムの限界について理解できる．
|
| 12週 |
アルゴリズムの限界2 |
問題のクラスについて理解できる．
|
| 13週 |
アルゴリズムの限界3 |
解くことのできない問題について理解できる．
|
| 14週 |
実装演習 |
学習したアルゴリズムを実装することができる．
|
| 15週 |
学年末試験 |
授業内容を理解し，試験問題に対して正しく解答することができる．
|
| 16週 |
試験返却・解答 |
試験問題を見直し，理解が不十分な点を解消する．
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 変数とデータ型の概念を説明できる。 | 3 | |
| 制御構造の概念を理解し、条件分岐や反復処理を記述できる。 | 3 | |
| 代入や演算子の概念を理解し、式を記述できる。 | 3 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 3 | |
| 主要な言語処理プロセッサの種類と特徴を説明できる。 | 1 | |
| ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 1 | |
| プログラミング言語は計算モデルによって分類されることを説明できる。 | 2 | |
| 主要な計算モデルを説明できる。 | 2 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 3 | |
| ソフトウェア | 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 4 | |
| アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| ソフトウェアを中心としたシステム開発のプロセスを説明できる。 | 4 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
| システムプログラム | コンピュータシステムにおけるオペレーティングシステムの位置づけを説明できる。 | 3 | |
| プロセス管理やスケジューリングなどCPUの仮想化について説明できる。 | 3 | |
| 分野別の工学実験・実習能力 | 情報系分野【実験・実習能力】 | 情報系【実験・実習】 | 与えられた数値を別の基数を使った数値に変換できる。 | 1 | |
| 与えられた問題に対してそれを解決するためのソースプログラムを、標準的な開発ツールや開発環境を利用して記述できる。 | 4 | |
| ソフトウェア生成に利用される標準的なツールや環境を使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | |
| ソフトウェア開発の現場において標準的とされるツールを使い、生成したロードモジュールの動作を確認できる。 | 3 | |