授業科目

アルゴリズム論
Algorithms 

担当者

教授   後藤 智範
前 火1

単位

2

到達目標

受講者が以下の内容について理解、修得することを目標とする。
  (1) 動的ハッシュ法
  (2) 基数探索木
  (3) 高度な探索アルゴリズム
  (4) グラフアルゴリズム
さらに、上記アルゴリズムのプログラミング言語(C言語プログラム)レベルでの論理構造を理解、修得することを目標とする。

授業内容

 本講は、大規模データ処理、特にデータベース・システム、テキスト・マイニング、検索エンジン、および自然言語処理ソフトウェアにおいて、実際に実装されているアルゴリズムについて、データ構造、操作関数の論理構造について詳説する。
 なお、受講希望者は担当者の下記サイトの該当ページに詳細が記述されているので必ず参照すること。
 http://angelos.info.kanagawa-u.ac.jp/
 上記URLにおいて、左フレームの担当科目から当科目のpageにアクセスすることができる。
本講義は高度かつ複雑なアルゴリズムを対象としているため、受講者は下記の全ての科目を単位取得していることが必要とされる(詳細は、当該ウェブページを参照)。
      1年次: プログラミングⅠ、プログラミング演習Ⅰ
      2年次: プログラミングⅡ、プログラミング演習Ⅱ
          アルゴリズム論Ⅰ、情報科学実験Ⅰ(ソフトウエア編)

授業計画

 各回の講義は以下を予定している。
  第 1回 ハッシュ法Ⅲ: 外部ハッシュ法
  第 2回 ハッシュ法Ⅳa: 拡張ハッシュ法(データ構造)
  第 3回 ハッシュ法Ⅳb: 拡張ハッシュ法(基本関数)
  第 4回 木構造Ⅶa: 離散探索木
  第 5回 木構造Ⅷb: Trie, MPTrie
  第 6回 木構造Ⅷc: PATRICIA
  第 7回 文字列探索Ⅱa: 複数文字列探索
  第 8回 文字列探索Ⅱb: NFSAによる複数文字列探索
  第 9回 文字列探索Ⅲa: 近似文字列探索: soundex, Metaphone
  第10回 文字列探索Ⅲb: 準汎用近似文字列探索
  第11回 グラフⅣ: 縦型探索(有向グラフ)
  第12回 グラフⅤ :横型探索(有向グラフ)
  第13回 グラフⅥ: 重み付グラフ、ラベル付きグラフ
  第14回 受講者による演習課題レポートの発表(60分)と解説および質疑応答(40分)
 講義内容により難易度の相違があり、受講者個人にとって十分理解できないこともある。したがって、各回毎に以下のような予習・復習をすることがが望ましい。
  予習(1時間):    事前に各回の講義内容のテキスト(PDFファイル)を読む。
  復習(1~1.5時間): 理解が不十分な概念・事柄について、テキストの該当箇所を再度読見直す。
上記以外にOffice Hourの時間帯に質問も受け付ける。

授業運営

全て講義形式による。授業運営の詳細については、上記web pageに掲載する。本講義の最終回を受講者による演習課題の説明・発表にあてる。

評価方法

アルゴリズムの実装技術の向上を意図し、1回/1人の演習課題を課する。提出された演習課題レポート(計測値、プログラム説明、出力結果の分析、等)、およびその発表(説明)をもとに評価する。

オフィスアワー

日時: 月曜日14:00~17:00 および 火曜日13:30~17:00
 場所: 2-205

使用書

 使用テキストは、【授業内容】で挙げた担当者のHPにおいて、各回毎にPDFとして掲載されている。使用テキストにアクセスするためには、password、userIDを必要とするが、第1回目の講義の際に提示する。各自、このPDFファイルをダウンロードし、printerに出力する。

参考書

上述のweb pageにリストが掲載されている。

Copyright© 2017 Kanagawa University. All Rights Reserved.