[B! algorithm] satzzのブックマーク

3/29 19:00@INAX:GINZA アルゴリズム討議 (roundabout journal)

satzz 2010/04/01

田中浩也先生刊行記念

リンク

安定結婚問題（あんていけっこんもんだい、英: stable marriage probl em）とはデイヴィッド・ゲールとロイド・シャプレイによって1962年に提示された問題である。安定結婚問題は n 人の男性と k 人の女性、および、各個人の選好順序からなる。選好順序とは各個人の好みに基づき異性全員と自分自身を全順序で並べたリストである。ここで、「自分自身」とは誰とも結婚せずに独身のままでいることを意味し、「参加者全員が独身であるよりも望ましい相手と結婚している」マッチングは個人合理性（英: individuality rationality）を満たすと定義される。安定結婚問題の解は安定なマッチングである。安定結婚問題に対し、互いに現在組んでいる相手よりも好きであるペア（以下ブロッキングペアとする）が存在せず、全員が個人合理性を満たすマッチングを安定マッチング（英: stable ma

satzz 2010/01/27

リンク

Prediction by Partial Matching - Wikipedia

Prediction by Partial Matching(PPM)は1984年にJ.G.ClearyとI.H.Wittenによって考案されたデータ圧縮アルゴリズムの1つ。この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。この亜種としてPPMC、PPMd、PPMZ等がある。符号化の原理[編集] aabacaabbaとデータを符号化したとして、次にどの記号が出現するかを統計的に予測する。この場合、統計的にaの次にはaが出現する可能性が高い。逆にcが出現する可能性は低いであろう。このように出現確率に偏りがあるとハフマン符号や算術符号で圧縮することが出来る。しかし、上記の場合に次に出現する符号をaを50%、bを40%、cを10%と予測したとすると、他の記号は絶対に現れないということになり、新たな記号(dとする

satzz 2010/01/27

リンク

研究会 - 共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良

2005-06-24 13:15 共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良 ○小林浩二・宮崎修一・岡部寿男（京大）オンラインバッファ管理問題は，近年のネットワーク運用における主要な論点なっているQoS (Quality of Service) 保証実現のための，スイッチなどのキュー管理をオンライン問題として定式化した問題であり，様々なモデルが考案されている．本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる．我々は，既知のアルゴリズムLongest Queue Policy ($LQD$) の競合比の既知の上限を$2 - 1/N$に改良した．ここで，$N$はスイッチの出力ポートの数である． The buffer management probl em is a kind of online probl ems, which

satzz 2010/01/19

2005/6

algorithm

リンク

なんでも焦点:水などの流体の音をCGと完全にシンクロして自動生成するアルゴリズムが世界で初めて開発される（ビデオあり）

水が注がれたり飛び散ったりするときの音、紙が破れる音、手拍子、木を揺らす風の音、ワイングラスが床に落ちる音などは、コンピュータによるシミュレートが難しいという。このため、コンピュータグラフィック（CG）にこれらの音を付けるときは、録音しておいた生の音をCGが出来上がってから追加するか、「フォーリーアーティスト」たちの助けを借りなければならない。コーネル大学コンピュータサイエンス学部（ニューヨーク州イサカ市）の研究者たちは、従来シミュレートが困難とされてきたこれらの自然音を自動生成するアルゴリズムの開発に成功したという。下のCG（Youtube映像）には、その新しいアルゴリズムが採用されている。実際に聞いてみると、確かにCGと完全にシンクロした音だ。少し違和感を覚えるものの、なんの予備情報もなく聞いたら、実に自然に聞こえるだろう。このアルゴリズムは、CGの中に存在するオブジェクト