学部・大学院区分
Undergraduate / Graduate		理学部
時間割コード
Registration Code		0610042
科目区分
Course Category		専門科目
Specialized Courses
科目名　【日本語】
Course Title		数学研究QⅠ
科目名　【英語】
Course Title		Undergraduate Seminar QI
コースナンバリングコード
Course Numbering Code
担当教員　【日本語】
Instructor		喜多 奈々緒 ○
担当教員　【英語】
Instructor		KITA Nanao ○
単位数
Credits		6
開講期・開講時間帯
Term / Day / Period		春 水曜日 ３時限
春 水曜日 ４時限
Spring Wed 3
Spring Wed 4
授業形態
Course style		セミナ－
Seminar
学科・専攻
Department / Program
数理学科
必修・選択
Compulsory / Selected
選択必修


授業の目的　【日本語】
Goals of the Course(JPN)
テーマ「離散最適化」：　グラフ上の離散最適化問題（組合せ最適化問題）について基礎を学び，さらにその計算量的性質と関わる構造を様々な角度から研究する．
授業の目的　【英語】
Goals of the Course
Theme: "Discrete Optimization". In this course, we aim to learn the basics of discrete opimization (combinatorial optimization) and develop original researches on combinatorial optimization problems on graphs, particularly focusing on various structures that are connected to computational properties.
到達目標　【日本語】
Objectives of the Course(JPN))
最適化理論・計算量理論・グラフ理論の基礎を修得すること．文献から専門的な知識を習得し議論する方法を身に付けること．離散数学あるいは理論計算機科学に関する独自のテーマを見つけ研究に取り組むこと．
到達目標　【英語】
Objectives of the Course
(1) To master the basics of optimization theory, computational complexity theory, and graph theory. (2) To learn how to understand technical materials from literature　and develop skills for discussion.
授業の内容や構成
Course Content / Plan
離散最適化の入門書にてグラフ・最適化理論・計算量理論の基礎を一通り学んだのち，グラフ理論・線形計画法・計算量理論のいずれかの方向に専門書を選び深堀りする．方向性は受講者の興味に応じて決定される．週１回のセミナーで輪講形式で文献を読み進める．
履修条件
Course Prerequisites
線型代数の知識を仮定する．離散数学・理論計算機科学の基礎知識があることは望ましいが必須ではない．
線型代数，離散数学，理論計算機科学
関連する科目
Related Courses
成績評価の方法と基準
Course Evaluation Method and Criteria
セミナーでの発表および議論の様子により評価される．
セミナー発表が最低限の到達度に達しない場合は不可と評定される．欠席が多く見られる場合は欠席と評定される．
不可(F)と欠席(W)の基準
Criteria for "Fail (F)" & "Absent (W)" grades
参考書
Reference Book
[3] Sipser, Michael, ""Introduction to the Theory of Computation"", Cengage Learning, 2001.　
[4] Mohar, Bojan, and Carsten Thomassen, ""Graphs on surfaces"", Johns Hopkins University Press, 2001.
[5] Ziegler, Günter M., ""Lectures on polytopes"", Springer, 2012.
その他都度紹介する．
教科書・テキスト
Textbook
[1] Cook, William J., et al., ""Combinatorial optimization"", Wiley, 1997.　
[2] Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty, ""Graph theory"", Springer, 2008.
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
発表担当回には十分な準備が必須である．
注意事項
Notice for Students
他学科聴講の可否
Propriety of Other department student's attendance
可
他学科聴講の条件
Conditions for Other department student's attendance
レベル
Level
2
キーワード
Keyword
グラフ理論，離散数学，最適化理論，理論計算機科学
履修の際のアドバイス
Advice
離散数学と理論計算機科学に意欲のある学生を歓迎する．
授業開講形態等
Lecture format, etc.
原則対面．ただし状況により変更の可能性あり．
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)