山梨大学電子シラバス>検索結果一覧>授業データ



授業科目名 アルゴリズムとデータ構造I
時間割番号 TCS207
担当教員名 豊浦 正広
開講学期・曜日・時限 前期・水・II 単位数 2
<対象学生>
(未登録)
<授業の目的>
幅広い分野で応用される基本的なデータ構造とアルゴリズムについて、原理、性能、実装法を学び、実際の問題に適切に適用できるようにする。扱うトピックは、プラオリティキュー、ハッシュ表、平衡木、グラフアルゴリズム(最小スパニング木、最短経路、クリティカルパス)、文字列照合である。動的プログラミングの考え方と適用例についても学ぶ。
<本授業科目による獲得・涵養が特に期待されるコンピテンシー>(能力・資質)
工学部(~2023年度入学生)>コンピュータ理工学科向け
記号コンピテンシー(能力・資質) 
CS-A専門6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。6a.解決すべき問題を形式化することができる。
CS-B6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。
<到達目標>  到達目標とは
目標NO説明コンピテンシーとの対応
CS
1各種探索アルゴリズムの原理と特徴を説明でき、適切に選択、実装できる。CS-A
2最小スパニング木問題、最短経路問題、クリティカルパス問題の意味と応用例を理解し、適切なアルゴリズムを用いて実装できる。CS-B
3動的プログラミングの考え方と簡単な適用例を説明できる。CS-A
<成績評価の方法>
目標No割合評価の観点
150%中間試験と授業中に課す小課題で評価する
230%期末試験と授業中に課す小課題で評価する
320%期末試験と授業中に課す小課題で評価する
合計100% 
<授業の方法>
プログラミング基礎、プログラミング応用の知識とスキルを前提とする。
<受講に際して・学生へのメッセージ>
演習科目との連携を重視する。
<テキスト>
  1. 電子情報通信学会編 ; 岩沼宏治,美濃英俊,鍋島英知,山本泰生 著, データ構造とアルゴリズム, コロナ社, ISBN:9784339018233,
    (電子情報通信レクチャーシリーズ / 電子情報通信学会編, B-8)
<参考書>
  1. きたみりゅうじ著, キタミ式イラストIT塾基本情報技術者 令和06年, 技術評論社, ISBN:9784297138073
<授業計画の概要>
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タイトル最終評価とまとめ
事前学習
事後学習
これまでの内容を復習し,前年度以前の問題例を参考にして,最終評価の対策を行う.
最終評価の振り返りを行う.
授業内容最終評価とまとめ
<前年度授業に対する改善要望等への対応>
教科書の内容に準じて授業を展開します.教員が教科書の内容を?み砕いて,スライドであえて穴埋めとしている部分まですべて解答を示すことが,必ずしも受講者のためになるとは考えていません.教科書を(はじめとして後続の書籍や論文についても)自身で読み解くことを養成することを目指します.しばらく考えてからやはり理解できないという場合には,教員にぜひ質問をしてください.
<備考>
(未登録)