シラバス参照 |
講義概要/Course Information |
科目基礎情報/General Information |
授業科目名 /Course title (Japanese) |
情報システム基礎論2 | ||
---|---|---|---|
英文授業科目名 /Course title (English) |
Foundations of Information Systems 2 | ||
開講年度 /Academic year |
2019年度 | 開講年次 /Year offered |
全年次 |
開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
科目区分 /Category |
選択科目 | ||
開講類・専攻 /Cluster/Department |
情報システム基盤学専攻 | ||
担当教員名 /Lecturer(s) |
古賀 久志 | ||
居室 /Office |
西10-832 | ||
公開E-mail |
koga@is.uec.ac.jp | ||
授業関連Webページ /Course website |
なし | ||
更新日 /Last update |
2019/02/23 18:16:11 | 更新状況 /Update status |
公開中 /now open to public |
講義情報/Course Description |
講義の狙い、目標 |
ビッグデータの時代においては、大量のデータ群からいかに目的のデータに高速に検索してアクセスするかがシステム性能に影響を与える重要なファクターである。 そこで、本講義では、代表的なデータ探索アルゴリズムをその理論的なバックグラウンドとともに理解することを目的とする。データ探索アルゴリズムに焦点を絞ることで学部レベルのデータ構造とアルゴリズムの授業ではカバーできないようなアルゴリズムを紹介したい。 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. |
---|---|
内容 |
本講義では、データ探索アルゴリズムについて集中的に講義する。具体的には、以下のようなアルゴリズムについて論じる。 第1回: ガイダンス 第2回:Markovの不等式とChebyshevの不等式 第3回:確率的選択アルゴリズム 第4、5回: SPLAY木 第6回:kd-tree 第7回: 四分木 第8回: R-木 第9回: 高次元データに対する類似検索 第10,11回: Locality Sensitive Hashing 第12回:Jaccard係数とMin Hash 第13回:文字列の類似度 第14回:スカイライン検索 第15回:ストリームデータに対する類似検索 適宜レジュメを配布し、レジュメに記載されている内容を解説する形で講義を行う。 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-5. Splay Tree 6. kd-tree 7. Quad Tree 8, R tree 9. Similarity Search in high-dimensional spaces 10, 11. Locality-Sensitive Hashing 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. |
教科書、参考書 |
毎回の講義でレジュメを配布する。 Text Book: This course does not use any textbook. A summary of the lecture is distributed to the students at every class. |
予備知識 |
学部レベルの「アルゴリズムとデータ構造」に関する知識を持っていることを前提とする。離散数学についても勉強しておくこと。 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. |
演習 |
学期途中に探索アルゴリズムおよび確率に関するレポート課題を出す。 Exercises: There will be a mid-term report on search algorithms and probabilistics. |
成績評価方法 および評価基準 |
成績評価方法: 学期中と学期末レポートによって成績評価を実施する。 評価基準: 以下の到達レベルをもって合格の最低基準とする ・授業で講義した探索アルゴリズムの動きを理解して説明できること ・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. |
その他 /Others |
講義は日本語で実施される. This course will be taught in Japanese. |
キーワード /Keywords |
データ構造とアルゴリズム, データ探索 Algorithms and Data Structures, Information Retrieval |