授業の目的 【日本語】
Goals of the Course(JPN) | | | アルゴリズム論特論では，グラフをはじめとする組合せ的対象に対するアルゴリズム設計について学ぶ．組合せ最適化問題は多くの場合多項式時間アルゴリズム設計が困難であることが知られている．アルゴリズム論特論1では特に，組合せ最適化問題に対する近似アルゴリズムの設計と解析について学ぶ． |
|
|
授業の目的 【英語】
Goals of the Course | | | In the course of Algorithm Theory, we learn the design of algorithms on combinatorial objects such as graphs. Combinatorial optimization problems are known to be hard to design polynomial-time algorithms. In the course of Algorithm Theory 1, we particularly learn the design and analysis of randomized algorithms for computationally hard problems. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | | 離散的に存在する考察対象から有益な情報を取り出そうとするとき，それらを単なる物の集まりとしてではなく 離散系として捉え理解することが第⼀歩であり，さらに分析し解析するためには，離散系に対する数学的基礎理論 を修得していることが非常に重要である。 このような数学的な思考法を⾝に着けることを目標とする。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | アルゴリズム論特論では，グラフをはじめとする組合せ的対象に対するアルゴリズム設計について解説する。 アルゴリズム論特論1では特に，計算困難問題に対する近似アルゴリズムの設計と解析について取り上げる．ガイダンスの後，以下のトピックを中心に講義する．
・近似アルゴリズムの設計例
・ＬＰラウンディング
・主双対法
・メトリックTSP等
・PTAS/FPTAS | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | | 学部レベルの理論計算機科学の基礎（アルゴリズムとデータ構造，グラフ理論の基礎，計算量理論の基礎）を理解していること． | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | レポート課題への解答を１００点満点で評価し，６０点以上を合格とする。 | |
|
|
教科書・参考書
Textbook/Reference book | | |
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | 定期的にレポート課題を課す。
また，講義で完全に証明し切れなかった部分を⾃ら補うことが望ましい。 | |
|
|
授業開講形態等
Lecture format, etc. | | | TACTでの資料掲載＋対面講義（回によってはzoom 等の遠隔授業を行う場合がある） |
|
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|