シラバス参照

講義概要/Course Information
2020/04/28 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
アルゴリズム論第二
英文授業科目名
/Course title (English)
Algorithms Ⅱ
科目番号
/Code
COM503c COM503d
開講年度
/Academic year
2020年度 開講年次
/Year offered
3
開講学期
/Semester(s) offered
前学期 開講コース・課程
/Faculty offering the course
情報理工学域
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
Ⅰ類
担当教員名
/Lecturer(s)
小林 聡
居室
/Office
西9-735
公開E-Mail
/e-mail
kobayashi.satoshi@uec.ac.jp
授業関連Webページ
/Course website
http://www.comp.cs.uec.ac.jp/lectures/
更新日
/Last updated
2020/03/02 17:45:57 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
コンピュータ技術,情報通信技術の進歩とともに,
ハードウエアを動かすためのソフトウエア/アルゴリズムの
理論の重要性が認識されている.画像データの圧縮技術や
情報を安全に送信するための暗号化技術,DNA 配列に
符号化されている遺伝情報の解析など,非常に広範な分野で
アルゴリズムの理論が研究され,実用化されている.

本講義では,アルゴリズム論における基礎的な問題を題材として,
効率の良いアルゴリズムを設計するための理論・技術を学ぶ.
より具体的には,以下を達成目標とする.

1) 講義で取り扱う各基礎問題に対するアルゴリズムの動作と
   正当性およびその計算量の解析結果を理解する.
2) 講義で紹介する貪欲算法や動的計画法に代表される
   アルゴリズムの設計手法の原理を理解する.
前もって履修
しておくべき科目
/Prerequisites
プログラミング通論,アルゴリズム論第一
前もって履修しておくこ
とが望ましい科目
/Recommended prerequisites and preparation
特になし
教科書等
/Course textbooks and materials
資料を配付する.参考書として,

情報工学ライブラリ アルゴリズムとデータ構造 藤田聡 数理工学社

アルゴリズム(Algorithms in C) 第1-3巻,
R.セジウィック,近代科学社

を挙げておく.



授業内容と
その進め方
/Course outline and weekly schedule
(a) 授業内容

できるだけ多くのトピックを選んで,
応用上役に立つアルゴリズムの設計手法について講義する.

第1回:グラフアルゴリズム(1):最小全域木問題等
第2回:グラフアルゴリズム(2):最短経路問題等
第3回:動的計画法の適用例(1):オートマトンから正則表現への変換
第4回:動的計画法の適用例(2):文脈自由文法の認識問題
第5回:動的計画法の適用例(3):文脈自由文法の認識問題における再帰構造の導出
第6回:動的計画法の適用例(4):隠れマルコフモデルとは
第7回:動的計画法の適用例(5):隠れマルコフモデルの認識問題
第8回;動的計画法の適用例(6):隠れマルコフモデルの認識アルゴリズム
第9回:動的計画法の適用例(7):近似文字列照合問題
第10回:KMPアルゴリズムにおける失敗関数の計算
第11回:KMPアルゴリズムにおけるオートマトンの構成アルゴリズム
第12回:NP完全・NP困難とは
第13回:NP困難な問題の例
第14回:NP困難問題に対する分枝限定法の理論
第15回:NP困難問題に対する近似アルゴリズムの理論

(b)授業の進め方

講義では,各問題の背景と動機を説明した後,
アルゴリズムを導入し,その正当性の
証明と計算量の解析を与える.
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
予習・復習は十分に行い,
できればアルゴリズムの実装などもして欲しい。
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
(a) 成績評価方法

期末試験の成績により判断する.指定された事項に関する
レポートや演習・小試験の評価を含める場合もある.

(b) 評価基準

達成目標で述べた1)と2)の達成度が一定の水準以上であれば合格とする.
オフィスアワー:
授業相談
/Office hours
適宜相談に応じるが,メールなどで事前にアポイントを取ること.
学生へのメッセージ
/Message for students
紹介したアルゴリズムを単に実装できるようになるだけでなく,
計算効率を上げるためにどのような工夫がされているか,
なぜ正しく動くのかを「理解」してほしい.
その他
/Others
特になし
キーワード
/Keyword(s)
アルゴリズム,計算量,グラフ,最短路,動的計画法,文字列照合,文法,隠れマルコフモデル,NP完全,NP困難,分枝限定法,近似アルゴリズム