◆ 講義概要
本講では、大規模データ処理、特にデータベース・システム、テキスト・マイニング、検索エンジン、および仮名漢字変換を含む自然言語処理ソフトウェアにおいて、実際に実装されているプログラムが依拠しているアルゴリズムについて、データ構造、操作関数の論理構造について詳説します。
本講で採り挙げているアルゴリズムには、全てC言語コードが付記されているので、実行することにより動作確認ができます。
◆ 受講者
・本講義で詳説するアルゴリズムは、非常に高度かつ複雑であるため、以下に示されるように、アルゴリズム論Ⅰ、および情報科学実験Ⅰ(ソフトウエア編)の単位取得が前提となります。
アルゴリズム論Ⅰ(2年、前期)
↓
情報科学実験Ⅰ(ソフトウエア編)(2年、後期)
↓
アルゴリズム論Ⅱ(3年、前期)
・受講者に対して演習課題を課すため、以下の全科目について単位を取得していることが必要とされます。
1年次: プログラミングⅠ、プログラミング演習Ⅰ
2年次: プログラミングⅡ、プログラミング演習Ⅱ
◆ 講義計画(2020年度)
講義テキストを事前にダウンロードし、よく読んで概要を理解しておいてください。
期日 回 数 講義内容(テキスト: PDFファイル)
5.12 第 1回
ハッシュ法Ⅲ 外部ハッシュ法
講義録画
演習課題
外部ハッシュ法補足資料
5.19 第 2回
木構造Ⅶ: 離散探索木(DST)
講義録画
演習課題
5.26 第 3回
木構造Ⅷ: Trie
講義録画
演習課題
2分TRIE ヒント
6. 2 第 4回
木構造Ⅸ: MPTRIE
講義録画
演習課題
6. 9 第 5回
木構造Ⅹ: PATRICIA
講義録画
演習課題
6.16 第 6回
文字列探索Ⅱ: 準汎用近似文字列探索
講義録画
演習課題
6.23 第 7回
整列法Ⅴ: 基数整列法
講義録画
演習課題
6.30 第 8回
整列法Ⅲ: ヒープ、ヒープソート
講義録画
7. 7 第 9回
整列法Ⅳ: 併合整列法
講義録画
演習課題
7.14 第10回
並列処理Ⅰ: 並列整列
講義録画
7.21 第11回
並列処理Ⅱ: 並列探索
講義録画
7.28 第12回
受講者による演習課題レポートの発表
解説および質疑応答
演習課題発表者
補遺1 ハッシュ法Ⅳa: 拡張ハッシュ法 演習課題
◆ 参考書
◆ 出席・演習課題・評価