| 英文名 | Algorithm | |
|---|---|---|
| 科目概要 | データサイエンス学科２年後期、３群科目、必修、講義、2単位 | |
| 科目責任者 | 榊原 康文 | |
| 担当者 | (※は実務経験のある教員) 榊原 康文※、 鎌田 真由美、 秋山 真那斗 | |
| 講義室 | ||
| 科目 | 教科及び教科の指導法に関する科目（高等学校 情報） |
|---|---|
| 各科目に含めることが必要な事項 |
|
データ解析などの実際の仕事を行うためのプログラムを書くためには、問題を解決するための手順を正確に記述して、それをプログラムに書き下す必要がある。この問題を解決するための手順には、いくつかの定石があり、その定石を組み合わせることにより、上質なプログラムを完成させることができる。計算機科学において、この定石はアルゴリズムと呼ばれている。本講義では、アルゴリズムの基礎知識と考え方を学ぶ。
データ構造の設計からはじめて、いくつかの代表的なアルゴリズム、ソーティング、グラフ探索、などを学び、いくつかのアルゴリズムスキーマについても学ぶ。さらに、計算理論についても学ぶ。
教科書を指定し、その内容について理解を深めるためにパワーポイントや板書による講義形式で進める。また、数回程度の演習を行い、アルゴリズムの知識と考え方の定着を図る。
演習課題等のフィードバックは、次回講義や講義のWEBページ等で共有する。
DP5
| 回 | 項目 | 内容 | 担当者 | 日時 |
|---|---|---|---|---|
| 1 | イントロダクション | アルゴリズムの概論について、計算モデル、バブルソート、基数ソート、計算量との関連性を含め講義する。 | 榊原 康文 秋山 真那斗 | 9/10③ |
| 2 | 効率的ソートアルゴリズム（１） | ソート問題を効率的に解くマージソートについて講義する。 | 榊原 康文 秋山 真那斗 | 9/17③ |
| 3 | 効率的ソートアルゴリズム（２） | ソート問題を効率的に解くクイックソートについて、分割統治法を含め講義する。 | 榊原 康文 秋山 真那斗 | 9/24③ |
| 4 | 効率的ソートアルゴリズム（３） | ソート問題を効率的に解くヒープソートについて、２分木とヒープのデータ構造との関連性を含め講義する。 | 榊原 康文 秋山 真那斗 | 10/1③ |
| 5 | ソートアルゴリズムの演習 | ここまで勉強してきたソートアルゴリズムについて、マージソート、クイックソート、ヒープソートの例題を解く演習を行う。 | 榊原 康文 秋山 真那斗 | 10/8③ |
| 6 | グラフのデータ構造 | グラフのデータ構造について、隣接行列、接続行列、深さ優先と幅優先探索との関連性を含め講義する。 | 榊原 康文 秋山 真那斗 | 10/15③ |
| 7 | グラフの連結成分と分解 | グラフの連結成分と分解について、最小全域木問題との関連性を含め講義する。 | 榊原 康文 秋山 真那斗 | 10/22③ |
| 8 | 最短経路問題 | 最短経路問題を効率的に解くダイクストラのアルゴリズムについて講義する。 | 榊原 康文 秋山 真那斗 | 10/29③ |
| 9 | グラフアルゴリズムの演習 | ここまで勉強してきたグラフアルゴリズムについて、グラフの探索、連結成分の検出、最短経路の例題を解く演習を行う。 | 榊原 康文 秋山 真那斗 | 11/12③ |
| 10 | 文字列処理（１） | 文字列処理について、文字列のデータ構造、パターンマッチングを含め講義する。 | 鎌田 真由美 | 11/19③ |
| 11 | 文字列処理（２） | 文字列処理について、効率的パターンマッチング（KMP法，BM法）を含め講義する。 | 鎌田 真由美 | 11/26③ |
| 12 | 文字列処理の演習 | ここまで勉強してきた文字列処理について、パターンマッチングの例題を解く演習を行う。 | 鎌田 真由美 | 12/3③ |
| 13 | 計算理論の基礎（１） | 計算理論の基礎について、有限オートマトンとの関連性を含め講義する。 | 鎌田 真由美 | 12/10③ |
| 14 | 計算理論の基礎（２） | 計算理論の基礎について、チューリングマシンとの関連性を含め講義する。 | 鎌田 真由美 | 12/17③ |
| 15 | 計算理論の基礎（３） | 計算理論の基礎について、計算可能、NP問題との関連性を含め講義する。 | 鎌田 真由美 | 12/24③ |
アルゴリズムを組み合わせることにより、上質なプログラムを完成させることができるようになる。
期末試験（70％）と演習課題（30％）の結果から総合的に評価する。
【講義時間外に必要な学修時間：60時間】
予習：講義中に事前に指定する次回講義内容について教科書を読み、疑問点を明らかにしておくこと。
復習：教科書の章末の問題について解答を作成し、講義後に配布する模範解答と比較・検討する。
計算機科学の本質の理解とセンスを身につけてもらうことを目指します。
【科目ナンバリング：FU301-MT02】
【関連科目：情報の基礎、プログラミングⅡ】
（榊原）企業研究所での情報工学・第五世代コンピュータ開発経験をもとに、プログラムを作成する作法としてのアルゴリズムの基礎から応用例までを解説する。
| 種別 | 書名 | 著者・編者 | 発行所 |
|---|---|---|---|
| 教科書 | アルゴリズム データ構造 計算論 | 横森貴 | サイエンス社 |
| 参考書 | オートマトン・言語理論 ［第2版］ | 富田悦次、横森貴 | 森北出版 |