| 科目コード | AN214 | ||||
| 科目名 | アルゴリズム工学(Algorithm Engineering) | 単位数 | 2単位 | ||
| 対象学科 | 電子情報システム工学専攻 | 対象学年 | 2年 | 開講期間 | 前期 |
| 科目区分 | 情報制御系 | 必修・選択 | 選択 | 履修/学修 | 学修 |
| 授業形式 | 講義 | 規定授業時数 | 15 | ||
| 教員名（所属） | 山本 直樹（人間情報システム工学科） | 教員室 | 3号棟3階 | ||
| 使用教科書 | 上野修一、高橋篤司 「情報とアルゴリズム」 森北出版 | ||||
| 参考書 | 立花他 訳「グラフ理論への入門」 共立出版 浅野他 訳「アルゴリズムイントロダクション」 近代科学社 | ||||
| 科目の位置付けと 関連科目 | 関連科目は、情報処理、プログラム通論、データ構造とアルゴリズム、オペレーティングシステム、情報数学、離散数学、数値計算などである。 | ||||
| 科目の概要 | 本講義では、グラフとネットワークの概念、アルゴリズムの解析に関する基本的な概念、アルゴリズムの設計技法の概要について説明する。 | ||||
| 授業方針 | ①グラフとネットワークアルゴリズムの考え方と実現技法を応用できる。 ②アルゴリズムの解析に関する基本的な概念を理解し説明できる。 ③アルゴリズムの設計技法について応用できる。 ④プログラミング演習などを通してアルゴリズムの設計および実装ができる。 | ||||
授業項目 | 時数 | 達成目標（習得すべき内容） |
| 概説 (Outline of this subject) | アルゴリズム工学の授業の概要、学習の進め方、本科目の評価法などの全体的ガイダンスを行う。 | |
| グラフとその表現および木 (Basic of graph theory and properties of trees) | グラフの基本的な定義と行列表現について理解し、説明できる。全域木および２分木の特徴および性質について理解し、説明できる。 | |
| 各種グラフの特徴と性質 (Properties of graphs) | ２部グラフ、オイラーグラフ、ハミルトングラフの特徴および性質について理解し、説明できる。ハミルトングラフと関連する巡回セールスマン問題の解法を理解し、説明できる。 | |
| アルゴリズムの解析 (Analysis of algorithms) | 関数の漸近的評価手法を理解できる。計算量の観点からアルゴリズムおよびプログラムを評価できる。 | |
| グラフのアルゴリズム (Graph algorithms) | 探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを理解し、説明できる。これら標準的なアルゴリズムのデータ構造の設計及び構成について理解し、実行効率を考慮したプログラムが実装できる。 | |
| アルゴリズムの設計技法 (Outline of design techniques for algorithms) | 様々なアルゴリズムの位置づけと代表的なアルゴリズム設計技法の概要について理解し、説明できる。 |
ルーブリック | |||
評価項目 | 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| グラフとその表現および木 | グラフの基本的な定義と行列表現、全域木、２分木についてすべて説明でき、これらに関する問題を正しく解くことができる。 | グラフの基本的な定義と行列表現、全域木、２分木について説明でき、これらに関する問題を解くことができる。 | グラフの基本的な定義と行列表現、全域木、２分木について一部しか説明できず、これらに関する問題を解くことができない。 |
| 各種グラフの特徴と性質 | ２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題をすべて説明でき、これらに関する問題を正しく解くことができる。 | ２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を説明でき、これらに関する問題を解くことができる。 | ２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を一部分しか説明できず、これらに関する問題を解くことができない。 |
| アルゴリズムの解析 | 関数の漸近的評価手法をすべて説明でき、計算量の観点からアルゴリズムおよびプログラムを的確に評価できる。 | 関数の漸近的評価手法を説明でき、計算量の観点からアルゴリズムおよびプログラムを評価できる。 | 関数の漸近的評価手法を一部分しか説明できず、計算量の観点からアルゴリズムおよびプログラムを評価できない。 |
| グラフのアルゴリズム | 探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムをすべて説明でき、対象のネットワーク問題に対する実行効率を考慮したプログラムが実装できる。 | 探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを説明でき、対象のネットワーク問題に対するプログラムが実装できる。 | 探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを一部分しか説明できず、対象のネットワーク問題に対するプログラムが実装できない。 |
| 評価方法及び 総合評価 | 【評価方法】学期末試験、演習レポートで評価する。【総合評価】学期末試験（70%）、演習レポート（30%）を総合して評価し、60%以上の得点率で目標達成と見なす。演習レポートの提出期限は課題提示と同時に示し、期限に遅れて提出されたレポートの評価点は0点となるので注意すること。 |
| 学習方法 | |
| 学生への メッセージ | 本授業では、一部英語の資料を用いたり、重要な用語は英語でも表記します。 |
| 学修単位への対応 | 1単位あたり30時間程度の自学自習が求められます。 |
| 本校教育目標との対応 | JABEE学習教育目標との対応 | ||||