講義ノート

第 1 回: 紹介(04.01.2011) (月)

基礎ゼミ (輪講形式)

テームを決めて, 勉強すること

スライドを作って, プレゼンテーションをやること (できるだけ, わかりやすい内容を作る)

一人は (50 分ぐらい)

週 2 回

教科書:

1. メターヒューリスティクスの数理
2. プログラミングのための確率統計
3. Hadoop 徹底入門 (オープンソース分散処理環境の構築)

来週 (1 章ずつ, やっていく)

おはようトーク (毎朝, 9:45)

研究テーマは(先生と相談すること)

キーワード::

数理計画 (数式) 並列処理 ネット理論

ネット理論 -> 数理計画 -> 並列処理

応用, 高性能並列分散処理:

バイオ処理 (大規模なデータもある) 大規模な数理計画 GPGPU, 高並列 (注目) 大規模分散処理

問題点:

並列しづらい問題がたくさんある

暗号通信 (公開鍵, 秘密鍵)

共通鍵 (EOR)

Android インタラクティブな計算

安定結婚問題 (複数の基準を持って, 安定なマッチング) (1 週間ぐらい, テーマを決める)

Google DNS Server: 8.8.8.8

安定結婚問題: 安定マッチング問題の一つで, 1962 年提唱された問題.

Gale & Shapley

どんな例題にも, 必ず安定マッチングが存在する.

安定マッチングを多項式時間で見つけることができる (Gale-Shapley アルゴリズム)

Apache Cassandra と Apache Hadoop を一体化した [Brisk] 発表

Apache Software Foundation (ASF)

Hadoop::

大規模なデータを処理するための並列分散処理基盤

Hadoop の適用領域は [テラバイトあるいはベタバイトクラスのデータのバッチ処理]

RDBMS: オンライン処理むけ Hadoop: バッチ処理むけ

Hadoop の動作モード:

1. ローカルモード (1 台のサーバで, HDFS を利用せずに MapReduce の動作環境を構築する)
2. 擬似分散モード (1 台のサーバで, HDFS 環境と MapReduce 環境を構築する)
3. 完全分散モード (複数サーバを利用し, 本格的な HDFS 環境と MapReduce 環境を構築する)

ペトリネット理論 (1960 年代にドイツ人の Carl Adam Petri によって考案された理論的計算モデル)

並行動作, 分散状態, 資源の概念を表現可能なオートマトン

数学的モデル + 図的言語

ペトリネットは 2 種類の頂点:

transition(トランジション, □ )
place(プレース, ○ )

同じプレースに複数のトークンがあった場合, それらは区別されない, 個数のみが意味を持つ.

ペトリネットは, システムの状態の変化を記述することができる.

トークンが移動することを [トランジションが発火する] という.

ペトリネットはシステムを構成する際のグラフィック言語としての能力, システムのしニュレーションとしての能力, システムの安全性, デッドロック検証などの解析を行う能力を持っている.

トランジションが発火するには, 入力プレースがすべてトークンを持たなければならない.

ネットにおけるトークンの配置 [マーキング]

petrinet の利点は 解析力があげられる

離散事象システムの特徴:

1. 非決定性
2. 非同期性
3. 並行性

ハイブリッドペトリネットによる歩行者を考慮した交通流:

離散プレース: トークンは整数個 -> 信号機
連続プレース: トークンは実数個 -> 交通流

歩行者, 自動車によりよい信号機の周期を計算.

センサネットワーク (Wireless Sensor Networks, WSN), M2M (Machine to Machine) で使用するコア技術.

モバイルアドホックネットワーク (mobile ad hoc network, MANET)