学部・大学院区分
Undergraduate / Graduate
情報・博前
時間割コード
Registration Code
2510049
科目区分
Course Category
主専攻科目
科目名 【日本語】
Course Title
アルゴリズム論特論1
科目名 【英語】
Course Title
コースナンバリングコード
Course Numbering Code
GSI116049J
担当教員 【日本語】
Instructor
小野 廣隆 ○
担当教員 【英語】
Instructor
ONO Hirotaka ○
単位数
Credits
1
開講期・開講時間帯
Term / Day / Period
秋1期 金曜日 2時限
Fall1 Fri 2
対象学年
Year
1年
1
授業形態
Course style

開講系(学部)・開講専攻(大学院)
Subject
数理情報学専攻
必修・選択
Required / Selected


授業の目的 【日本語】
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では特に,計算困難問題に対する乱択アルゴリズムの設計と解析について取り上げる.ガイダンスの後,以下のトピックのいくつかを取り上げ講義する.


・確率的基礎
・乱択アルゴリズムの概念
・フィンガープリント
・アドバーサリーの議論
・マルコフ連鎖とランダムウォーク
・サンプリングとモンテカルロ法
・その他のトピック
履修条件・関連する科目
Course Prerequisites and Related Courses
学部レベルの理論計算機科学の基礎(アルゴリズムとデータ構造,グラフ理論の基礎,計算量理論の基礎)を理解していること.
成績評価の方法と基準
Course Evaluation Method and Criteria
レポート課題への解答を100点満点で評価し,60点以上を合格とする。
教科書・参考書
Textbook/Reference book
適宜紹介する.
課外学習等(授業時間外学習の指示)
Study Load(Self-directed Learning Outside Course Hours)
定期的にレポート課題を課す。
また,講義で完全に証明し切れなかった部分を⾃ら補うことが望ましい。
授業開講形態等
Lecture format, etc.
NUCTでの資料掲載+zoom等での解説による(感染状況により開講形態を変更することがある).
遠隔授業(オンデマンド型)で行う場合の追加措置
Additional measures for remote class (on-demand class)