シラバス参照 |
科目一覧へ戻る | 2020/06/05 現在 |
開講科目名 /Course |
計算幾何学 |
---|---|
時間割コード /Course Code |
S21A0030_S6 |
開講所属 /Course Offered by |
システム工学研究科/Graduate School of Systems Engineering |
ターム・学期 /Term・Semester |
2020年度/Academic Year 第2クォーター/2Q |
曜限 /Day, Period |
月/Mon 3, 水/Wed 3 |
開講区分 /semester offered |
第2クォーター/2Q |
単位数 /Credits |
2.0 |
学年 /Year |
1,2,3,4 |
主担当教員 /Main Instructor |
今井 敏行 |
科目区分 /Course Group |
_ |
授業形態 /Lecture Form |
|
教室 /Classroom |
A-204/A-204 |
教員名 /Instructor |
教員所属名 /Affiliation |
---|---|
今井 敏行 | システム工学部(教員) |
授業の概要・ねらい /Course Aims |
計算幾何学とは, 図形処理の諸問題を, アルゴリズムの観点から捉え, 問題の 高速解法や数値的に安定な解法の開発や, 高速化の限界や, 不安定性の原因を 探る情報科学の一分野で, 分類上はアルゴリズム論に属する. 本科目では, 計 算幾何学から典型的な題材を選び, データ構造やアルゴリズムを駆使して高速 解法を開発したり, 数学や統計学を利用して問題の複雑さや解法の効率性を論 じる. 情報科学の主柱のひとつであるアルゴリズム論の特論的性質を持つ. 学部段階 で既習のデータ構造やアルゴリズム, 解析, 代数, 幾何, 統計の知識を活用し て, プログラムより一段抽象度の高いレベルで, 組合せ論としての理論限界を 超える高速アルゴリズムを, 幾何的性質を利用して開発する手法を理解し, そ の能力を獲得する. 併せて, 問題の複雑度や解法の効率性を解析し, 解法の数 値的安定性の評価する能力を獲得する. |
---|---|
到達目標 /Course Objectives |
データ構造とアルゴリズムの基礎知識と計算複雑度の概念は既知とする. 既存 の効率的アルゴリズムの構成方法と, 効率性の解析能力の獲得をもって合格と する. さらに問題の複雑度の解析ができれば良, また, 未知の問題に対して, 最適アルゴリズムの構築へと向かえる問題解析力と知識, アルゴリズム構成能 力をもって優とする. |
成績評価の方法・基準 /Grading Policies/Criteria |
レポートと試験で総合評価する. |
教科書 /Textbook |
特になし. |
参考書・参考文献 /Rreference Book |
必要があれば講義中に示す. |
履修上の注意 ・メッセージ /Notice for Students |
データ構造とアルゴリズム, 解析や線形代数の知識は必須である. アルゴリズム論であるから, プログラム言語を直接参照することはないが, ア ルゴリズムを具体的なものとして知覚するため, ある程度のプログラム言語の 知識とプログラムの経験は必要であろう. |
履修する上で必要な事項 /Prerequisite |
|
履修を推奨する関連科目 /Related Courses |
|
授業時間外学修についての指示 /Instructions for studying outside class hours |
本授業の授業計画に沿って、準備学習45時間と復習45時間を行ってください。さらに、授業内容に関連する課題に関する調査・考察を含めて、毎回の授業ごとに自主的学修を求めます。 |
その他連絡事項 /Other messages |
クォーター制移行に伴い,週2時限の開講となる.開講するクォーターと時限をよく確認すること. |
授業理解を深める方法 /How to deepen your understanding of classes |
|
オフィスアワー /Office Hours |
|
科目ナンバリング /Course Numbering |
S5470N03J |
高等教育無償化に関する特記事項 /Special note on free higher education |
No. | 回(日時) /Time (date and time) |
主題と位置付け(担当) /Subjects and instructor's position |
学習方法と内容 /Methods and contents |
備考 /Notes |
---|---|---|---|---|
1 | 計算幾何学の例(1)(データ構造とアルゴリズムと計算複雑度) | |||
2 | 計算幾何学の例(2)(線分の交差列挙) | |||
3 | 凸包(1)(表現形式と応用例) | |||
4 | 凸包(2)(構成) | |||
5 | 三角形分割(1)(応用例と複雑度解析) | |||
6 | 凸包(3)(凸包の拡張) | |||
7 | 三角形分割(2)(Delaunay三角形分割) | |||
8 | Voronoi図(1)(応用例と解析) | |||
9 | Voronoi図(2)(構成(1)(2)) | |||
10 | Voronoi図(3)(構成(3)一般化, 応用例) | |||
11 | 幾何的双対変換 | |||
12 | 計算誤差と数値的安定性(1)(解析と記号摂動法) | |||
13 | 計算誤差と数値的安定性(2)(位相優先法) | |||
14 | 計算幾何学の例(3)(ハムサンドイッチカット) | |||
15 | まとめと試験 | |||
16 | ||||
17 | ||||
18 | ||||
19 | ||||
20 | ||||
21 | ||||
22 | ||||
23 | ||||
24 | ||||
25 | ||||
26 | ||||
27 | ||||
28 | ||||
29 | ||||
30 |