オフラインオンラインストリームリアルタイムバッチアルゴリズム

アルゴリズムデザイン勉強会でのこと。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

オンラインアルゴリズムとか、リアルタイムアルゴリズムのあたりの概念が、僕の頭に整頓されず入っていたので、参加者と議論して簡単に整頓しました。

以下、メモ。

■オフラインアルゴリズム : 問題を解く際に、最初から入力データ全体にアクセスする必要がある
■オンラインアルゴリズム : 問題を解く際に、最初から入力データ全体にアクセスする必要がなく、先頭から順に処理していけば大丈夫

■オンラインアルゴリズム : 時系列になっている入力データを蓄積しながら、実時間で処理して、未知の未来の結果の推測する
■ストリームアルゴリズム : 時系列になっている入力データをほぼ蓄積せず、実時間で処理して、結果を取得

■リアルタイムアルゴリズム（実時間適応アルゴリズム） : ある一定の時間内に所定の処理を完了する。一定時間の定義は「人間がある状況で待てる」や「機械が動作する際にできる隙間時間、1/1000秒以内に」とか、状況により変わる。

■ソフトリアルタイム : 次の処理が間に合わないと分かるときに、次の次をリアルタイム処理すれば許されるような制約が課される状況。動画処理のコマ落ちとか。
■ハードリアルタイム : 全てのタイミングで必ずリアルタイム処理が必要となる制約が課される状況。車のエンジンとか。

■静的適応 : 問題に対するアルゴリズムが時間的に不変
■動的適応 : 問題に対するアルゴリズムが時間と共に変動

■リアルタイム処理 : 入力データを即座に処理し、結果を出力する。
■バッチ処理 : 入力データを一定期間蓄積した後、まとめて処理し、結果を出力する。

OS関係の参考書や、以下の参考書を読むと良いみたいです。

■関連リンク
- オンラインアルゴリズム (Online Algorithms)
-- http://www.al.ics.saitama-u.ac.jp/horiyama/online/

投稿者:としのり日時:23:59:59 | コメント | トラックバック() |