概要:
アルゴリズムは情報工学や情報科学を学ぶ上で基礎となる重要な科目の一つである.
本講義では基本的なデータ構造,ならびに,探索やソーティングに関する基本的なアルゴリズムの特性を学び,当該アルゴリズムを習得する.
授業の進め方・方法:
授業の進行にはスライドやプリント,学習用ソフトを使用した講義とする.
適宜実践演習やレポート課題を課し,学習内容の定着と理解度の向上を図る.
注意点:
【成績評価の基準・方法】
試験の成績80 %,課題の成績20 %の割合で総合的に評価する.学年の評価は前学期末の評価とする.技術者が身につけるべき専門基礎として,上記の到達目標に対する達成度を試験等において評価する.
【履修上の注意】
この科目を履修するにあたり,2年生科目の「プログラミング基礎」の内容を十分に理解しておくこと.
2週目までに,講義に使用するパソコン上に,C言語を実装できる環境を構築しておくこと.
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
アルゴリズムの計算量 |
アルゴリズムのフローチャートから オーダ記法による計算量を算出できる
|
2週 |
データ構造「リスト①」 |
リストに対する 値の追加・削除・入れ替えによって データがどのように更新されるか説明できる
|
3週 |
データ構造「リスト②」 |
配列を応用したリストに対して 値の追加・削除・入れ替えを実装できる
|
4週 |
データ構造「スタック,キュー」 |
スタックとキューの特徴を説明できる
|
5週 |
アルゴリズム「探索」 |
探索アルゴリズムの「逐次探索法」を実装でき 「2分探索法」を再起呼び出しを含むフローチャートで説明できる
|
6週 |
アルゴリズム「ソート①」 |
ソートアルゴリズムである「選択法」と「挿入法」「クイックソート」を説明できる
|
7週 |
アルゴリズム「ソート②」 |
ソートアルゴリズムである「選択法」と「挿入法」を実装できる
|
8週 |
中間試験 |
第1週~第7週の学習内容について試験を行い 到達度を判定する
|
2ndQ |
9週 |
試験返却・解説 アルゴリズム「ソート③」 |
「バブルソート」など ソーティングには複数のアルゴリズムがあることを理解する
|
10週 |
データ構造「ポインタと構造体」 |
C言語のポインタや構造体を使うなどすることで リストや木構造 グラフなどのデータ構造を実装できることを理解する
|
11週 |
データ構造「木構造」 |
2分探索木の構造を理解し「深さ優先探索」「幅優先探索」の違いを説明できる
|
12週 |
データ構造「グラフ」 |
グラフの構造を理解し「ダイクストラ法」を説明できる
|
13週 |
データ構造「リスト③」 |
ポインタと構造体を使って リストを実装できる
|
14週 |
プログラミング演習「スタック,キュー」 |
ポインタと構造体を使って スタックとキューを実装できる
|
15週 |
プログラミング演習「探索,ソート」 |
ポインタと構造体が使われたリストに対して 「選択法」を実装できる
|
16週 |
|
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
基礎的能力 | 工学基礎 | 情報リテラシー | 情報リテラシー | 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。 | 4 | 前1,前5,前6,前7,前9,前11,前12,前15 |
与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。 | 4 | 前5,前6,前7,前9,前11,前12 |
任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。 | 4 | 前5,前7,前9,前15 |
専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 代入や演算子の概念を理解し、式を記述できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
変数の概念を説明できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
データ型の概念を説明できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
制御構造の概念を理解し、条件分岐を記述できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
制御構造の概念を理解し、反復処理を記述できる。 | 3 | 前3,前4,前7,前13,前14,前15 |
与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 4 | 前3,前4,前7,前14,前15 |
与えられたソースプログラムを解析し、プログラムの動作を予測することができる。 | 4 | 前3,前4,前7,前14,前15 |
ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | 前1 |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | 前5,前6,前7,前9,前15 |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | 前1,前5,前6,前7,前9 |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | 前5,前6,前7,前9,前15 |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | 前1,前5,前6,前7,前9,前15 |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | 前1,前5,前6,前7,前9,前15 |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | 前2,前4,前10,前11,前12,前14 |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 前1,前11 |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | 前2,前4,前11,前14 |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | 前3,前4,前14 |
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | 前1,前6,前7,前9 |
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | 前1,前6,前7,前9 |
情報数学・情報理論 | コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。 | 4 | 前10 |