シラバス参照

授業情報/Class Information

科目一覧へ戻る 2020/06/05 現在

基本情報/Basic Information

開講科目名
/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 Information

教員名
/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

科目一覧へ戻る