計算幾何（アルゴリズム論２）のシラバス情報
| 科目名称 Course title(Japanese) |
計算幾何 | 科目番号 Course number |
14ISCIP304 | |
|---|---|---|---|---|
| 科目名称（英語） Course title(English) |
Computational geometry | |||
| 授業名称 Class name |
計算幾何（アルゴリズム論２） | |||
| 教員名 | 関川 浩 |
|---|---|
| Instructor |
| 開講年度学期 | 2022年度 後期 |
|---|---|
| Year/Semester |
| 曜日時限 | 金曜2限 |
|---|---|
| Class hours |
| 開講学科 Department |
理学部第一部 応用数学科 |
|---|---|
| 外国語のみの科目 （使用言語） Course in only foreign languages (languages) |
- |
| 単位 Course credit |
2.0 | 授業の主な実施形態 Main class format |
対面授業/On-site class |
|---|
| 概要 Descriptions |
計算幾何学とは，幾何学の問題を効率よく解くアルゴリズムを開発したり，その計算量を解析したりする計算機科学の一分野である． この授業では，計算幾何学への入門として2次元，3次元の線形計画問題を説明した後，代表的な問題をいくつか取り上げ，問題に関わる図形の性質，問題を解くために利用するデータ構造，問題を効率よく解くアルゴリズムについて説明する． 担当教員が企業の研究員のときに計算幾何学を利用した例なども取り上げる予定である． |
|---|---|
| 目的 Objectives |
本科目は本学科のカリキュラム・ポリシーに定める「数学を中心とする基礎教育と，応用領域を基盤とする最先端の多様な専門教育」のうちの専門教育に該当する科目の一つであり，ディプロマ・ポリシーに定める「数学を中心とする基礎知識を習得し、数学の応用領域を体系的かつ統合的に理解できる能力」の一部を身につけること，具体的には，計算幾何学で用いる基本的な概念，データ構造，アルゴリズムについて理解することが目的である． |
| 到達目標 Outcomes |
(1) 凸包の性質および2次元の凸包構成法を理解すること． (2) 超平面アレンジメントの定義，性質，構成法を理解すること． (3) 三角形分割の定義と性質，Voronoi 図と Delaunay 三角形分割の構成法を理解すること． (4) 代表的な幾何学的探索問題を解くアルゴリズムを理解すること． |
| 履修上の注意 Course notes prerequisites |
とくになし． |
| アクティブ・ラーニング科目 Teaching type（Active Learning） |
|||
|---|---|---|---|
| 課題に対する作文 Essay |
- | 小テストの実施 Quiz type test |
- |
| ディベート・ディスカッション Debate/Discussion |
○ | グループワーク Group work |
- |
| プレゼンテーション Presentation |
○ | 反転授業 Flipped classroom |
- |
| その他（自由記述） Other（Describe） |
- | ||
| 準備学習・復習 Preparation and review |
授業時間中に適宜，演習の時間を取り解いた問題を解説してもらうので，できるだけ事前に問題を解いておくこと． |
|---|---|
| 成績評価方法 Performance grading policy |
到達度評価試験50%，レポート30%，演習20%の割合で評価する． レポートはテーマ(1)が終了する第6回終了後，到達目標(1)に関する基本的な問題を出題する．解説は到達度評価試験前にLETUSに掲載する．到達度評価試験は授業全体の範囲から基本的な問題を出題する． レポートの提出，演習で少なくとも1問解くことを必須とし，一方でも欠けた場合は科目全体の成績を「-」とする． |
| 学修成果の評価 Evaluation of academic achievement |
・S：到達目標を十分に達成し、極めて優秀な成果を収めている ・A：到達目標を十分に達成している ・B：到達目標を達成している ・C：到達目標を最低限達成している ・D：到達目標を達成していない ・-：学修成果の評価を判断する要件を欠格している ・S：Achieved outcomes, excellent result ・A：Achieved outcomes, good result ・B：Achieved outcomes ・C：Minimally achieved outcomes ・D：Did not achieve outcomes ・-：Failed to meet even the minimal requirements for evaluation |
| 教科書 Textbooks/Readings |
・教科書を使用する場合は、MyKiTS(教科書販売サイト)から検索・購入可能ですので以下のURLにアクセスしてください。 https://gomykits.kinokuniya.co.jp/tokyorika/ ・Search and purchase the necessary textbooks from MyKiTS (textbook sales site) with the link below. https://gomykits.kinokuniya.co.jp/tokyorika/ |
| 参考書・その他資料 Reference and other materials |
【参考書】 今井浩，今井桂子，計算幾何学，共立出版，1994. M. ドバーグ，M. ファン クリベルド，M. オーバマーズ，O. チョン，コンピュータ・ジオメトリ―計算幾何学：アルゴリズムと応用，近代科学社，2010. 【その他資料】 講義資料をLETUSに掲載する． |
| 授業計画 Class plan |
第1回：計算幾何学とは 計算幾何学とはどのような分野であるかを理解する． 第2回：低次元線形計画問題(1) 高速なアルゴリズムを実現する有効なパラダイムである縮小法について理解する． 第3回：低次元線形計画問題(2) 縮小法を利用して線形計画問題を解くアルゴリズムについて理解する． 第4回：低次元線形計画問題(3) ランダム抽出を利用して線形計画問題を解くアルゴリズムについて理解する． 第5回：凸包(1) 凸包の定義と性質，および，2次元の凸包を構成する Graham のアルゴリズム，包装法について理解する． 第6回：凸包(2) 2次元の凸包を構成する分割統治法，およびそれに線形計画法を組合せたアルゴリズムについて理解する． 第7回：アレンジメント(1) 超平面のアレンジメントの定義と性質について理解する． 第8回：アレンジメント(2) 超平面と点との間の双対性，および，超平面と点との間の双対変換について理解する． アレンジメントの応用についても理解する． 第9回：アレンジメント(3) アレンジメントの構成法について理解する． 第10回：三角形分割(1) 三角形分割の定義と性質について理解する． 第11回：三角形分割(2) Voronoi図とDelaunay三角形分割の構成アルゴリズムについて理解する． 第12回：三角形分割(3) Delaunay三角形分割の性質について理解する． 第13回：幾何学的探索(1) 幾何学的データ探索の代表的なデータ構造であるヒープ探索木と区分木について理解する． 第14回：幾何学的探索(2) 点位置決定問題を解くアルゴリムについて理解する． 第15回：到達度の確認と解説 本科目の授業内容に関する到達度の確認と解説を行う． |
|---|
| 教職課程 Teacher-training course |
|
|---|---|
| 実務経験 Practical experience |
情報通信関係企業の研究員の勤務実績を活かし講義する． |
| 教育用ソフトウェア Educational software |
Python, Mathematica |
| 備考 Remarks |
|---|
| 9914B72 |
