データ構造にはバリエーションがあることを理解し，同一の問題に対し，選択したデータ構造によってアルゴリズムが変化しうることを理解できる．リスト構造、スタック、キューなどの基本的なデータ構造と，木構造，グラフ構造の概念と操作を説明できる．
与えられたアルゴリズムが問題を解決していく過程を説明できる．同一の問題に対し，それを解決できる複数のアルゴリズムが存在しうることを理解できる．整列，探索など基本的なアルゴリズム及びハッシュ法，再帰法，動的計画法などのアルゴリズムについて説明できる．時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解できる．
概要:
データ構造とアルゴリズムはコンピュータ・サイエンスの根幹を成すものであり,プログラミング技法を学ぶにおいて最も重要となる概念である．本科目は基本的なデータ構造としてのリスト，スタックとキュー，動的なデータ構造としての木構造，グラフ構造などの構成と，これらのデータ構造における整列と探索アルゴリズムについて学ぶ．また，ハッシュ法，自己組織リスト検索，再帰法、動的計画法など実用性の高いアルゴリズムの設計及びその応用を取り上げる. プログラミングの基礎を踏まえてデータ構造とアルゴリズム設計の手順や手法と，アルゴリズム時間計算量の解析法とオーダーの求め方などを学んで行く.
授業の進め方・方法:
（１） 自力で基本なデータ構造とアルゴリズムの設計及び実装することができる． （２） 探索と整列のアルゴリズムの考え方について理解しそのプログラムを作成できる．（３）木構造及び深さ探索アルゴリズム，グラフ構造及びＤＦＳとＢＦＳアルゴリズム， ハッシュ法，再帰法，動的計画法，貪欲法の考え方について理解でき，簡単な応用例をプログラミングできる．（４）アルゴリズム時間計算量の解析方法とオーダーの求め方について理解できる．
上記のことを授業目的とし授業を進める．本科目は学修科目であるため，学習の各段階において自学学習用の課題を設け，学習の成果を定期試験等筆記試験や実技試験，小テストと演習を総合し評価する．実技試験または演習レポートの提出期限は課題提示と同時に示し，期限に遅れて提出されたレポートに対し減点する．60%以上の得点率で目標達成とみなす．
注意点:
規定授業時間数は60時間，放課後・家庭で30時間程度の自学自習が求められる．
本科目は，計算機科学及び情報管理に関する基礎的な科目である.より効率の良いプログラムを書くために理解しておかねばならない必要な知識でもある．３年次のプログラミング言語,４・５年次のソフトウェア系の科目と関連する．講義内容について十分に復習して受講することが望まれる．また，資格試験や編入学・就職試験にも役立つ知識であるため，理論だけではなく，実際に学んだデータ構造とアルゴリズムを実装してみることも重要である．
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス
|
本科目の概要，授業方針，評価方法等について紹介する．
|
| 2週 |
配列または連結リストによるスタック（棚）構造 |
スタック構造とその実装方法について理解し，その挿入・削除操作アルゴリズムを実装できる．
|
| 3週 |
配列または連結リストによるキュー（待ち行列）とリング（環状キュー）構造 |
キューとリング構造と実装方法について理解し，その挿入・削除操作アルゴリズムを実装できる．
|
| 4週 |
バブルソートアルゴリズム，
クイックソートアルゴリズム |
２つのソートアルゴリズムについて理解でき，プログラムを組める．
|
| 5週 |
マージソートアルゴリズム，
ソートアルゴリズムの性能分析 |
マージソートアルゴリズムについて理解でき，プログラムを組める．また，３つのソートアルゴリズムを実装し，それぞれの実行時間を計測し，性能分析について理解する．
|
| 6週 |
アルゴリズム計算量の評価方法（１）
概念，時間計算量，領域計算量，オーダー記法 |
計算量の評価基準と記法を理解し，時間計算量と領域計算量の評価を理解できる（英文教材を利用する）．
|
| 7週 |
アルゴリズム計算量の評価方法（２）
オーダーの計算，アルゴリズム計算量の計算 |
オーダー記法の求め方及びそれを利用したアルゴリズム計算量の評価を説明できる（英文教材を利用する）．
|
| 8週 |
中間試験 |
|
| 2ndQ |
| 9週 |
線形探索（リニアサーチ），
バイナリサーチ |
線形探索（リニアサーチ），バイナリサーチアルゴリズムと実装方法を理解できる．時間計算量を解析できる．
|
| 10週 |
自己組織化探索（１）
概念，三つのアルゴリズム |
自己組織化探索アルゴリズムと実装方法を理解できる（英文教材を利用する）．
|
| 11週 |
自己組織化探索（２）
三つのアルゴリズム，性能分析 |
自己組織化探索アルゴリズムと実装方法を理解できる．時間計算量を解析できる（英文教材を利用する）．
|
| 12週 |
ハッシュ法（１）
概念，ハッシュ関数の設計 |
ハッシュ法の概念を理解し，ハッシュ関数の設計方法を説明できる．
|
| 13週 |
ハッシュ法（２）
内部ハッシング |
ハッシュ法における衝突を解消するハッシュ法の仕組み，内部ハッシングアルゴリズムの設計と実装法を理解でき，プログラムを組める．
|
| 14週 |
ハッシュ法（３）
外部ハッシングアルゴリズム |
ハッシュ法における衝突を解消する外部ハッシングアルゴリズムの設計と実装法を理解でき，プログラムを組める．
|
| 15週 |
定期試験：基本的なテータ構造，ソートと探索アルゴリズム，計算量など |
|
| 16週 |
定期試験答案返却と解説 |
|
| 後期 |
| 3rdQ |
| 1週 |
木構造（ツリー構造）（１）
概念とデータ構造 |
木構造の概念とデータ構造について理解できる．
|
| 2週 |
木構造（ツリー構造）（２）
深さ優先探索アルゴリズム |
木構造の深さ優先探索アルゴリズムの行きがけ順（前順，pre-order）, 通りがけ順（中順，in-order）,帰りがけ順 (後順，post-order)について理解できる．
|
| 3週 |
.２分木と多分木 |
２分木構造及び２分木・多分木の相互変換について理解できる．
|
| 4週 |
２分探索木（１）
２分探索木の構造 |
２分探索木の概念と構造を理解できる．
|
| 5週 |
２分探索木（２）
挿入・探索・削除アルゴリズム |
２分探索木の構成と挿入・削除，探索操作の実装法について説明できる．
|
| 6週 |
再帰法（１）
概念，直接再帰法 |
直接再帰法の仕組みとその応用について理解できる。
|
| 7週 |
再帰法（２）
間接再帰法 |
間接再帰法の仕組みとその応用について理解できる。
|
| 8週 |
中間試験 |
|
| 4thQ |
| 9週 |
グラフ構造（１）
概念，グラフ構造とネットワーク構造 |
グラフの概念，隣接行列，接続行列，隣接リストを用いたグラフの表現法を応用できる．
|
| 10週 |
グラフの深さ優先探索（DFS）アルゴリズム |
ＤＦＳアルゴリズムを理解でき，プログラムを組める．
|
| 11週 |
グラフの幅優先探索（BFS）アルゴリズム |
ＢＦＳアルゴリズムを理解でき，プログラムを組める．
|
| 12週 |
動的計画法と最短経路問題のDijkstra法（１）
概念，動的計画法アルゴリズム |
動的計画法の考え方と仕組み，動的計画法を扱うと解きやすい問題の条件について理解できる．
|
| 13週 |
動的計画法と最短経路問題のDijkstra法（２）
Dijkstraアルゴリズムとその実装 |
動的計画法を用いて最短経路問題を解くプログラムを組める．Ｄｉｊｋｓｔｒａ法を理解し，実装できる．
|
| 14週 |
貪欲法と最大スパニング木問題（１）
概念，貪欲法アルゴリズム
（２）
Ｋｒｕｓｋａｌアルゴリズムとその実装 |
貪欲法の考え方と仕組み，貪欲法を扱うと解きやすい問題の条件について理解できる．貪欲法を用いて最大スパニング木問題を解くプログラムを組める．Ｋｒｕｓｋａｌ法を理解し，実装できる．
|
| 15週 |
定期試験：グラフ、グラフ探索アルゴリズム |
|
| 16週 |
定期試験答案返却と解説 |
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 代入や演算子の概念を理解し、式を記述できる。 | 4 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 4 | 前10 |
| 変数の概念を説明できる。 | 4 | |
| データ型の概念を説明できる。 | 4 | |
| 制御構造の概念を理解し、条件分岐を記述できる。 | 4 | |
| 制御構造の概念を理解し、反復処理を記述できる。 | 4 | |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 4 | |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | |
| 与えられたソースプログラムを解析し、プログラムの動作を予測することができる。 | 4 | 前16 |
| 主要な言語処理プロセッサの種類と特徴を説明できる。 | 4 | |
| ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 4 | |
| プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | |
| 主要な計算モデルを説明できる。 | 3 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 4 | |
| 要求仕様に従って、いずれかの手法により動作するプログラムを設計することができる。 | 4 | |
| 要求仕様に従って、いずれかの手法により動作するプログラムを実装することができる。 | 4 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを実装できる。 | 4 | |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | 前3 |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 後15 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | 後15 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | |
| ソフトウェアを中心としたシステム開発のプロセスを説明できる。 | 2 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
| 計算機工学 | 整数・小数をコンピュータのメモリ上でディジタル表現する方法を説明できる。 | 3 | |
| 基数が異なる数の間で相互に変換できる。 | 3 | |
| 基本的な論理演算を行うことができる。 | 2 | |
| 基本的な論理演算を組合わせて、論理関数を論理式として表現できる。 | 2 | |
| 論理式の簡単化の概念を説明できる。 | 2 | |
| 論理ゲートを用いて論理式を組合せ論理回路として表現することができる。 | 2 | |
| 与えられた組合せ論理回路の機能を説明することができる。 | 2 | |
| 組合せ論理回路を設計することができる。 | 2 | |
| フリップフロップなどの順序回路の基本素子について、その動作と特性を説明することができる。 | 2 | |
| レジスタやカウンタなどの基本的な順序回路の動作について説明できる。 | 2 | |
| 与えられた順序回路の機能を説明することができる。 | 2 | |
| 順序回路を設計することができる。 | 2 | |
| コンピュータを構成する基本的な要素の役割とこれらの間でのデータの流れを説明できる。 | 2 | |
| プロセッサを実現するために考案された主要な技術を説明できる。 | 2 | |
| メモリシステムを実現するために考案された主要な技術を説明できる。 | 2 | |
| 入出力を実現するために考案された主要な技術を説明できる。 | 2 | |
| コンピュータアーキテクチャにおけるトレードオフについて説明できる。 | 2 | |
| ハードウェア記述言語など標準的な手法を用いてハードウェアの設計、検証を行うことができる。 | 2 | |