授業科目名				担当教員
離散構造システム特論				岩沼　宏治／鍋島　英知／クップル　ドミニク
時間割番号	単位数	コース	履修年次	期別	曜日	時限
PTW713	2	(未登録)	1	後期	木	V
［概要と目標］
情報を計算という切り口で捉える立場は20世紀中葉にはじまり, 現在では記号や離散データの計算に関する数学理論が, コンピュータ科学の重要な基盤となっている．更にこのアプローチは，混沌とした情報の中から新たな知識を紡ぎ出すマイニング技術や, 膨大な組み合わせの中から制約条件を満たす解を探し出す技術へと広がっている．本講義は, 計算という立場から種々の情報処理の本質を学ぶことを目的としている．講義の第1部では, 離散データマイニングに焦点をあて，その理論と技術について解説する．第2部では，コンピュータ科学における最重要問題の1つである命題論理の充足可能性判定問題とその高速解法，実応用を含む種々の適用事例を示す．各テーマにおける最新の研究事例についても概観することで, 各々における現状と課題について議論する．第3部では，大規模なデータに対する簡潔なデータ構造の解析に焦点を当てる．データ構造の理論的な基礎から最新研究結果までを網羅し，データの効率的な管理と解析を行うための手法を習得する．基本的なデータ構造の概念，アルゴリズムの効率性，およびデータ構造の選択基準などがテーマに含まれる．
[到達目標]
講義の第1部では, 離散データマイニング, WEBインテリジェンスに関する基礎理論・最新技術について理解する. 第2部では，命題論理の充足可能性判定問題の基礎と最新技術，応用手法について理解する．第3部では，データ構造の理解と適用，アルゴリズムの効率性の評価，およびデータ構造の選択と設計を行う．
［必要知識・準備］
コンピュータによるデータ処理の基盤を支える離散・組合せ数学，確率統計，数理論理，アルゴリズムとデータ構造, プログラミング言語論，情報理論などにに関する基礎的な事項を理解していることが望ましい．
［評価基準］
No 評価項目 割合 評価の観点 1 小テスト／レポート  100  % 各部分で課されるレポートにより評価する.
［教科書］
(未登録)
［参考書］
edited by Armin Biere ... [et al.], Handbook of Satisfiability 2nd Edition, IOS Press, ISBN:9781643681603, (2021年出版 Frontiers in artificial intelligence and applications, v. 336)
［講義項目］
講義はライプ型授業とオンデマンド型の授業を組み合わせて行う． 第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. パターン照合の拡張
［前年度授業に対する改善要望等への対応］
前年度と同様に実施する