2015年度シラバス（熊本高等専門学校　熊本キャンパス）				科目コード	HI407
科目名	データ構造とアルゴリズム(Data Structure and Algorithms)			単位数	2単位
対象学科	人間情報システム工学科	対象学年	4	開講期間	通年
科目区分	専門基礎科目	必修・選択	必修	履修/学修	学修
授業形式	講義	規定授業時数（単位時間）	60
教員名（所属）	孫寧平（人間情報システム工学科）		教員室	3号棟2階
使用教科書	紀平拓男，春日伸弥，アルゴリズムとデータ構造，SoftBank Creative
参考書	茨木俊秀，Cによるアルゴリズムとデータ構造
科目の位置付けと関連科目	３年次のプログラミング言語,　4年次,　5年次のソフトウェア系科目と関連する．また，情報技術者資格試験や進学，就職試験などと関連する．
科目の概要	データ構造とアルゴリズムはコンピュータ・サイエンスの根幹を成すものであり,プログラミング技法を学ぶにおいて最も重要となる概念である．本講義は基本のデータ構造としてのリスト，スタックとキュー，木構造，グラフ構造などの構成と，これらのデータ構造における整列と探索アルゴリズムについて学ぶ．また，ハッシュ法，自己組織リスト検索，再帰法、動的計画法など実用性の高いアルゴリズムの設計及びその応用を取り上げる. プログラミングの基礎を踏まえてデータ構造とアルゴリズム設計の手順や手法と、アルゴリズム時間計算量の解析法とオーダーの求め方などを学んで行く.
授業方針	１．自力で基本なデータ構造とアルゴリズムの設計及び実装することができる.２．探索と整列のアルゴリズムの考え方について理解しそのプログラムを作成できる.３．ハッシュ法，再帰法，動的計画法，貪欲法の考え方について理解できる.簡単な応用例をプログラミングできる.４．アルゴリズム時間計算量の解析方法とオーダーの求め方について理解できる。

授業項目	時数	達成目標（習得すべき内容）
ガイダンス	1	本科目の概要，授業方針，評価方法等について紹介する．
ソート（整列）とサーチ(探索)	9	バブルソート，クイックソート，マージソートアルゴリズムについて理解でき，プログラムを組める．また，そのほかソート方法や，ソートアルゴリズムの性能を分析方法について理解できる．線形探索（リニアサーチ），バイナリサーチ，自己組織化探索などについて理解と実装できる．
リスト,スタック，キュー，リング	6	配列によるまたはポインタによる連結リストの実装方法について理解し，リストにおける線形探索及び自己組織化探索の実装できる．スタック，キュー，リングの概念，配列と連結リストを用いるスタックとキューの作成，挿入と削除操作を理解できる．
アルゴリズム計算量の評価方法	6	計算量の評価基準と記法を理解し，オーダー記法の求め方及びそれを利用したアルゴリズム時間計算量の評価を説明できる（英文教材を利用する）．
ハッシュ法	6	ハッシュ法の概念を理解し，ハッシュ関数の設計方法を説明できる．ハッシュ法における衝突を解消する仕組み，内部ハッシングと外部ハッシングアルゴリズムの設計と実装法を理解し，それぞれのプログラムを組める．
木構造（ツリー構造）	10	木構造の概念と構成，深さ優先探索について理解できる.２分木と２分探索木の概念を理解し，その構成と挿入・削除，探索操作の実装法について説明できる．
グラフ構造とグラフ探索アルゴリズム	12	グラフの概念と応用例を理解できる．隣接行列，接続行列，隣接リストを用いたグラフの表現法を応用できる．再帰法の仕組みと応用について理解できる。試行錯誤の概念，バックトラック法と再帰，グラフの深さ優先探索（DFS）と幅優先探索（BFS）について理解でき，GUIを用いるDFSとBFSプログラムを組める．
最短経路問題と最大スパニング木問題	10	動的計画法の考え方と仕組み，動的計画法を扱うと解きやすい問題の条件について理解できる．動的計画法を用いて最短経路問題を解くプログラムを組める．貪欲法の考え方と仕組み，貪欲法を扱うと解きやすい問題の条件について理解できる．貪欲法を用いて最大スパニング木問題を解くプログラムを組める．

