【授業の目的】
情報科学の基礎知識として必要となる，各種のデータ構造とそれらに関連するアルゴリズムについて学習する．
【授業の到達目標】
(a)各種のデータ構造（線形構造、木構造、グラフ構造）を説明できる【知識・理解】
(b)基本的な探索法（縦型探索法、横型探索法）を説明できる【知識・理解】
(c)文字列照合の代表的なアルゴリズム（ＫＭＰ法）を説明できる【知識・理解】
(d)グラフの最短路問題の代表的なアルゴリズム（ダイクストラ法）を説明できる【知識・理解】
(e)解探索の代表的なアルゴリズム（Ａアルゴリズム）を説明できる【知識・理解】
(f)データ整列の代表的なアルゴリズム（ヒープソート法，クイックソート法）を説明できる【知識・理解】
(g)データ探索の代表的なアルゴリズム（ハッシュ法、ニ分探索木法）を説明できる【知識・理解】
【授業概要（キーワード）】
線形構造，木構造，グラフ構造，スタックと待ち行列，文字列照合，グラフの最短路問題，解の探索，データ整列，データ探索
【科目の位置付け】
本科目は，学科のディプロマポリシーの3(1)「情報科学と電気・電子通信工学の基礎知識を身につけ，それを応用する能力を身につけている」の前半部（基礎知識を身に付ける）に対応する．
本科目と関連が深い科目：プログラミング言語，データベース論，計算理論，計算機基礎，プログラミング演習Ⅰ～Ⅲ
【授業計画】
・授業の方法
講義形式で行う．毎回15分～20分間でその時間内に学んだ内容の演習問題を解いてもらう．
原則対面で行うが，新型コロナウィルスの感染状況等によってはZoomによるオンライン授業に変更する場合もある．
・日程
第１回 ガイダンス，データ構造とアルゴリズムの基礎
第２回 線形構造
第３回 スタックと待ち行列，基本的な探索法
第４回 文字列照合（単純照合法、KMP法）
第５回 文字列照合（KMP法）
第６回 木構造
第７回 グラフ構造
第８回 中間試験と解説
第９回 グラフの最短路問題（ダイクストラ法など）
第１０回 解の探索（Aアルゴリズムなど）
第１１回データ整列（ヒープソート法など）
第１２回 データ整列（クイックソート法など）
第１３回 データ探索（ハッシュ法など）
第１４回 データ探索（ニ分探索木法など）
第１５回 期末試験と解説
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
欠席や遅刻をすると授業内容が分からなくなるので必ず遅刻せずに出席すること．
私語など他の受講生の迷惑となる行為は行わないこと．受け身にならず積極的な受講を期待する．
・授業時間外学習（予習・復習）のアドバイス
予習として，講義資料をWebClassで公開するので，事前に読んでくるとともに疑問点をノートに書きだしてくる(30分程度)．
復習として，演習問題をもう一度解いてみるとともに講義で出てきたアルゴリズムを実際にC言語を用いてプログラミングするのが望ましい(30分程度)．
【成績の評価】
・基準
授業に2/3以上出席することを前提に（満たない場合は0点）、授業の到達目標に記載した各項目を総合的に評価して，総合点で６０点以上を合格とする．
・方法
中間試験（30点），期末試験（30点）の配点で成績評価をする．それ以外の演習課題（レポート）（40点）
なお，新型コロナウイルスの感染状況等によっては試験の代わり中間レポート，期末レポートに変更する場合もある．
【テキスト・参考書】
講義開始前にwebclass上にテキストをアップロードするため、必ずwebclassに登録する。
必要に応じて、プリントアウトするかダウンロードする。
1. データ構造とアルゴリズム、斎藤信男・西原清一 著、コロナ社、2800円(1998）
2. Cで学ぶデータ構造とアルゴリズム、西原清一 著、オーム社、2600円(2008)
3. アルゴリズムとデータ構造、原 隆浩 他著、共立出版、2400円(2012)
【その他】
・学生へのメッセージ
講義の前後に予習，復習をしっかりやり，受け身にならず積極的な受講を期待する．
・オフィス・アワー
毎週月曜日 15:00～16:00 相談場所：工学部8号館8-112号室．質問は，WebClassのメッセージ機能でも受け付ける．
|