授業科目名	アルゴリズムとデータ構造I
時間割番号	TCS207
担当教員名	豊浦　正広
開講学期・曜日・時限	前期・水・I	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
幅広い分野で応用される基本的なデータ構造とアルゴリズムについて、原理、性能、実装法を学び、実際の問題に適切に適用できるようにする。扱うトピックは、プラオリティキュー、ハッシュ表、平衡木、グラフアルゴリズム(最小スパニング木、最短経路、クリティカルパス)、文字列照合である。動的プログラミングの考え方と適用例についても学ぶ。
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>コンピュータ理工学科向け 記号 コンピテンシー（能力・資質）   CS-A 専門 6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。 6a.解決すべき問題を形式化することができる。 ○ CS-B 6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。 ◎
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 CS 1 各種探索アルゴリズムの原理と特徴を説明でき、適切に選択、実装できる。 CS-A 2 最小スパニング木問題、最短経路問題、クリティカルパス問題の意味と応用例を理解し、適切なアルゴリズムを用いて実装できる。 CS-B 3 動的プログラミングの考え方と簡単な適用例を説明できる。 CS-A
＜成績評価の方法＞
目標No 割合 評価の観点 1 50% 中間試験と授業中に課す小課題で評価する 2 30% 期末試験と授業中に課す小課題で評価する 3 20% 期末試験と授業中に課す小課題で評価する 合計 100%
＜授業の方法＞
プログラミング基礎、プログラミング応用の知識とスキルを前提とする。
＜受講に際して・学生へのメッセージ＞
演習科目との連携を重視する。
＜テキスト＞
岩沼宏治，美濃英俊，鍋島英知，山本泰生, データ構造とアルゴリズム, コロナ社, ISBN:978-4339018233
＜参考書＞
きたみりゅうじ, キタミ式イラストIT塾 基本情報技術者 令和03年, 技術評論社, ISBN:978-4297117818, (第16章プログラムの作り方)
＜授業計画の概要＞
1 タイトル 二分探索木 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書4.1章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 先行授業の復習，素朴な二分探索木の構成について 2 タイトル 平衡木 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書4.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 平衡二分探索木について 3 タイトル 優先度付きキュー 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書4.3章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 優先度付きキュー，ヒープソート，最近傍探索について 4 タイトル ハッシュ表(分離チェイン法) 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書5.1章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 分離チェイン法，ハッシュ関数について 5 タイトル ハッシュ表(開番地法) 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書5.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 開番地法，代替アドレスについて 6 タイトル ハッシュ表(ハッシュ表の拡大) 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書5.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 ハッシュ表の拡大について 7 タイトル 中間評価 事前学習 事後学習 これまでの内容を復習し，前年度以前の問題例を参考にして，中間評価の対策を行う． 中間評価の振り返りを行う． 授業内容 中間評価 8 タイトル グラフの概念、表現、探索 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書6.1章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 グラフの表現と探索について 9 タイトル 最小全域木 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書6.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 最小全域木問題とその解法について 10 タイトル 最短経路問題(ダイクストラ法) 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書6.3章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 最短経路問題とその解法であるダイクストラ法について 11 タイトル 最短経路問題(A*アルゴリズム) 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書6.3章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 最短経路問題とその解法であるA*アルゴリズムについて 12 タイトル トポロジカルソートとクリティカルパス問題 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書6.4章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 最長経路問題とトポロジカルソートについて 13 タイトル 文字列照合 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書7.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 文字列照合のための力まかせ法とBMアルゴリズムについて 14 タイトル 動的計画法 事前学習 事後学習 事前に配布するスライドを印刷し，ノートを作成できる準備をする． 教科書8.2章の内容に沿って展開される授業に対して，ノートに知識をまとめる． 授業内容 ナップサック問題と動的計画法について 15 タイトル 最終評価とまとめ 事前学習 事後学習 これまでの内容を復習し，前年度以前の問題例を参考にして，最終評価の対策を行う． 最終評価の振り返りを行う． 授業内容 最終評価とまとめ 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜備考＞
(未登録)