C[[x]] の割り算定理とその近似アルゴリズム
二変数有理関数近似のハイブリッド計算と多変数近似GCDアルゴリズム (数式処理における理論と応用の研究)
... +29831 $\cross 10^{-6}y^{3}+3.2702y^{2}-0.56574y+0.57500$ . ここで、 数式処理システム $\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$ 上で計算を行い、倍精度浮動小数計算を用い、 各デー タに与えた微小な乱数値として ...
10
ユークリッド平面上の積空比定数のエネルギー最小化車両経路問題の近似アルゴリズムについて (アルゴリズムと計算機科学の数理的基盤とその応用)
... 断りがない限り, この特別な場合の EMVRP を単に $f$ “EMVRP” と表記する ). そして, Arora, Ka akostas の WMLP に対する近似アルゴリズムに車両重量対 $\vee$ 応の修正を加えることを考える . $\ovalbox{\tt\small REJECT}$ . ...
7
完全グラフ上の最大辺素パス問題に対する貪欲近似アルゴリズム (最適化の数理とアルゴリズム)
... $\rho$ 近似アルゴリズム ( $\mu \mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ algorithm) であるとは, ...
12
MAX DICUT問題の近似解法 (計算理論とアルゴリズムの新展開)
... $E= \sum_{i,j}w_{i,j^{\frac{\arccos(\overline{v}_{i}\cdot\overline{v}_{j})+\arccos(v_{0}\cdot\overline{v}_{j})-\arccos(v_{0}\cdot\overline{v}_{i})}{2\pi}}}$ . ここで , ...
5
量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用)
... とき , データ列中の 1 の数を求める問題について考察 する. この問題に対して通常の数え上げをそのまま 適用できないため , majority voting により誤りを高 確率で吸収することで , 量子数え上げを文字列出現 頻度問い合わせで適用できるようにした . また , 周期 的なパターンが与えられたとき, 配列の総和計算を ...
7
不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
... あるいは $\kappa(n)\leq\epsilon$ が成立していて, プレイヤーが悲 または $\kappa(n)\leq\epsilon$ が成立していて , プレイヤーが悲観 観的な仮説関数を用いて遷移を決定するものとする . 的な仮説関数を用いて遷移を決定するものとする. こ このとき , $\epsilon$ -ナッシュ均衡状態では, いずれのプレイ のとき , ...
7
ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)
... たアルゴリズム Best Pair Merge wiht Reconstnuction を提案し , 実験結果の比較と定理の証明を行った. 今後の課題としては, 本稿で提案したアルゴリズム の改良が挙げられる . また, 新たなアルゴリズムを考 ...
5
最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)
... において , $N_{s}\neq\emptyset$ である場合に以下の処理により全 体から独立してスケジュールできる頂点を求める方 法である, Zigzag 法は次のように定義される . $L_{\mathrm{O}}:=\emptyset,$ $L_{0}’:=N_{s},$ $q:=0$ ...
5
片方のみがタイを持つ安定結婚問題に対する25/17近似アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
... と $w$ がブロッキングペアであると言うのは、 以下の 三条件が全て成立したときである :(i) $M(m)\neq w$ だ が $rr\prime_{\ovalbox{\tt\small REJECT}}$ と $\prime 1t$ ’ は’/. いに受け入れ可能、 (ii) $\{v\succ_{m}M(\cdot;r\iota)$ もしくは $m$ が ...
6
3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
... 本稿では関数 e-score が if-penalty $=0$ , ratio- $type=1$ のときの近似比を求める. 以後 , 単に BPMF と呼ぷときは $e$ score が if-penalty $=0$ . ratio-type $=1$ である BPMF とする . まずアル ゴリズムや $e_{-}\epsilon\omega re$ ...
7
アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
... もっとも基本的なオプションであるヨーロピアンオプションは , 満期と呼ばれる将来の決めら れた時点において , 行使価格と呼ばれる価格で原資産を買う権利のことである . 行使価格が $X$ の とき , 満期における資産価格 $S_{n}$ が $X$ より大きい場合には, オプションを行使して資産を価格 $X$ で購入し, 直ちに市場価格 $S_{n}$ ...
8
不動点近似法による最適化アルゴリズム (決定理論と最適化アルゴリズム)
... $\lim_{narrow\infty}\alpha_{n}=0$ , $\sum_{n=1}^{\infty}\alpha_{n}=\infty$ , $\lim_{narrow\infty}r_{n}=\infty$ を満たすとする . このとき $A^{-1}0\neq\phi$ ならば, $\{x_{n}\}$ は $Px\in A^{-1}0$ に強収束する . ただし , $P$ は $H$ から ...
15
DAG の高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(計算機科学の理論とその応用)
... にスケジュールするとき, $v$ の上界は $l\alpha v+$ $\lfloor 0.4e(u_{j})\rfloor+j$ となる . また , $j\leq l$ であるので, $l\alpha v+\lfloor 0.4e(u_{j})\rfloor+j\leq$ $l \sigma w+\frac{2}{3}(low-\lfloor\alpha low\rfloor)+l-1\leq ...
7
近似GCDアルゴリズムにおける枢軸選択の影響 (数式処理とその周辺分野の研究)
... $R_{22}^{(k-1)}$ と $R_{22}^{(k)}$ の大きさについて調べ，その比が $arrow\Vert R^{(k1}\overline{b}||R_{22}k\Gamma_{1}^{\frac{)\Vert_{2}}{1_{2}}}<10\epsilon$ を満たす場合に，近似 GCD の候補とし て， ...GCD ...
12
二次元ハムサンドイッチ定理の一般化とその周辺 (新しいパラダイムとしてのアルゴリズム工学)
... $\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}(\iota)$ の中心、 $a,$ $b,$ $c$ を分割の足と呼ぶ。 \angle aob\leq \mbox{\boldmath $\pi$} かつ $\angle boc\leq\pi$ かつ \angle coa\leq ...
10
実関数の帰納推論(II) : 近似推論 (アルゴリズムと計算の理論)
... ( 廣渡栄寿 ) 1Department of Computer Science, University of Maryland, USA. : {kalvis, $\mathrm{s}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{h}$ } ...
6
特異値計算アルゴリズムdqds法の収束定理 (計算科学の基盤技術としての高速アルゴリズムとその周辺)
... 上 2 重対角行列の特異値計算アルゴリズムとしては, 近年, dqds (differential quotient difference with shifts) 法が特に注目されている [6]. 従来よく用いられてきた QR 法に基 づく方法 [5] に比べて数値的安定性に優れており , 適切な原点シフトにより十分な収束 速度を達成できるため, 現在 LAPACK にも DLASQ ...
14
ファジィ関係代数とその表現定理について(アルゴリズムと計算量理論)
... 係では表現し難く, これを表現可能にするために考えられたものがファジィ関係である . $\cdot\supset$ まりファジィ関係は通常の関係の拡張として論じることができる $[11,12]$ . 方 , 通常の関係において , 個々の変数間の関係の振舞いを用いることなく関係を代数的 に取り扱う関係計算なるものがある . ...
8
割り算アルゴリズムとBuchberger アルゴリズムのためのインタラクティブユーザインターフェース作成について (Computer Algebra : Design of Algorithms, Implementations and Applications)
... 今のステップで簡約を行うことができる多項式を表している。 次に操作方法であるが、ボールをクリックしてやれば、その多項式で簡約できる場合は簡約を行う。左の next button を押せば、今設定されている戦略 ( たとえば、 sugar の大小や単項式順序の大小 ) にしたがっ て、 自動的に多項式を選択して簡約を進める。 start button を押せば、 ...
3
離散ラプラス作用素の反復力学系 : 不動点定理と周期性定理 (アルゴリズムと計算機科学の数理的基盤とその応用)
... periodic functions. For an integer $M$ , which is called the size, we consider the following periodic functions: $F(M)=\{f\in F|f(x+mM,y+nM)=f(x,y),(n,m\in Z)\}$ Choosing a neighborhood we define the ...
7