山梨大学電子シラバス−授業データ

授業科目名

担当教員

大規模離散構造処理特論

岩沼　宏治／鍋島　英知

時間割番号

単位数

コース

履修年次

期別

曜日

時限

GTK501

(未登録)

1,2

後期

金

［概要と目標］

Large-scale Discrete Structure Processing

現代社会を支えるシステムやデータは，高度に大規模化し複雑化している．これらのシステムやデータを効果的に構築し利用することは重要な課題であるが，その実現は実際には極めて難しい．これらのシステムやデータには，一般に大規模な離散的構造が内在しており，その効果的かつ高度な処理を実現を支える理論と技術の重要性が近年高まっている．本講義では，大規模離散構造処理の理論と実際を学ぶために，前半では，大規模離散データマイニングシステムの理論と技術について学ぶ．後半では，命題論理における様々な高速アルゴリズムが大規模離散データにおける実用問題の解決に有用であることを学ぶ．なお、本授業はコンピュータ理工学コースのディプロマポリシーで定めた専門知識・技術(A2)に対応する。

As the Internet explosively has spread, we have experienced a flood of information. Consequently, there is a growing demand for advanced computing techniques which effectively handle large-scale data as much as possible. The purpose of this course is to give students an understanding of large-scale discrete data structures and some core algorithms for efficiently compute them. The first half of this course introduces the basics of transaction data mining and some advanced topics for online approximation mining algorithms for data streams. In the second half of the course, modern algorithms on propositional logic which handle large-scale discrete data and their applications are introduced.

[到達目標]

（１）大規模離散データの高速マイニング技術の基礎と幾つかの最新の話題について理解する．
（２）命題論理における各種高速アルゴリズムとその大規模離散データへの応用手法について理解する．

1) To understand basic natures of huge discrete data and fundamental mining computation principles.
2) To learn modern algorithms on propositional logic for discrete data and their applications.

［必要知識・準備］

プログラミング，アルゴリズムとデータ構造，離散数学，ブール代数，データベース理論，確率統計，情報理論．以上の専門知識がないと本授業の単位修得は困難であるので、十分に検討の上履修すること。

A grounding of linear algebra, analytics, discrete mathematics, Boolean algebra, algorithms and data structure, information theory, and database

［評価基準］

No	評価項目	割合	評価の観点
1	小テスト／レポート	100 %	複数回のレポートによって理解度を評価する．

［教科書］

(未登録)

［参考書］

［講義項目］

講義はライプ型授業とオンデマンド型の授業を組み合わせて行う．
第１回　離散マイニング：大規模離散データのマイニングの概要（担当岩沼）
第２回　離散マイニング：頻出アイテム集合と相関ルール（担当岩沼）
第３回　離散マイニング：小メモリを前提とする高速計算法（担当岩沼）
第４回　離散マイニング：大規模メモリを前提とする高速計算法（担当岩沼）
第５回　離散マイニング：相関ルールの妥当性の統計学的な評価法（担当岩沼）
第６回　離散マイニング：クラスタリングの基礎その１（K-平均法，階層集約法）（担当岩沼）
第７回　離散マイニング：クラスタリングの基礎その２（密度法，クラスタリング結果の統計学的評価）（担当岩沼）
第８回　離散アルゴリズム：命題論理における高速アルゴリズムと大規模離散データへの応用手法概観（担当鍋島）
第９回　離散アルゴリズム：整数線形計画問題・制約充足問題とその解法（担当鍋島）
第１０回　離散アルゴリズム：命題論理式の充足可能性判定(SAT)問題とその基本アルゴリズム（担当鍋島）
第１１回　離散アルゴリズム：高速SATソルバーの原理と実装（担当鍋島）
第１２回　離散アルゴリズム：SAT 型制約充足ソルバーの解法（直接符号化，対数符号化，順序符号化）（担当鍋島）
第１３回　離散アルゴリズム：命題論理式のコンパクトな表現手法 (BDD, ZDD) と演算アルゴリズム（担当鍋島）
第１４回　離散アルゴリズム：BDD, ZDD の応用手法（担当鍋島）
第１５回全体の復習とまとめ（担当岩沼，鍋島）

1. Data mining: basic natures of huge transactional data, mining frameworks and principles (1).
2. Data mining: basic natures of huge transactional data, mining frameworks and principles (2).
3. Data mining: fundamental association rule mining.
4. Data mining: advanced association rule mining.
5. Data mining: measures for evaluating the interestingness of association rules
6. Data mining: basic algorithms for mining a single data stream.
7. Data mining: advanced online approximation algorithms for mining multi-dimensional data streams.
8. Discrete algorithms: introduction of modern algorithms for discrete data.
9. Discrete algorithms: integer programming and constraint satisfaction problem.
10. Discrete algorithms: fundamental of Boolean propositional satisfiability.
11. Discrete algorithms: principles of modern SAT solvers.
12. Discrete algorithms: SAT encoding and SAT based constraint satisfaction solvers.
13. Discrete algorithms: introduction of BDD/ZDD.
14. Discrete algorithms: applications of BDD/ZDD.
15. Summary.

［前年度授業に対する改善要望等への対応］

アンケート結果確認中