シラバス参照
|
シラバス参照
|
| 科目一覧へ戻る | 2025/06/24 現在 |
|
開講科目名 ／Course |
計算幾何学／Computational Geometry | ||||||||
|---|---|---|---|---|---|---|---|---|---|
|
時間割コード ／Course Code |
S21A0030_S6 | ||||||||
|
開講所属 ／Course Offered by |
システム工学研究科／Graduate School of Systems Engineering | ||||||||
|
ターム・学期 ／Term・Semester |
2025年度／Academic Year 第2クォーター／2Q | ||||||||
|
曜限 ／Day, Period |
月／Mon 3, 水／Wed 3 | ||||||||
|
開講区分 ／Semester offered |
第2クォーター／2Q | ||||||||
|
単位数 ／Credits |
2.0 | ||||||||
|
学年 ／Year |
1,2 | ||||||||
|
主担当教員 ／Main Instructor |
今井 敏行 | ||||||||
|
授業形態 ／Lecture Form |
講義 | ||||||||
|
教室 ／Classroom |
北１号館Ａ２０４／北１号館Ａ２０４ | ||||||||
|
開講形態 ／Course Format |
|||||||||
|
ディプロマポリシー情報 ／Diploma Policy |
|
|
教員名 ／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 |
本授業の授業計画に沿って、準備学習と復習を行ってください。さらに、授業内容に関連する課題に関する調査・考察を含めて、毎回の授業ごとに自主的学修を求めます。 1単位の学修のために必要な学修量は、授業時間と予習復習の時間をあわせて45時間と定められている。それぞれに見合う自主的学修時間を確保すること。 |
|
その他連絡事項 ／Other messages |
クォーター制移行に伴い，週２時限の開講となった．開講するクォーターと時限をよく確認すること． |
|
授業理解を深める方法 ／How to deepen your understanding of classes |
興味あるトピックに関して，自発的にプログラムを組んだり，関連文献を探索したりする．また，各自の修士論文の研究テーマに活用できないか検討する． 【「アクティブ・ラーニング」実施要項⑦】 |
|
オフィスアワー ／Office Hours |
質問や相談があれば，まず連絡してください． |
|
科目ナンバリング ／Course Numbering |
S60095J10099N503 |
|
実務経験 ／Practical Experience |
無 |
| No. | 回（日時） ／Time (date and time) |
主題と位置付け ／Subjects and position in the whole course |
学習方法と内容 ／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 | まとめ | 講義内容の振り返り | |
| 16 | 16 | 単位認定試験 | 単位認定試験 |