ルーブリック
評価項目	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
代表的なアルゴリズムとしてのソート（整列）とサーチ(探索)について理解しているかどうかを,筆記試験と実技試験で評価する．　基本的なデータ構造としてのリスト,スタック，キュー，リングについてそれぞれの構成，実装法，性能評価について筆記試験で評価する．	バブルソート，クイックソート，マージソートアルゴリズムについてよく理解でき，自力でプログラムを組める．また，ソートアルゴリズムの性能を分析方法についてよく理解できる．線形探索（リニアサーチ），バイナリサーチ，自己組織化探索などについて理解と実装よくできる．　配列によるまたはポインタによる連結リストの実装方法についてよく理解し，リストにおける線形探索及び自己組織化探索の実装よくできる．スタック，キュー，リングの概念，配列と連結リストを用いるスタックとキューの作成，挿入と削除操作をよく理解できる．	バブルソート，クイックソート，マージソートアルゴリズムについて理解でき，自力でプログラムを組める．また，ソートアルゴリズムの性能を分析方法について理解できる．線形探索（リニアサーチ），バイナリサーチ，自己組織化探索などについて理解と実装できる．　配列によるまたはポインタによる連結リストの実装方法について理解し，リストにおける線形探索及び自己組織化探索の実装できる．スタック，キュー，リングの概念，配列と連結リストを用いるスタックとキューの作成，挿入と削除操作を理解できる．	バブルソート，クイックソート，マージソートアルゴリズムについて理解できなく，自力でプログラムを組めない．また，ソートアルゴリズムの性能を分析方法について理解できない．線形探索（リニアサーチ），バイナリサーチ，自己組織化探索などについて理解と実装できない．　配列によるまたはポインタによる連結リストの実装方法について理解していない．リストにおける線形探索及び自己組織化探索の実装できない．スタック，キュー，リングの概念，配列と連結リストを用いるスタックとキューの作成，挿入と削除操作を理解できない．
アルゴリズム計算量の評価方法について理解しているかどうかを，演習課題の完成度と筆記試験による評価する．　ハッシュ法について，演習と実技試験で評価する．	計算量の評価基準と記法をよく理解し，オーダー記法の求め方及びそれを利用したアルゴリズム時間計算量の評価を詳細に説明できる．英文教材を読解できる．　ハッシュ法の概念をよく理解し，ハッシュ関数の設計方法を詳細に説明できる．ハッシュ法における衝突を解消する仕組み，内部ハッシングと外部ハッシングアルゴリズムの設計と実装法をよく理解し，それぞれのプログラムをよく組める．	計算量の評価基準と記法を理解し，オーダー記法の求め方及びそれを利用したアルゴリズム時間計算量の評価を説明できる．　ハッシュ法の概念を理解し，ハッシュ関数の設計方法を説明できる．ハッシュ法における衝突を解消する仕組み，内部ハッシングと外部ハッシングアルゴリズムの設計と実装法を理解し，それぞれのプログラムを組める．	計算量の評価基準と記法を理解していない．オーダー記法の求め方及びそれを利用したアルゴリズム時間計算量の評価を説明できない．　ハッシュ法の概念を理解できない．ハッシュ関数の設計方法を説明できない．ハッシュ法における衝突を解消する仕組み，内部ハッシングと外部ハッシングアルゴリズムの設計と実装法を理解できない．それぞれのプログラムを組めない．
木構造（ツリー構造），2分木，2分探索木についての理解を小テストと筆記試験で評価する．	構造の概念と構成，深さ優先探索についてよく理解できる.２分木と２分探索木の概念をよく理解し，その構成と挿入・削除，探索操作の実装法について詳細に説明できる．	構造の概念と構成，深さ優先探索について理解できる.２分木と２分探索木の概念をよ理解し，その構成と挿入・削除，探索操作の実装法について説明できる．	構造の概念と構成，深さ優先探索について理解できない.２分木と２分探索木の概念をよ理解していない．その構成と挿入・削除，探索操作の実装法について説明できない．
グラフ構造とグラフ探索アルゴリズムの理解について，演習小テストと実技試験で評価する．　最短経路問題と最大スパニング木問題の理解について，実技試験で評価する．	グラフの概念と応用例をよく理解できる．隣接行列，接続行列，隣接リストを用いたグラフの表現法をよく応用できる．再帰法の仕組みと応用についてよく理解できる。試行錯誤の概念，バックトラック法と再帰，グラフの深さ優先探索（DFS）と幅優先探索（BFS）についてよく理解でき，GUIを用いるDFSとBFSプログラムをよく組める．　動的計画法の考え方と仕組み，動的計画法を扱うと解きやすい問題の条件についてよく理解できる．最短経路問題を解くプログラムをGUIを用いて組める．貪欲法の考え方と仕組み，貪欲法を扱うと解きやすい問題の条件について理解よくできる．最大スパニング木問題を解くプログラムをGUIを用いて組める．	グラフの概念と応用例を理解できる．隣接行列，接続行列，隣接リストを用いたグラフの表現法を応用できる．再帰法の仕組みと応用について理解できる。試行錯誤の概念，バックトラック法と再帰，グラフの深さ優先探索（DFS）と幅優先探索（BFS）について理解でき，DFSとBFSプログラムを組める．　動的計画法の考え方と仕組み，動的計画法を扱うと解きやすい問題の条件について理解できる．最短経路問題を解くプログラムをGUIを用いて組める．貪欲法の考え方と仕組み，貪欲法を扱うと解きやすい問題の条件について理解できる．最大スパニング木問題を解くプログラムを組める．	グラフの概念と応用例を理解できない．隣接行列，接続行列，隣接リストを用いたグラフの表現法を応用できない．再帰法の仕組みと応用について理解できない。試行錯誤の概念，バックトラック法と再帰，グラフの深さ優先探索（DFS）と幅優先探索（BFS）について理解できない．DFSとBFSプログラムを組めない．　動的計画法の考え方と仕組み，動的計画法を扱うと解きやすい問題の条件について理解できない．最短経路問題を解くプログラムをGUIを用いて組めない．貪欲法の考え方と仕組み，貪欲法を扱うと解きやすい問題の条件について理解できない．最大スパニング木問題を解くプログラムを組めない．

評価方法及び総合評価	【評価方法】定期試験の筆記試験と実技試験，小テストや演習により評価する．【総合評価】本科目は学修科目であるため，学習の各段階において自学学習用の課題を設け，学習の成果を定期試験等筆記試験や実技試験，小テストと演習を総合し評価する．実技試験または演習レポートの提出期限は課題提示と同時に示し，期限に遅れて提出されたレポートに対し減点する．60%以上の得点率で目標達成とみなす．
学習方法	本科目は，計算機科学及び情報管理に関する基礎的な科目である.より効率の良いプログラムを書くために理解しておかねばならない必要な知識でもある．３年次のプログラミング言語,4年次のプログラミング特論と関連する．この科目の講義内容について十分に復習して受講することが望まれる．
学生へのメッセージ	資格試験や編入学・就職試験にも役立つ知識であるため，理論だけではなく，実際に学んだデータ構造とアルゴリズムを実装してみることも重要ですので，プログラミングの実力もつけてもらいたい．
学修単位への対応	90分の授業に対して放課後・家庭で90分程度の自学自習が求められます．

本校教育目標との対応

(2)

JABEE学習教育目標との対応

D-1(◎)