|
授業科目名
|
担当教員
|
|||||||||||||
|
大規模離散構造処理特論
|
岩沼 宏治／鍋島 英知
|
|||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||
| GTK501 | 2 | (未登録) | 1,2 | 後期 | 金 | I | ||||||||
| ［概要と目標］ | ||||||||||||||
| 現代社会を支えるシステムやデータは，高度に大規模化し複雑化している．これらのシステムやデータを効果的に構築し利用することは重要な課題であるが，その実現は実際には極めて難しい．これらのシステムやデータには，一般に大規模な離散的構造が内在しており，その効果的かつ高度な処理を実現を支える理論と技術の重要性が近年高まっている．本講義では，大規模離散構造処理の理論と実際を学ぶために，前半では，大規模離散データマイニングシステムの理論と技術について学ぶ．後半では，命題論理における様々な高速アルゴリズムが大規模離散データにおける実用問題の解決に有用であることを学ぶ． | ||||||||||||||
| [到達目標] | ||||||||||||||
| （１） 大規模離散データの高速マイニング技術の基礎と幾つかの最新の話題について理解する．<BR>（２） 命題論理における各種高速アルゴリズムとその大規模離散データへの応用手法について理解する． | ||||||||||||||
| ［必要知識・準備］ | ||||||||||||||
| アルゴリズムとデータ構造，離散数学，ブール代数，データベース理論，確率統計，情報理論 | ||||||||||||||
| ［評価基準］ | ||||||||||||||
|
||||||||||||||
| ［教科書］ | ||||||||||||||
| (未登録) | ||||||||||||||
| ［参考書］ | ||||||||||||||
| ［講義項目］ | ||||||||||||||
| 第１回 離散データマイニング：大規模離散データのマイニングの概観（担当 岩沼）<BR>第２回 離散データマイニング：相関ルールマイニングの基礎 （探索空間の構造，逆単調性，極大性と飽和性）（担当 岩沼）<BR>第３回 離散データマイニング：高速な出現頻度計算法 （ハッシュ木法，垂直フォーマット法）（担当 岩沼）<BR>第４回 離散データマイニング：分割統治型マイニング （射影法，FP木とFP成長法）（担当 岩沼）<BR>第５回 離散データマイニング：より進んだマイニング理論と技術 （BIDE法，Prefix-Span法）（担当 岩沼）<BR>第６回 離散データマイニング：相関ルールの評価尺度（情報理論や確率統計学的な評価尺度）（担当 岩沼）<BR>第７回 離散データマイニング：ストリームデータマイニング（オンライン処理，誤差保証型近似計算）（担当 岩沼）<BR>第８回 離散アルゴリズム：命題論理における高速アルゴリズムと大規模離散データへの応用手法概観（担当 鍋島）<BR>第９回 離散アルゴリズム：整数線形計画問題・制約充足問題とその解法（担当 鍋島）<BR>第１０回 離散アルゴリズム：命題論理式の充足可能性判定(SAT)問題とその基本アルゴリズム（担当 鍋島）<BR>第１１回 離散アルゴリズム：高速SATソルバーの原理と実装（担当 鍋島）<BR>第１２回 離散アルゴリズム：SAT 型制約充足ソルバーの解法（直接符号化，対数符号化，順序符号化）（担当 鍋島）<BR>第１３回 離散アルゴリズム：命題論理式のコンパクトな表現手法 (BDD, ZDD) と演算アルゴリズム（担当 鍋島）<BR>第１４回 離散アルゴリズム：BDD, ZDD の応用手法（担当 鍋島）<BR>第１５回 全体の復習とまとめ（担当 岩沼，鍋島） | ||||||||||||||