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

授業項目

時間

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

ガイダンス
1
本科目の概要,授業方針,評価方法等について紹介する.
ソート(整列)
5
バブルソート,クイックソート,マージソートアルゴリズムについて理解でき,プログラムを組める.また,そのほかソート方法や,ソートアルゴリズムの性能を分析方法について理解できる.
サーチ
4
線形探索(リニアサーチ),バイナリサーチ,自己組織化探索などについて理解と実装できる.
リスト
2
配列によるまたはポインタによる連結リストの実装方法について理解し,リストにおける線形探索及び自己組織化探索の実装できる.
スタック,キュー,リング
4
スタック,キュー,リングの概念,配列と連結リストを用いるスタックとキューの作成,挿入と削除操作を理解できる.
アルゴリズム計算量の評価方法
6
計算量の評価基準と記法を理解し,オーダー記法の求め方及びそれを利用したアルゴリズム時間計算量の評価を説明できる(英文教材を利用する).
ハッシュ法
6
ハッシュ法の概念を理解し,ハッシュ関数の設計方法を説明できる.ハッシュ法における衝突を解消する仕組み,内部ハッシングと外部ハッシングアルゴリズムの設計と実装法を理解し,それぞれのプログラムを組める.
木構造(ツリー構造)
10
木構造の概念と構成,深さ優先探索について理解できる.2分木と2分探索木の概念を理解し,その構成と挿入・削除,探索操作の実装法について説明できる.
グラフ構造
4
グラフの概念と応用例を理解できる.隣接行列,接続行列,隣接リストを用いたグラフの表現法を応用できる.
再帰法とグラフ探索アルゴリズム(DFS,BFS)
8
再帰法の仕組みと応用について理解できる。試行錯誤の概念,バックトラック法と再帰,グラフの深さ優先探索(DFS)と幅優先探索(BFS)について理解でき,GUIを用いるDFSとBFSプログラムを組める.
動的計画法(DP)と最短経路問題
4
動的計画法の考え方と仕組み,動的計画法を扱うと解きやすい問題の条件について理解できる.動的計画法を用いて最短経路問題を解くプログラムを組める.
貪欲法と最大スパニング木問題
4
貪欲法の考え方と仕組み,貪欲法を扱うと解きやすい問題の条件について理解できる.貪欲法を用いて最大スパニング木問題を解くプログラムを組める.
まとめ
2
データ構造とアルゴリズムの設計法と実践について理解できる。
評価方法及び総合評価【評価方法】定期試験の筆記試験と実技試験,小テストや演習により評価する.【総合評価】本科目は学修科目であるため,学習の各段階において自学学習用の課題を設け,学習の成果を定期試験等筆記試験や実技試験,小テストと演習を総合し評価する.実技試験または演習レポートの提出期限は課題提示と同時に示し,期限に遅れて提出されたレポートに対し減点する.60%以上の得点率で目標達成とみなす.
学習方法本科目は,計算機科学及び情報管理に関する基礎的な科目である.より効率の良いプログラムを書くために理解しておかねばならない必要な知識でもある.3年次のプログラミング言語,4年次のプログラミング特論と関連する.この科目の講義内容について十分に復習して受講することが望まれる.
学生へのメッセージ資格試験や編入学・就職試験にも役立つ知識であるため,理論だけではなく,実際に学んだデータ構造とアルゴリズムを実装してみることも重要ですので,プログラミングの実力もつけてもらいたい.
学修単位への対応本科目は60時間の授業に対して,放課後・家庭で40時間程度の自学学習が課せられます.
本校教育目標との対応
(2)
JABEE学習教育目標との対応
D-1(◎)