![]() ![]() |
講義概要/Course Information |
科目基礎情報/General Information |
授業科目名 /Course title (Japanese) |
アルゴリズム論第二 | ||
---|---|---|---|
英文授業科目名 /Course title (English) |
Algorithms Ⅱ | ||
科目番号 /Code |
COM503c COM503d | ||
開講年度 /Academic year |
2021年度 | 開講年次 /Year offered |
3 |
開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
科目区分 /Category |
専門科目 | ||
開講類・専攻 /Cluster/Department |
Ⅰ類 | ||
担当教員名 /Lecturer(s) |
小林 聡 | ||
居室 /Office |
西9-735 | ||
公開E-mail |
kobayashi.satoshi@uec.ac.jp | ||
授業関連Webページ /Course website |
今回は使用しません ★★その他の項目の遠隔授業情報を参照すること★★ | ||
更新日 /Last update |
2021/03/07 23:26:24 | 更新状況 /Update status |
公開中 /now open to public |
講義情報/Course Description |
主題および 達成目標(2,000文字以内) /Themes and goals(up to 2,000 letters) |
コンピュータ技術,情報通信技術の進歩とともに, ハードウエアを動かすためのソフトウエア/アルゴリズムの 理論の重要性が認識されている.画像データの圧縮技術や 情報を安全に送信するための暗号化技術,DNA 配列に 符号化されている遺伝情報の解析など,非常に広範な分野で アルゴリズムの理論が研究され,実用化されている. 本講義では,アルゴリズム論における基礎的な問題を題材として, 効率の良いアルゴリズムを設計するための理論・技術を学ぶ. より具体的には,以下を達成目標とする. 1) 講義で取り扱う各基礎問題に対するアルゴリズムの動作と 正当性およびその計算量の解析結果を理解する. 2) 講義で紹介する貪欲算法や動的計画法に代表される アルゴリズムの設計手法の原理を理解する. |
---|---|
前もって履修 しておくべき科目(1,000文字以内) /Prerequisites(up to 1,000 letters) |
プログラミング通論,アルゴリズム論第一 |
前もって履修しておくこ とが望ましい科目(1,000文字以内) /Recommended prerequisites and preparation(up to 1,000 letters) |
特になし |
教科書等(1,000文字以内) /Course textbooks and materials(up to 1,000 letters) |
資料を配付する.参考書として, 情報工学ライブラリ アルゴリズムとデータ構造 藤田聡 数理工学社 アルゴリズム(Algorithms in C) 第1-3巻, R.セジウィック,近代科学社 を挙げておく. |
授業内容と その進め方(2,000文字以内) /Course outline and weekly schedule(up to 2,000 letters) |
(a) 授業内容 できるだけ多くのトピックを選んで, 応用上役に立つアルゴリズムの設計手法について講義する. 第1回:グラフアルゴリズム(1):最小全域木問題等 第2回:グラフアルゴリズム(2):最短経路問題等 第3回:動的計画法の適用例(1):オートマトンから正則表現への変換 第4回:動的計画法の適用例(2):文脈自由文法の認識問題 第5回:動的計画法の適用例(3):文脈自由文法の認識問題における再帰構造の導出 第6回:動的計画法の適用例(4):隠れマルコフモデルとは 第7回:動的計画法の適用例(5):隠れマルコフモデルの認識問題 第8回;動的計画法の適用例(6):隠れマルコフモデルの認識アルゴリズム 第9回:動的計画法の適用例(7):近似文字列照合問題 第10回:KMPアルゴリズムにおける失敗関数の計算 第11回:KMPアルゴリズムにおけるオートマトンの構成アルゴリズム 第12回:その他のアルゴリズム 第13回:NP完全・NP困難性とは 第14回:NP困難問題に対する分枝限定法の理論 第15回:NP困難問題に対する近似アルゴリズムの理論 (b)授業の進め方 講義では,各問題の背景と動機を説明した後, アルゴリズムを導入し,その正当性の 証明と計算量の解析を与える. |
実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
授業時間外の学習 (予習・復習等)(1,000文字以内) /Preparation and review outside class(up to 1,000 letters) |
予習・復習は十分に行い, できればアルゴリズムの実装などもして欲しい。 |
成績評価方法 および評価基準 (最低達成基準を含む) (1,000文字以内) /Evaluation and grading (up to 1,000 letters) |
(a) 成績評価方法 期末試験の成績により判断する.指定された事項に関する レポートや演習・小試験の評価を含める場合もある. (b) 評価基準 達成目標で述べた1)と2)の達成度が一定の水準以上であれば合格とする. |
オフィスアワー: 授業相談(1,000文字以内) /Office hours(up to 1,000 letters) |
適宜相談に応じるが,メールなどで事前にアポイントを取ること. |
学生へのメッセージ(1,000文字以内) /Message for students(up to 1,000 letters) |
紹介したアルゴリズムを単に実装できるようになるだけでなく, 計算効率を上げるためにどのような工夫がされているか, なぜ正しく動くのかを「理解」してほしい. |
その他 /Others |
特になし |
キーワード /Keywords |
アルゴリズム,計算量,グラフ,最短路,動的計画法,文字列照合,文法,隠れマルコフモデル,NP完全,NP困難,分枝限定法,近似アルゴリズム |