2015年度シラバス(熊本高等専門学校 熊本キャンパス)
科目コードAN214
科目名アルゴリズム工学(Algorithm Engineering) 単位数2単位
対象学科電子情報システム工学専攻対象学年2年開講期間前期
科目区分情報制御系必修・選択選択履修/学修学修
授業形式講義規定授業時数15  
教員名(所属)
山本 直樹(人間情報システム工学科)教員室
3号棟3階
使用教科書
上野修一、高橋篤司 「情報とアルゴリズム」 森北出版
参考書
立花他 訳「グラフ理論への入門」 共立出版
浅野他 訳「アルゴリズムイントロダクション」 近代科学社
科目の位置付けと
関連科目
関連科目は、情報処理、プログラム通論、データ構造とアルゴリズム、オペレーティングシステム、情報数学、離散数学、数値計算などである。
科目の概要本講義では、グラフとネットワークの概念、アルゴリズムの解析に関する基本的な概念、アルゴリズムの設計技法の概要について説明する。
授業方針@グラフとネットワークアルゴリズムの考え方と実現技法を応用できる。
Aアルゴリズムの解析に関する基本的な概念を理解し説明できる。
Bアルゴリズムの設計技法について応用できる。
Cプログラミング演習などを通してアルゴリズムの設計および実装ができる。

授業項目

時数

達成目標(習得すべき内容)

概説
(Outline of this subject)
0.5
アルゴリズム工学の授業の概要、学習の進め方、本科目の評価法などの全体的ガイダンスを行う。
グラフとその表現および木
(Basic of graph theory and properties of trees)
4
グラフの基本的な定義と行列表現について理解し、説明できる。全域木および2分木の特徴および性質について理解し、説明できる。
各種グラフの特徴と性質
(Properties of graphs)
3
2部グラフ、オイラーグラフ、ハミルトングラフの特徴および性質について理解し、説明できる。ハミルトングラフと関連する巡回セールスマン問題の解法を理解し、説明できる。
アルゴリズムの解析
(Analysis of algorithms)
2.5
関数の漸近的評価手法を理解できる。計算量の観点からアルゴリズムおよびプログラムを評価できる。
グラフのアルゴリズム
(Graph algorithms)
4
探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを理解し、説明できる。これら標準的なアルゴリズムのデータ構造の設計及び構成について理解し、実行効率を考慮したプログラムが実装できる。
アルゴリズムの設計技法
(Outline of design techniques for algorithms)
1
様々なアルゴリズムの位置づけと代表的なアルゴリズム設計技法の概要について理解し、説明できる。

ルーブリック

評価項目

理想的な到達レベルの目安

標準的な到達レベルの目安

未到達レベルの目安

グラフとその表現および木グラフの基本的な定義と行列表現、全域木、2分木についてすべて説明でき、これらに関する問題を正しく解くことができる。グラフの基本的な定義と行列表現、全域木、2分木について説明でき、これらに関する問題を解くことができる。グラフの基本的な定義と行列表現、全域木、2分木について一部しか説明できず、これらに関する問題を解くことができない。
各種グラフの特徴と性質2部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題をすべて説明でき、これらに関する問題を正しく解くことができる。2部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を説明でき、これらに関する問題を解くことができる。2部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を一部分しか説明できず、これらに関する問題を解くことができない。
アルゴリズムの解析関数の漸近的評価手法をすべて説明でき、計算量の観点からアルゴリズムおよびプログラムを的確に評価できる。関数の漸近的評価手法を説明でき、計算量の観点からアルゴリズムおよびプログラムを評価できる。関数の漸近的評価手法を一部分しか説明できず、計算量の観点からアルゴリズムおよびプログラムを評価できない。
グラフのアルゴリズム探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムをすべて説明でき、対象のネットワーク問題に対する実行効率を考慮したプログラムが実装できる。探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを説明でき、対象のネットワーク問題に対するプログラムが実装できる。探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを一部分しか説明できず、対象のネットワーク問題に対するプログラムが実装できない。
評価方法及び
総合評価
【評価方法】学期末試験、演習レポートで評価する。【総合評価】学期末試験(70%)、演習レポート(30%)を総合して評価し、60%以上の得点率で目標達成と見なす。演習レポートの提出期限は課題提示と同時に示し、期限に遅れて提出されたレポートの評価点は0点となるので注意すること。
学習方法 
学生への
メッセージ
本授業では、一部英語の資料を用いたり、重要な用語は英語でも表記します。
学修単位への対応1単位あたり30時間程度の自学自習が求められます。
本校教育目標との対応
 (2)
JABEE学習教育目標との対応
B-2(○)