|
授業科目名
|
担当教員
|
|||||||||||||
|
離散構造システム特論
|
岩沼 宏治／鍋島 英知／クップル ドミニク
|
|||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||
| PTW713 | 2 | (未登録) | 1 | 後期 | 火 | V | ||||||||
| ［概要と目標］ | ||||||||||||||
| [Advanced Discrete Structure Systems] Regarding information as a product obtained from computation began in the mid-20th century. Nowadays, mathematical theories of symbolic and/or discrete computation becomes ones of the most important foundations for computer science and information engineering. For example, data mining technologies can derive new valuable knowledge from a huge amount of information. The purpose of this course is to understand some essential features of information science from the viewpoint of computation. This course consists of three parts. The first part is for transactional/sequential data mining. The second part of the course introduces Boolean satisfiability testing (SAT) which is one of the important subjects in computer science and shows the state-of-the-art techniques of modern SAT solvers and their various application areas. In the third part, we study succinct data structures for big data. We cover the theoretical foundations of data structures up to the latest research results, enabling the acquisition of techniques for efficient data management and analysis. For that, we include fundamental concepts of data structures, the study of algorithm efficiency, and criteria for selecting data structures based on efficiency. The course shows the latest case study in each topic and discusses the current status and challenges. 情報を計算という切り口で捉える立場は20世紀中葉にはじまり, 現在では記号や離散データの計算に関する数学理論が, コンピュータ科学の重要な基盤となっている．更にこのアプローチは，混沌とした情報の中から新たな知識を紡ぎ出すマイニング技術や, 膨大な組み合わせの中から制約条件を満たす解を探し出す技術へと広がっている．本講義は, 計算という立場から種々の情報処理の本質を学ぶことを目的としている．講義の第1部では, 離散データマイニングに焦点をあて，その理論と技術について解説する．第2部では，コンピュータ科学における最重要問題の1つである命題論理の充足可能性判定問題とその高速解法，実応用を含む種々の適用事例を示す．各テーマにおける最新の研究事例についても概観することで, 各々における現状と課題について議論する．第3部では，大規模なデータに対する簡潔なデータ構造の解析に焦点を当てる．データ構造の理論的な基礎から最新研究結果までを網羅し，データの効率的な管理と解析を行うための手法を習得する．基本的なデータ構造の概念，アルゴリズムの効率性，およびデータ構造の選択基準などがテーマに含まれる． |
||||||||||||||
| [到達目標] | ||||||||||||||
|
- To understand the basics and state-of-the-art data mining technologies for discrete data. - To understand the basics and state-of-the-art of Boolean propositional satisfiability testing and its applications. - To understand and apply data structures, evaluate algorithms based on their efficiencies, and select and design data structures. - 第1部では, 離散データマイニング, WEBインテリジェンスに関する基礎理論・最新技術について理解する. - 第2部では，命題論理の充足可能性判定問題の基礎と最新技術，応用手法について理解する． - 第3部では，データ構造の理解と適用，アルゴリズムの効率性の評価，およびデータ構造の選択と設計を行う． |
||||||||||||||
| ［必要知識・準備］ | ||||||||||||||
| A strong background in algorithms and data structures, information theory, discrete mathematics, and mathematical logic is desirable. コンピュータによるデータ処理の基盤を支える離散・組合せ数学，確率統計，数理論理，アルゴリズムとデータ構造, プログラミング言語論，情報理論などにに関する基礎的な事項を理解していることが望ましい． |
||||||||||||||
| ［評価基準］ | ||||||||||||||
|
||||||||||||||
| ［教科書］ | ||||||||||||||
| (未登録) | ||||||||||||||
| ［参考書］ | ||||||||||||||
| ［講義項目］ | ||||||||||||||
| First part: Data-mining 1. Introduction of data mining for big discrete data 2. Association rule mining: compression based on closed/maximal itemsets 3. Fast support computation: hash-tree, vertical format computation 4. Mining based on divide and conquer: database reduction and FP-growth method 5. More advanced technology: Prefix-Span, BIDE Second part: SAT and its applications 6. Foundations of Boolean satisfiability testing 7. Principles of Modern SAT Solvers 8. Constraint Optimization Problem and SAT Encoding 9. SAT-based system verification 10. SAT scheduling and planning Third part: Succinct Data Structures 11．Overview of Indexing Discrete Big Data 12．Efficient Pattern Matching 13．Succinct Data Structures 14．Compressed Data Structures 15．Extensions and Variations of Pattern Matching 第1部： 1. 大規模離散データのマイニングの概観 2. 相関ルールマイニングの基礎 （探索空間の構造，逆単調性，極大性と飽和性） 3. 高速な出現頻度計算法 （ハッシュ木法，垂直フォーマット法） 4. 分割統治法に基づくマイニング （射影法，FP木とFP成長法） 5. より進んだマイニング理論と技術 （BIDE法，Prefix-Span法） 第2部 6. 命題論理の充足可能性問題の基礎 7. 高速SATソルバーの原理 8. 制約最適化問題とSAT符号化 9. SATによるシステム検証 10. SATによるスケジューリングとプランニング 第3部： 11．大規模離散データを索引する概観 12．高速のパターン照合 13．簡潔なデータ構造 14．圧縮されたデータ構造 15. パターン照合の拡張 [実施形態] 講義はライプ型授業とオンデマンド型の授業を組み合わせて行う． |
||||||||||||||
| ［前年度授業に対する改善要望等への対応］ | ||||||||||||||
| アンケート結果確認中 | ||||||||||||||