基本情報/Basic Information

遠隔授業（授業回数全体の半分以上）の場合は、科目名の先頭に◆が付加されています（2023年度以降）

開講科目名 ／Course	計算幾何学／Computational Geometry
時間割コード ／Course Code	S21A0030_S6
開講所属 ／Course Offered by	システム工学研究科／Graduate School of Systems Engineering
ターム・学期 ／Term・Semester	2024年度／Academic Year　　第2クォーター／2Q
曜限 ／Day, Period	月／Mon　3,　水／Wed　3
開講区分 ／Semester offered	第2クォーター／2Q
単位数 ／Credits	2.0
学年 ／Year	1,2
主担当教員 ／Main Instructor	今井　敏行
科目区分 ／Course Group	_
授業形態 ／Lecture Form	講義
教室 ／Classroom	北１号館Ａ２０３／北１号館Ａ２０３
開講形態 ／Course Format
ディプロマポリシー情報 ／Diploma Policy

担当教員情報/Instructor Information

教員名 ／Instructor	教員所属名 ／Affiliation
今井　敏行	システム工学部（教員）

授業の概要・ねらい ／Course Aims	計算幾何学とは, 図形処理の諸問題を, アルゴリズムの観点から捉え, 問題の 高速解法や数値的に安定な解法の開発や, 高速化の限界や, 不安定性の原因を 探る情報科学の一分野で, 分類上はアルゴリズム論に属する. 本科目では, 計 算幾何学から典型的な題材を選び, データ構造やアルゴリズムを駆使して高速 解法を開発したり, 数学や統計学を利用して問題の複雑さや解法の効率性を論 じる. 情報科学の主柱のひとつであるアルゴリズム論の特論的性質を持つ. 学部段階 で既習のデータ構造やアルゴリズム, 解析, 代数, 幾何, 統計の知識を活用し て, プログラムより一段抽象度の高いレベルで, 組合せ論としての理論限界を 超える高速アルゴリズムを, 幾何的性質を利用して開発する手法を理解し, そ の能力を獲得する. 併せて, 問題の複雑度や解法の効率性を解析し, 解法の数 値的安定性の評価する能力を獲得する.
到達目標 ／Course Objectives	データ構造とアルゴリズムの基礎知識と計算複雑度の概念は既知とする. ただし，授業では簡単に触れる．既存の効率的アルゴリズムの構成方法と, 効率性の解析能力の獲得を目指す．さらに問題の複雑度の解析ができればを目指し， 最終的には未知の問題に対して, 最適アルゴリズムの構築へと向かえる問題解析力と知識, アルゴリズム構成能力の獲得を目指す.
成績評価の方法・基準 ／Grading Policies/Criteria	レポートと試験で総合評価する． 既存 の効率的アルゴリズムの構成方法と, 効率性の解析能力の獲得をもって合格（C）とする. さらに問題の複雑度の解析ができればB, また, 未知の問題に対して, 最適アルゴリズムの構築へと向かえる問題解析力と知識, アルゴリズム構成能力の最低限をA, これらの能力に余裕があればSとする.
教科書 ／Textbook	該当なし.
参考書・参考文献 ／Reference Book	必要があれば講義中に示す．
履修上の注意 ・メッセージ ／Notice for Students	アルゴリズム論であるから, プログラム言語を直接参照することはないが, ア ルゴリズムを具体的なものとして知覚するため, ある程度のプログラム言語の 知識とプログラムの経験は必要であろう.
履修する上で必要な事項 ／Prerequisite	データ構造とアルゴリズム, 解析や線形代数の知識は必須である. ただし講義中にある程度は補う．
履修を推奨する関連科目 ／Related Courses	該当なし.
授業時間外学修についての指示 ／Instructions for studying outside class hours	本授業の授業計画に沿って、準備学習45時間と復習45時間を行ってください。さらに、授業内容に関連する課題に関する調査・考察を含めて、毎回の授業ごとに自主的学修を求めます。
その他連絡事項 ／Other messages	クォーター制移行に伴い，週２時限の開講となった．開講するクォーターと時限をよく確認すること．
授業理解を深める方法 ／How to deepen your understanding of classes	興味あるトピックに関して，自発的にプログラムを組んだり，関連文献を探索したりする．また，各自の修士論文の研究テーマに活用できないか検討する． 【「アクティブ・ラーニング」実施要項⑦】
オフィスアワー ／Office Hours	質問や相談があれば，まず連絡してください．
科目ナンバリング ／Course Numbering	S60095J10099N503

No.	回（日時） ／Time (date and time)	主題と位置付け（担当） ／Subjects and instructor's position	学習方法と内容 ／Methods and contents	備考 ／Notes
1	1	計算幾何学の紹介	計算幾何学の例(1)(データ構造とアルゴリズムと計算複雑度)
2	2	計算幾何学の紹介	計算幾何学の例(2)(線分の交差列挙)
3	3	凸包・数学的表現・下限計算量	凸包(1)(表現形式と応用例)
4	4	アルゴリズムの多様性	凸包(2)(構成)
5	5	凸包の発展的内容	凸包(3)(凸包の拡張)
6	6	三角形分割の導入	三角形分割(1)(応用例と複雑度解析)
7	7	評価基準とアルゴリズム	三角形分割(2)(Delaunay三角形分割)
8	8	Voronoi図の導入	Voronoi図(1)(応用例と解析)
9	9	構成アルゴリズム	Voronoi図(2)(構成(1)(2))
10	10	Voronoi図の発展的内容	Voronoi図(3)(構成(3)一般化, 応用例)
11	11	幾何的双対変換の導入と応用・わかりやすさ	幾何的双対変換
12	12	幾何的退化とアルゴリズムの挙動・対策	計算誤差と数値的安定性(1)(解析と記号摂動法)
13	13	幾何的退化への対策	計算誤差と数値的安定性(2)(位相優先法)
14	14	計算幾何学の活用例	計算幾何学の例(3)(ハムサンドイッチカット)
15	15		まとめと試験