大学院
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
近似・オンラインアルゴリズムとその応用
In this class, we discuss basic concepts in algorithmics such as NP-hardness, approximation algorithms, and online algorithms. Then, we give examples how to apply them to practical research.
At the end of this class, students who are not familiar with these theoretical concepts are expected to learn their importance in practical point of views. On the other hands, students who are familiar with them are expected to gain more experiences on applying the concepts to practical settings.
本講義では、NP困難、近似アルゴリズム、オンラインアルゴリズムなどアルゴリズムを解析する理論の概要を説明し、機械学習や データベースなど応用分野に適用する事例を挙げる。
アルゴリズム論を勉強したことがない学生には理論的な解析の重要性を実感させ、勉強したことがある学生にはアルゴリズム論の応用を経験させることを目的としている。
At the end of this class, students who are not familiar with these theoretical concepts are expected to learn their importance in practical point of views. On the other hands, students who are familiar with them are expected to gain more experiences on applying the concepts to practical settings.
本講義では、NP困難、近似アルゴリズム、オンラインアルゴリズムなどアルゴリズムを解析する理論の概要を説明し、機械学習や データベースなど応用分野に適用する事例を挙げる。
アルゴリズム論を勉強したことがない学生には理論的な解析の重要性を実感させ、勉強したことがある学生にはアルゴリズム論の応用を経験させることを目的としている。
時間割／共通科目コード
コース名
教員
学期
時限
4810-1183
GIF-CS5054L3
近似・オンラインアルゴリズムとその応用
Suppakitpaisarn Vorapong
月曜5限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
情報理工学系研究科
授業計画
Class 1: Linear Programming, Optimization Models
Class 2: NP-Hardness
Class 3: Product Selection Problem
Approximation Algorithms
Class 4: Basic Definitions, Greedy Techniques
Class 5: Adaptive Bloom Filter
Class 6: Deterministic Rounding, Network Monitoring
Class 7: Randomized Rounding
Class 8: Sparse PCA
Class 9: Exercises on Approximation Algorithms
Class 10: Inapproximability
Online Algorithms
Class 11: Basic Definitions
Class 12: Online Machine Learning
Class 13: Online Graph Algorithms
Class 14: Online Scheduling (Guest Lectures)
Class 15: Exercises on Inapproximability and Online Algorithms
授業の方法
The lecture is given in English using a blackboard. Some of the classes will be offered both onsite and online.
成績評価方法
There are three optional assignments and one final examination during this course.
教科書
Lecture notes given in the classes.
参考書
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010.
A. Fiat and G. J. Woeginer (editors). Online Algorithms: The State of the Art. Springer, 1998.
履修上の注意
This class will start from April 8th. Some of the classes will be offered also at the university, but the first class will be fully online. We will distribute documents by course Slack. Please click at the following link to join the course Slack.
https://*****.slack.com/*****
その他
Students must be familiar with mathematical concepts such as set, functions, and mathematical proofs to join this course.
As the evaluation of this course will be conducted mainly by the final examination, students who are not familiar with the mathematical concepts might not be able to obtain credits of this course.
