学部・大学院区分
Undergraduate / Graduate
情報・博前
時間割コード
Registration Code
2510027
科目区分
Course Category
主専攻科目
科目名 【日本語】
Course Title
最適化特論1
科目名 【英語】
Course Title
Optimization 1
コースナンバリングコード
Course Numbering Code
GSI116027J
担当教員 【日本語】
Instructor
柳浦 睦憲 ○ 大舘 陽太 小野 廣隆
担当教員 【英語】
Instructor
YAGIURA Mutsunori ○ OTACHI Yota ONO Hirotaka
単位数
Credits
1
開講期・開講時間帯
Term / Day / Period
春1期 木曜日 3時限
Spring1 Thu 3
対象学年
Year
1年
1
授業形態
Course style

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


授業の目的 【日本語】
Goals of the Course(JPN)
多くの離散最適化問題がNP困難であることが知られており,それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の実践的手法を学び,それらを用いた問題解決の力を養う。
具体的には,基本戦略として構築型の解法である欲張り法と反復改善型の解法である局所探索法を学んだのち,
アニーリング法,遺伝アルゴリズム,タブー探索法などに代表されるメタヒューリスティクスと呼ばれる枠組みについて学ぶ。
授業の目的 【英語】
Goals of the Course
In this course, we study the basic concepts of practical methods, including local search, simulated annealing, tabu search and genetic algorithms, for solving hard combinatorial optimization problems.
到達目標 【日本語】
Objectives of the Course(JPN)
多くの離散最適化問題がNP困難であることが知られており,それらに対して厳密な最適解を現実的な時間で得ることは困難であることが知られている。
本講義では最適化の手法について理解するとともに,それらを用いた問題解決の力を養う。
到達目標 【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
最適化特論1では,計算困難な離散最適化問題の中から,主にNP困難であるものを対象として,
それらに現実的に対処するために用いられる代表的なアルゴリズムの基礎を取り上げる。
基本戦略として構築型の解法である欲張り法と反復改善型の解法である局所探索法を学んだのち,
アニーリング法,遺伝アルゴリズム,タブー探索法などに代表されるメタヒューリスティクスと
呼ばれる枠組みについて,局所探索の一般化に基づく統一的な視点から,それらの基本的な考え方を修得する。

〔計画〕
1. イントロダクション
2. 離散最適化問題
3. 欲張り法と局所探索法
4. アニーリング法
5. 遺伝アルゴリズム
6. タブー探索法
7. 総合討論
履修条件・関連する科目
Course Prerequisites and Related Courses
必須ではないが,プログラミング(とくにC言語)の基礎知識があるほうが望ましい。
成績評価の方法と基準
Course Evaluation Method and Criteria
講義中に課題を与えた場合はその評価と期末レポートを総合的に評価し,合計100点満点で60点以上を合格とする。
教科書・参考書
Textbook/Reference book
必要に応じて参考資料を配布し,講義のウェブサイトからダウンロードできるようにする。
課外学習等(授業時間外学習の指示)
Study Load(Self-directed Learning Outside Course Hours)
講義において説明した内容を理解するために課題を与える。
授業開講形態等
Lecture format, etc.
遠隔授業(オンデマンド型)で行う場合の追加措置
Additional measures for remote class (on-demand class)