シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
Advanced Communication Engineering and Informatics Ⅳ（Computer Algorithms）（学域） | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced Communication Engineering and Informatics Ⅳ（Computer Algorithms） | ||
| 科目番号 /Code |
INT004c INT004d INT004f INT004g | ||
| 開講年度 /Academic year |
2019年度 | 開講年次 /Year offered |
3/4 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
Ⅰ類/Ⅱ類 | ||
| 担当教員名 /Lecturer(s) |
小林 聡 | ||
| 居室 /Office |
W9-735 | ||
| 公開E-mail |
kobayashi.satoshi@uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://www.comp.cs.uec.ac.jp/lectures/ | ||
| 更新日 /Last update |
2019/02/22 13:07:05 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
The purpose of this lecture is provide the theory and technique to design efficient algorithms for various fundamental problems. The goals of the students are to achieve the following points: (1) to understand the behavior, correctness, and time complexity analysis of the algorithms discussed in the lecture, (2) to understand the principles of design methodologies of algorithms, such as dynamic programming, greedy method, etc. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
Registered students should have ability to write C programs. Furthermore, the knowledge about some basic data structures (list, binary tree, heap, etc.) and basic algorithms (sorting, etc.) are required. |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
None |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
Some handouts are provided at the lecture. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
(a) Contents of the lecture [1] Minimum spanning tree problem and greedy algorithms [2] Correctness of Prim's and Kruskal's algorithm [3] Greedy algorithms for other problems [4] Shortest path problem and Dynamic Programming (DP) [5] DP Method (1) --- Transform DFAs to regular expressions [6] DP Method (2) --- Context-free grammar and its recognition problem [7] DP Method (3) --- CYK algorithm for CFG recognition [8] DP Method (4) --- Hidden Markov Models (HMM) [9] DP Method (5) --- Recognition problem of HMM [10] DP Method (6) --- HMM recognition algorithm [11] DP Method (7) --- Approximate string matching algorithms [12] String matching problem [13] Computing failure functions in KMP algorithm [14] Correctness and time complecity of KMP algorithm [15] Summary and conclusion of this lecture (b) How does this lecture proceed? For each problem, we first discuss on its background and motivation, and then give an algorithm for the problem. The correctness and time complexity analysis of the given algorithm will be discussed in details. Example runs will be used to enrich the understanding. |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
Implement algorithms given in the the lecture, if possible. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
Academic performance is evaluated by exams. The lowest standard is 60%. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
Any time, but appointments by e-mails are necessary. |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
None |
| その他 /Others |
None |
| キーワード /Keywords |
Dynamic programming, greedy algorithms, context free grammars, HMM, string matching, etc. |