シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
学域特別講義A(アルゴリズムの基礎) (Fundamentals of Algorithms) | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Special Lecture on Informatics and Engineering A (Fundamentals of Algorithms) | ||
| 科目番号 /Code |
UEC028z | ||
| 開講年度 /Academic year |
2024年度 | 開講年次 /Year offered |
1/2/3/4 |
| 開講学期 /Semester(s) offered |
前学期集中 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
1 |
| 科目区分 /Category |
総合文化科目 | ||
| 開講類・専攻 /Cluster/Department |
情報理工学域 | ||
| 担当教員名 /Lecturer(s) |
小林 聡 | ||
| 居室 /Office |
西９―７３８ West No. 9 Building Room 738 | ||
| 公開E-mail |
kobayashi.satoshi@uec.ac.jp | ||
| 授業関連Webページ /Course website |
今回は Google classroom を利用します | ||
| 更新日 /Last update |
2024/03/12 00:49:03 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
本講義の目的は、いくつかの基礎的な問題に対する効率の良いアルゴリズムの設計方法を与えることである。達成目標は、 (1) 講義で議論するアルゴリズムの振る舞い、正当性、時間計算量を理解できること、および (2) 動的計画法や貪欲算法などのアルゴリズムの設計手法を理解できること である。 The purpose of this lecture is to provide the theory and technique to design efficient algorithms for some 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） |
C言語のプログラミングに関する科目、および、アルゴリズムの基礎的なデータ構造（リスト、二文木、ヒープ、など）と基礎アルゴリズム（ソートアルゴリズムなど）を理解できていること。 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） |
文脈自由文法に関する知識 Some knowledge about context-free grammars |
| 教科書等（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) 授業の内容 [1] 最小全域木と貪欲算法 [2] Prim のアルゴリズムと Kruskal のアルゴリズムの正当性 [3] 他の問題に対する貪欲算法 [4] 最短経路問題と動的計画法 [5] 動的計画法（１）―DFAの正則表現への変換 [6] 動的計画法（２）―文脈自由文法とその認識問題 [7] 動的計画法（３）―文脈自由文法の認識問題に対するCKYアルゴリズム [8] 動的計画法（４）―近似文字列照合アルゴリズム (b) 授業の進め方 各問題に対して背景などを説明した後、アルゴリズムを与える。 アルゴリズムの正当性と時間計算量の解析は詳細に行う。 理解を深めるために実行例も与える。 すべて講義について、講義ビデオを事前に与える。授業時間は 講義ビデオの内容に関する質問を受け付けるために用いる。 (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) --- Approximate string matching algorithms (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. Every lecture is given as a lecture video beforehand. At the lecture time, students can ask questions. |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
学生は、講義の内容に関連した問題をオンラインで解くことが要求される。 Students should solve some problems online related to lecture topics. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績は、与えた問題に対する評価で決まる。最低基準は、６０％以上 正解することである。 Academic performance is evaluated by giving problems online. The lowest standard is 60%. |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
学生からの電子メールによる質問を受け付ける。 しかしながら、講義開始前に講義ビデオをすべて与えるので、講義時間に できるだけ質問してほしい。講義時間は、学生への質問に答えるために 利用する。 Students may ask questions by e-mails. Since all the lecture videos are provided before starting the lecture, please ask questions at the lecture time as far as possible. Each lecture time is used for answering questions of the students. |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
なし None |
| その他 /Others |
なし None |
| キーワード /Keywords |
Dynamic programming, greedy algorithms, context free grammars, etc. |