シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/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 |
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 配列に 符号化されている遺伝情報の解析など，非常に広範な分野で アルゴリズムの理論が研究され，実用化されている． 本講義では，アルゴリズム論における基礎的な問題を題材として， 効率の良いアルゴリズムを設計するための理論・技術を学ぶ． より具体的には，以下を達成目標とする． １) 講義で取り扱う各基礎問題に対するアルゴリズムの動作と 正当性およびその計算量の解析結果を理解する． ２) 講義で紹介する貪欲算法や動的計画法に代表される アルゴリズムの設計手法の原理を理解する． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
プログラミング通論，アルゴリズム論第一 |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
特になし |
| 教科書等 /Course textbooks and materials |
資料を配付する．参考書として， 情報工学ライブラリ アルゴリズムとデータ構造 藤田聡 数理工学社 アルゴリズム(Algorithms in C) 第１-３巻, R.セジウィック，近代科学社 を挙げておく． |
| 授業内容と その進め方 /Course outline and weekly schedule |
(a) 授業内容 できるだけ多くのトピックを選んで， 応用上役に立つアルゴリズムの設計手法について講義する． 第１回：グラフアルゴリズム（１）：最小全域木問題等 第２回：グラフアルゴリズム（２）：最短経路問題等 第３回：動的計画法の適用例（１）：オートマトンから正則表現への変換 第４回：動的計画法の適用例（２）：文脈自由文法の認識問題 第５回：動的計画法の適用例（３）：文脈自由文法の認識問題における再帰構造の導出 第６回：動的計画法の適用例（４）：隠れマルコフモデルとは 第７回：動的計画法の適用例（５）：隠れマルコフモデルの認識問題 第８回；動的計画法の適用例（６）：隠れマルコフモデルの認識アルゴリズム 第９回：動的計画法の適用例（７）：近似文字列照合問題 第１０回：KMPアルゴリズムにおける失敗関数の計算 第１１回：KMPアルゴリズムにおけるオートマトンの構成アルゴリズム 第１２回：NP完全・NP困難とは 第１３回：NP困難な問題の例 第１４回：NP困難問題に対する分枝限定法の理論 第１５回：NP困難問題に対する近似アルゴリズムの理論 （ｂ）授業の進め方 講義では，各問題の背景と動機を説明した後， アルゴリズムを導入し，その正当性の 証明と計算量の解析を与える． |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
予習・復習は十分に行い， できればアルゴリズムの実装などもして欲しい。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
(a) 成績評価方法 期末試験の成績により判断する．指定された事項に関する レポートや演習・小試験の評価を含める場合もある． (b) 評価基準 達成目標で述べた１)と２)の達成度が一定の水準以上であれば合格とする． |
| オフィスアワー： 授業相談 /Office hours |
適宜相談に応じるが，メールなどで事前にアポイントを取ること． |
| 学生へのメッセージ /Message for students |
紹介したアルゴリズムを単に実装できるようになるだけでなく， 計算効率を上げるためにどのような工夫がされているか， なぜ正しく動くのかを「理解」してほしい． |
| その他 /Others |
特になし |
| キーワード /Keyword(s) |
アルゴリズム，計算量，グラフ，最短路，動的計画法，文字列照合，文法，隠れマルコフモデル，NP完全，NP困難，分枝限定法，近似アルゴリズム |