PageRank を応用したアルゴリズムの
最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)
... $v_{q)}v_{q}’$ を $\mathrm{A}1\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{a}\mathrm{t}i\mathrm{n}_{\mathrm{t}\supset}\sigma \mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}^{1}$ と ...
5
絵画的迷路作成アルゴリズムの改善 (アルゴリズムと計算機科学の数理的基盤とその応用)
... 図 4: 絵画的迷路作成のアルゴリズム続き 3 提案アルゴリズム 岡本上原によるアルゴリズムの欠点として、 ス タートとゴールが必ず隣り合っていなくてはならず、 スタートとゴールを自由に指定できないということ があげられる。 しかしパズル雑誌に掲載されている ような絵画的迷路で、 スタートとゴールが隣り合っ ているものは稀である。 そこで、 ...
5
複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)
... 次の補題は, 任意のパラメータ $\beta$ に対して成立する . 補題 1 任意の系列長 $T$ , 任意の賭金の総額 $M$ , 任 意の事象の系列 $y\in\{0,1\}^{T}$ , 任意の予測戦略 $\mathcal{E}=$ $\{\mathcal{E}_{1)}.\text{。}. , ...
6
ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
... $X_{i}$ を導入する， $X_{i}=\{\begin{array}{l}1 with p=\frac{t}{N\theta}0 otherwise\end{array}$ (15) 総計 $N$ 個の要素が入力されることを考える．それぞ れが別種の要素だと仮定すれば， $K$ に $\frac{c}{\theta}$ 個以上入る確 率の上界を ...
4
偏微分作用素を用いた多変数留数計算アルゴリズムと中国剰余定理 (数式処理における理論と応用の研究)
... y]/I_{i}$ を表現するベクトル空間を作ると , $U_{1}=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x^{5}, X, X, x, x, 1\}432,$ $U_{\mathit{2}}=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{X, 1\},$ ...
19
行列の特異値を求めるアルゴリズムに含まれた離散可積分系に対する中心多様体理論アプローチ(数値シミュレーションを支える応用数理)
... – An integrable system–in: Dynamical Systems. Theory and Applications, J. Moser ed., Lec. Notes in Phys., 38 Springer-Verlag, Berlin, 1975, PP. 467-497. . [12] 中村佳正, 可積分系の機能数理. 裳華房 (2006) [13] Rutishauser H., Lec ...
6
画像切り出しに対するアルゴリズムの提案 (アルゴリズムと計算機科学の数理的基盤とその応用)
... $O(N)$ 時間かかることが Chun ら $[3|$ により示され ている . この手法はまず , 格子点 $p$ を通るように水 平線と垂直線を引き , 階段凸領域を 4 つの部分領域 に分割する . その後 , それぞれの部分領域に対し , 動 的計画法を用いて最適領域を構成することで, 全体 ...
5
嘘を含む比較による最小値最大値発見アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
... $G$ の任意の a-b カットの容量が $m^{*}$ 以上であることを示せば十分である ...$i$ を $i^{+}\in S$ となる最小のものとする. 最小カットは容量 無限大の辺を用いることができないので , 任意の $j>i$ に対して $i^{-}\in S$ が成り立つ ...
9
数式処理から見た行列の数値計算アルゴリズム (数式処理における理論と応用の研究)
... 2 数値計算による実対称行列の三重対角化 2.1 Householder 法と Lanczos 法 この節では , Householder 法と Lanczos 法について特徴を簡単に述べる . 両手法とも反 復法ではなく , 誤差がなければ有限ステヅプで終了し , 使用する演算は四則と開平である . 開平はベクトルの長さを求めるところで必要で , 具体的には , ...
8
ネットワーク上のバックトラックアルゴリズム(計算理論とその応用)
... い部分木は独立に処理できる。 そこで、 いくつかの部分木をランダムにまとめグループとし、 グループごとに $\mathrm{C}\mathrm{P}\mathrm{U}$ を割り当てれば、 同時に多数の $\mathrm{C}\mathrm{P}\mathrm{U}$ を使って、 処理することが可能と なる。 ...
8
大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)
... 見積もれ，また， Sort ジョブを高速化できない限り， $Tref/$ Rename はあまり高速化できないと推定できる． [ 補足 2] 例えば，図 5 の Tref の Reduce の参照で， pos が 4 のペアは，別の Reduce タスクに存在する pos が 3 ...
4
特異値計算のmdLVsアルゴリズムと特異値分解のI-SVDアルゴリズムにおける最近の進展 (流体計算における高速アルゴリズムの理論とその応用)
... [221 Y. Nakamura, Functionality of Jntegrable Systems, Tokyo: Kyoritsu Shuppan, 2006, (中村佳正著 「可積分系の機能数理」 共立出版). [23] B. N. Parlett and I. S. Dhillon, Femando’s solution to Wilkinson’s problem: An application of ...
18
ホロノミックシステムの多項式解と有理解を求めるアルゴリズム (数式処理における理論と応用の研究)
... holonomic のとき多項式解を見つけるアルゴリズムを与えよ . 2. $I$ が , holonomic のとき有理解を見つけるアルゴリズムを与えよ ...pole の位置については $\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{o}- ...
10
線形計画問題に対する単体法の計算量と強多項式アルゴリズム (最適化アルゴリズムの進展 : 理論・応用・実装)
... $c_{K}’=0$ となって停止した場合には、 最適基底と最適解を求めることができる。 ステップ 2 で停止した場合には、 線形計画問題 (1) は実行不能であるか非有界であり、 最適解を 持たないことがわかる。 補助問題では目的関数の係数ベクトル $\overline{d}_{K}$ の各成分の絶対値が ...
10
ifplotアルゴリズム(数式処理における理論とその応用の研究)
... $\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$ の ifplot の precise モードにより提供されている。 28.3.3 区間演算アルゴリズム 1993 年 ...により提案されたアルゴリズムで図を正確に求めるよりも孤立特異点 ...
6
片方のみがタイを持つ安定結婚問題に対する25/17近似アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
... ルゴリズム、 整数計画問題、 線形計画緩和 これにタイのみを認めた問題では、 問題の定義より、 安定マッチングは完全マッチングとなるのでマッチ ングの大きさは一定であった。 また、 不完全なリス 1 はじめに トのみを認めた問題では、 安定マッチングは完全マッ ...
6
ファジイ平均を用いた最適化アルゴリズムとその流れ場のコントロールへの応用(計算流体力学に関わる数理的諸問題)
... dk の例を図 $5_{\text{、}}6$ に示す。 図 5 は探索ベクトルの方向が振動することを押さえるように働いている例である。 実線は $\mathrm{C}$ 法の探索 ベクトル、 破線は C-FA 法の探索ベクトルを示す。 図 6 は逆にファジィ平均操作が探索ベクトルの方向を乱し、 ...
12
EBP-EWLS 学習アルゴリズムの応用 : 正弦関数と文字認識
... 1.は じめ に 階層型ニ ュー ラルネ ッ トワーク (NN)に 対す る 教 師あ り学習 アル ゴ リズム と しては誤差逆伝搬法 (BP法 )[1]お よびその拡張である慣性項を用 いた B P tt12]を 始 め と して非常 に多 くの提案 [3]∼ [5] がな されている。 しか し、 BP法 には多 くの欠陥 が指摘 されてお り、その改良に多 くの[r] ...
10
文脈を考慮したJavaプログラムの参照先解析に関する一考察 (アルゴリズムと計算機科学の数理的基盤とその応用)
... ることに成功した. この計算量のオーダーは文脈非依存である Andersen-style の解析とも同じなので, 計 算量のオーダーを増加させずに文脈を考慮した結果が得られる手法と言える. 参考文献 [And94] Lars Ole Andersen. Program Analysis and ...
7
AKS 素数判定アルゴリズムについての計算機を用いた実験的考察 (計算機科学とアルゴリズムの数理的基礎とその応用)
... しかしながら，原論文の公表後十分な改良が施され たものについてみても，前世紀に開発され広く使わ れている APR 法や ECPP 法などの確定的素数判定 アルゴリズムと比べて実用的な範囲の入力に対する 計算時間が極めて長いことが判明している．本論文 ...
4