シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
アルゴリズム工学特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced Topics on Algorithmic Engineering | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅱ | ||
| 開講学科・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
古賀 久志 | ||
| 居室 /Office |
西10-832 | ||
| 公開E-Mail |
koga@sd.is.uec.ac.jp | ||
| 授業関連Webページ /Course website |
なし | ||
| 更新日 /Last updated |
2020/03/20 20:08:08 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
ビッグデータの時代においては、大量のデータ群からいかに目的のデータに高速に検索してアクセスするかがシステム性能に影響を与える重要なファクターである。 そこで、本講義では、代表的なデータ探索アルゴリズムをその理論的なバックグラウンドとともに理解することを目的とする。データ探索アルゴリズムに焦点を絞ることで学部レベルのデータ構造とアルゴリズムの授業ではカバーできないようなアルゴリズムを紹介したい。 Course Aims: In the big-data err, the performance of information systems is determined by their speed to search the objective data from very large database. The objective of this course is to understand various search algorithms along with their theoretical backgrounds. Especially, this course deals with advanced search algorithms which are not covered by the undergraduate-level algorithms and data structures. |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
学部レベルの「アルゴリズムとデータ構造」に関する知識を持っていることを前提とする。離散数学についても勉強しておくこと。 Course Prerequisites: Students are assumed to be familiar with the undergraduate-level algorithms and data structures. Students should also have some knowledge of discrete mathematics. |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
確率論 Probabilistic Theory |
| 教科書等 /Course textbooks and materials |
毎回の講義でレジュメを配布する。 Text Book: This course does not use any textbook. A summary of the lecture is distributed to the students at every class. |
| 授業内容と その進め方 /Course outline and weekly schedule |
本講義では、データ探索アルゴリズムについて集中的に講義する。具体的には、以下のようなアルゴリズムについて論じる。 第１回： ガイダンス 第２回：Markovの不等式とChebyshevの不等式 第３回：確率的選択アルゴリズム 第４回： SPLAY木のアルゴリズム 第５回：SPLAY木の理論解析 第６回：kd-tree 第７回： 四分木 第８回： R-木 第９回： 高次元データに対する類似検索 第１０回： Locality Sensitive Hashing: ハッシュ関数 第１１回： Locality Sensitive Hashing: 最近傍探索 第１２回：Jaccard係数とMin Hash 第１３回：文字列の類似度 第１４回：スカイライン検索 第１５回：ストリームデータに対する類似検索 適宜レジュメを配布し、レジュメに記載されている内容を解説する形で講義を行う。 Course Contents: This course teaches various topics on information retrieval. The course contents are shown below. 1. Introduction 2. Markov Inequality and Chebyshev's Inequality 3. Randomized Selection 4. Splay Tree 5. Theoretical Analysis of Splay Tree 6. kd-tree 7. Quad Tree 8, R tree 9. Similarity Search in high-dimensional spaces 10, Locality-Sensitive Hashing; Hash Function 11. Locality-Sensitive Hashing: Nearest Neighbor Search 12. Jaccard Coefficient and Min Hash 13. Similarity Measure for Strings 14. Skyline Computation 15. Similarity Search for Stream Data I will teach this class with explaining the contents of the handouts distributed to students. |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
予習は不要ですが、復習には力をいれること。 Preparation and Review: No preparation is required before the classes. Instead, please take much effort for the review after the classes. |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
成績評価方法： 学期中と学期末レポートによって成績評価を実施する。 評価基準： 以下の到達レベルをもって合格の最低基準とする ・授業で講義した探索アルゴリズムの動きを理解して説明できること ・Markovの不等式とChebyshevの不等式を理解して授業で説明する問題と同程度の 難易度の例題に適用できること Grading Policies: Your final grade will be decided based on the mid-term report and the end-term report. To pass, students must be able to do the following at the end of the course. - Understand and describe the behavior of algorithms taught in this course - Apply the Markov Inequality and Chebyshev's Inequality to the analysis of randomized processes which are as complex as those treated in the lecture. |
| オフィスアワー： 授業相談 /Office hours |
オフィスアワーは特に設けない。質問は授業終了後の昼休みに受け付ける。また、メールでの質問も受け付ける。 Office Hours: I do not fix specific office hours. Students are welcomed to ask questions to me at recess after the classes. Students may ask questions via e-mail. |
| 学生へのメッセージ /Message for students |
情報検索分野では、様々な検索問題が定義され、それに対するアルゴリズムが提案されています。情報検索アルゴリズムは、プログラムの1部品なので目にする機会は少ないですが、こんな問題も解けるんだということを知っているだけでも、実現可能なプログラムの幅が全く変わります。 Message to Students: In the area of information retrieval, various new problems have been formulated and algorithms to solve these problems have been invented so far. Knowledge of the latest search algorithms will make it possible for programmers to implement programs of high functionality, though search algorithms are rarely noticed by end users of information systems. |
| その他 /Others |
講義は日本語で実施される. This course will be taught in Japanese. |
| キーワード /Keyword(s) |
データ構造とアルゴリズム, データ探索 Algorithms and Data Structures, Information Retrieval |