| 授業科目名 | 計算幾何学 |
|---|---|
| 履修期 秋 2単位 履修基準年度 3年 | |
| 担当者 | 加藤 直樹（KATOH NAOKI） |
| 授業目的 / Course Objectives |
|---|
| 幾何学的な対象のアルゴリズムを例として，アルゴリズムとその効率の解析の手法を学ぶ． |
| 到達目標 / Attainment Objectives |
| 目標１：平面上の点，線分，直線に対する基本操作（線分の交差判定，左右の判定）を小さいサイズの具体例に対して実行する過程を図示することができるようになること． 目標２：多数の点，線分からなる図形を計算機で処理するための初歩的な幾何学的アルゴリズムを，縮退のない入力例に対して，実行過程を記述することができるようになること． 目標３：「データ構造とアルゴリズム」で学んだデータ構造が，幾何学的アルゴリズムの中ではたしている役割，なぜ，そのデータ構造を選択したかを説明することができるようになること． 目標４：講義中に紹介するアルゴリズムの時間計算量を導く過程を説明することができるようになること |
| 教科書 / Textbook(s) |
| 浅野哲夫「計算幾何 －理論の基礎から実装まで－」（共立出版、２００７） |
| 関連科目 Related Courses |
| データ構造とアルゴリズム |
| 授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.) |
| 授業中に理解することが最も重要である．各回の学習において，それまでの授業の学習成果を活用することが不可欠である．授業開始までに，前回までの授業内容を復習しておくことを求める． |
| 授業計画 / Class Overall Plan |
|
第1回．計算幾何学とは 第2回．第２章 計算幾何の基礎－１ 第3回．第２章 計算幾何の基礎－２ 第4回．第３章 幾何計算の実装 第5回．第４章 計算幾何学の基本的な考え方－１ 第6回．第４章 計算幾何学の基本的な考え方－２ 第7回．第５章 基本的なアルゴリズム設計技法－１ 第8回．第５章 基本的なアルゴリズム設計技法－２ 第9回．第７章 幾何計算のためのデータ構造－１ 第10回．第７章 幾何計算のためのデータ構造－２ 第11回．第８章 計算幾何のためのアルゴリズム設計技法－１ 第12回．第８章 計算幾何のためのアルゴリズム設計技法－２ 第13回．第９章 ボロノイ図とデローネイ３角形分割ー１ 第14回．第９章 ボロノイ図とデローネイ３角形分割ー２ |
| 授業方法 / Method of Instruction |
| プレゼンテーションソフトを利用する．教科書は用いず，プレゼンテーションの資料を毎回配布する．また，講義中に簡単な演習問題を行い，提出を求める．提出後，解答を説明し，授業内容の理解を促す．演習の提出物を評価，採点し，成績に反映させる． |
| 学生による授業評価の方法 / Course Evaluation by Students |
| 授業中においてミニットペーパーを用いるとともに授業最終回には授業評価のアンケートを実施する． |
| 成績評価 / Evaluation Criteria/Method |
|
定期試験 70% その他 30%（講義時間内に演習を行い，提出を求め評価する．） |
| 備考 / Note |
| 毎回講義中に演習を行い，提出を求める．講義時間中の演習の評価を約30%，定期試験の評価を約70%，加えて総合的に評価する．定期試験においては，到達目標に従い，簡単な入力に対して，幾何学的対象を処理する方法の理解を確認する．講義中に説明したアルゴリズムを実行し，その過程を記述することを求める．また，簡単なアルゴリズムについて時間計算量を導出し，その過程を説明することを求める． - |
| 検索キーワード / Keywords |
| データ構造 アルゴリズム 点 直線，線分 |