|
授業科目名
|
担当教員
|
|||||||||||||
|
大規模離散構造処理特論
|
岩沼 宏治／鍋島 英知
|
|||||||||||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
||||||||
| GTK501 | 2 | (未登録) | 1,2 | 後期 | 金 | I | ||||||||
| ［概要と目標］ | ||||||||||||||
| 現代社会を支えるシステムやデータは，高度に大規模化し複雑化している．これらのシステムやデータを効果的に構築し利用することは重要な課題であるが，その実現は実際には極めて難しい．これらのシステムやデータには，一般に大規模な離散的構造が内在しており，その効果的かつ高度な処理を実現を支える理論と技術の重要性が近年高まっている．本講義では，大規模離散構造処理の理論と実際を学ぶために，前半では，大規模離散データマイニングシステムの理論と技術について学ぶ．後半では，命題論理における様々な高速アルゴリズムが大規模離散データにおける実用問題の解決に有用であることを学ぶ．なお、本授業はコンピュータ理工学コースのディプロマポリシーで定めた専門知識・技術(A2)に対応する。 | ||||||||||||||
| [到達目標] | ||||||||||||||
|
（１）大規模離散データの高速マイニング技術の基礎と幾つかの最新の話題について理解する． （２）命題論理における各種高速アルゴリズムとその大規模離散データへの応用手法について理解する． |
||||||||||||||
| ［必要知識・準備］ | ||||||||||||||
| プログラミング，アルゴリズムとデータ構造，離散数学，ブール代数，データベース理論，確率統計，情報理論．以上の専門知識がないと本授業の単位修得は困難であるので、十分に検討の上履修すること。 | ||||||||||||||
| ［評価基準］ | ||||||||||||||
|
||||||||||||||
| ［教科書］ | ||||||||||||||
| (未登録) | ||||||||||||||
| ［参考書］ | ||||||||||||||
|
||||||||||||||
| ［講義項目］ | ||||||||||||||
| 講義はライプ型授業とオンデマンド型の授業を組み合わせて行う． 第１回 離散マイニング：大規模離散データのマイニングの概要（担当 岩沼） 第２回 離散マイニング：頻出アイテム集合と相関ルール（担当 岩沼） 第３回 離散マイニング：小メモリを前提とする高速計算法（担当 岩沼） 第４回 離散マイニング：大規模メモリを前提とする高速計算法（担当 岩沼） 第５回 離散マイニング：相関ルールの妥当性の統計学的な評価法（担当 岩沼） 第６回 離散マイニング：クラスタリングの基礎その１（K-平均法，階層集約法）（担当 岩沼） 第７回 離散マイニング：クラスタリングの基礎その２（密度法，クラスタリング結果の統計学的評価）（担当 岩沼） 第８回 離散アルゴリズム：命題論理における高速アルゴリズムと大規模離散データへの応用手法概観（担当 鍋島） 第９回 離散アルゴリズム：整数線形計画問題・制約充足問題とその解法（担当 鍋島） 第１０回 離散アルゴリズム：命題論理式の充足可能性判定(SAT)問題とその基本アルゴリズム（担当 鍋島） 第１１回 離散アルゴリズム：高速SATソルバーの原理と実装（担当 鍋島） 第１２回 離散アルゴリズム：SAT 型制約充足ソルバーの解法（直接符号化，対数符号化，順序符号化）（担当 鍋島） 第１３回 離散アルゴリズム：命題論理式のコンパクトな表現手法 (BDD, ZDD) と演算アルゴリズム（担当 鍋島） 第１４回 離散アルゴリズム：BDD, ZDD の応用手法（担当 鍋島） 第１５回 全体の復習とまとめ（担当 岩沼，鍋島） |
||||||||||||||
| ［前年度授業に対する改善要望等への対応］ | ||||||||||||||
| 前年度と同様に実施する | ||||||||||||||