授業科目名				担当教員
離散構造システム特論				岩沼　宏治／鍋島　英知
時間割番号	単位数	コース	履修年次	期別	曜日	時限
PTW713	2	(未登録)	1	後期	木	V
［概要と目標］
情報を計算という切り口で捉える立場は20世紀中葉にはじまり, 現在では記号や離散データの計算に関する数学理論が, コンピュータ科学の重要な基盤となっている．更にこのアプローチは，混沌とした情報の中から新たな知識を紡ぎ出すマイニング技術や, 膨大な組み合わせの中から制約条件を満たす解を探し出す技術へと広がっている．本講義は, 計算という立場から種々の情報処理の本質を学ぶことを目的としている．講義前半では, 離散データマイニングとWEBインテリジェンスに焦点をあて，その理論と技術について解説する．後半では，コンピュータ科学における最重要問題の1つである命題論理の充足可能性判定問題とその高速解法，実応用を含む種々の適用事例を示す．各テーマにおける最新の研究事例についても概観することで, 各々における現状と課題について議論する．
[到達目標]
講義前半では, 離散データマイニング, WEBインテリジェンスに関する基礎理論・最新技術について理解する. 後半では，命題論理の充足可能性判定問題の基礎と最新技術，応用手法について理解する．
［必要知識・準備］
コンピュータによるデータ処理に必要なアルゴリズムとデータ構造, 組合せ数学および情報理論に関する基礎的な事項を理解していることが望ましい．
［評価基準］
No 評価項目 割合 評価の観点 1 小テスト／レポート  100  % 前半, 及び後半で課されるレポートにより評価する.
［教科書］
(未登録)
［参考書］
(未登録)
［講義項目］
講義はライプ型授業とオンデマンド型の授業を組み合わせて行う． 1. 大規模離散データのマイニングの概観 2. 相関ルールマイニングの基礎　（探索空間の構造，逆単調性，極大性と飽和性） 3. 高速な出現頻度計算法　（ハッシュ木法，垂直フォーマット法） 4. 分割統治法に基づくマイニング　（射影法，FP木とFP成長法） 5. より進んだマイニング理論と技術　（BIDE法，Prefix-Span法） 6. 相関ルールの統計学・情報理論的な評価 7. ストリームデータマイニング 8. 命題論理の充足可能性問題の基礎 9. 高速SATソルバーの原理 10. インクリメンタルSATと極小充足不能コア 11. 並列SATソルバーの基礎 12. 制約最適化問題とSAT符号化 13. SATによるプランニングとスケジューリング 14. SATによるシステム検証 15. 全体の復習とまとめ