計算機で生成するランダム性を持つ数列
弱いランダム仮定の元での公開鍵暗号の強秘匿性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... random である. 数列生成オラクル巧 c 上の EIGamal 暗号は 2 個の平文に対して indistinguishability あるい は super-indistinguishability を持つことは容易に示す ことができ , 結局, 2 個の平文に対して ...
6
コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
... 次は本稿の鍵となる命題で , Rose, Tarjan, Lueker [21] の結果から導かれる . 命題 21 与えられたコーダルグラフの対 $\overline{G}=(V,\overline{E})$ と $\underline{G}=(V,\underline{E})$ は $\underline{G}\subset\overline{G}$ を満たすとし, また ...
6
数学と計算機科学の相互作用：計算代数とHaskellにおける安全性と拡張性
... 審 査 の 要 旨 〔批評〕 純粋関数型言語では、プログラムの合成可能性や一貫性が向上する利点がある一方、現実のソフトウェ アの開発においては、副作用を伴う処理も必要不可欠である。その際、副作用を伴う処理が重なることも ...
4
矩形領域を生成する可変ブロックパターン要素の組み合わせマッチングによる行列認識手法 (数学解析の理論的展開の計算機上での遂行可能性)
... 野や教育においても例外ではなく、 数式処理システムや学術情報データベースに接続した電子ボードなど、 数学の授業や講義に新しいスタイルをもたらすと考えられている。 このようにして、 数式をコンピ $=\mathrm{L}^{-}$ タ上 で取り扱うことの必要性が重要視され、 研究が進んでいる。 しかしながら、 数学に欠かせない “行列” につ ...
5
分割表の列挙とランダム生成 (グレブナ-基底の理論的有効性と実践的有効性)
... 輸送問題の制約式の係数行列は totally unimodular 行列なので , 輸送問題多面体の頂点 は整数格子点である . また, 周辺和 $a:,$ $b_{j}$ の 2 元分割表 $(x_{ij})$ と , 供給量 $a$ : と需要量 $b_{j}$ の 輸送問題の実行可能 (整数) 解 $x_{ij}$ が一対一対応しているので , 周辺和を固定した 2 元分割 表の counting は, ...
16
動的グラフ上のランダムウォークの到達時間と全訪問時間 (理論計算機科学の新展開)
... グラフ $G$ の次数が大きくなるほど，ベルヌーイグ ラフ上のメトロポリスウォークの到達時間，全訪問 時間は，変化のないグラフ $G$ 上でのメ トロポリス ウォークの到達時間，全訪問時間に近づく． 補題 3.4 ある遷移確率行列 $P=(P(u, v))(u, v\in V)$ が与えられるとする．このとき，グラフ上の各頂点 ...
5
フロンティア法から生成されるZDDの幅解析 (理論計算機科学の新展開)
... たフロンティア法が提唱された [7]. しかし，このア ルゴリズムは一般の入カグラフについては頂点数， 辺数といったサイズに対して指数時間かかることが 実験的に確かめられていた．本研究では列挙対象を サイクル，s-t パスとし，入カグラフについては完 全グラフ，平面グラフ，グリッドグラフの 3 つを対 象に， ZDD 構築に必要な時間，領域計算量につい ...
6
反復型アルゴリズムによるフィボナッチ列の生成について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... 証明 . $n$ に関する帰納法で証明する. 明らかに $n=2$ について定理は成立する . $n\leqq m$ について定理は成 立すると仮定し, $n=m+1$ について考える. 帰納法 の仮定より , 各部分リストの内部では定理は成立する . したがって, 部分リストの境界について定理を示せば ...
6
0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生
... 式(3.101)において絶対値記号を用いているが,変動幅 は が正から負に変 わる境界においても微分可能であるゆえ における面の連続性は保たれる．この式を用 いて新たな を求めるときに，係数 a は固定し係数 b のみを変化させる．なお，画像に は投影される物体の に対応して明るさ E が構成されているが，ある反復段階での ...
6
決定性プッシュダウンオートマトンを模倣する拡張単純回帰ネットワークの構成法 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... 表 1: 水平 - 垂直順の場合の水平線の状態と垂直線 の状態の可能な組み合わせ 定義 23ARH $k\mathrm{V}lM$ の状態遷移関数 \mbox{\boldmath $\delta$} $\subseteq((Q\cross$ $\{0,1\}^{k_{\cross}}\{\mathrm{o}, 1\}\iota)\cross((\Sigma\cup ...
7
ランダムに生成された和積形論理式が充足不能となるしきい値について (アルゴリズムと計算の理論)
... 1-path $p$ に対して 1 のラベルを持つ節点までの変数節点の個数を $P$ の長さと定義し $lc7?,(P)$ と書く, 以下では 1-path $P$ の表現として $\overline{x_{i_{1}}.}\cdot\overline{x_{\ovalbox{\tt\small REJECT} i_{1}}}\cdot\cdot\text{・}$ ...
7
任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
... 九州大学大学院システム情報科学府 \dagger 九州大学大学院システム情報科学研究院 概要 グラフ上のランダムウォークは, 粒子がグラフの 頂点をある遷移確率に従ってランダムに遷移してい くモデルである。 $n$ 個の頂点からなる木上のランダム ...
5
木ネットワークでヒープ順序を実現する自己安定プロトコル (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... 公開鍵暗号方式の多くは, 有限体上の乗法群における素因数分解および離散対数問題の計算困難性に基づいている . 素因数分解と離散対数問題ともに効率的なアルゴリズムを用 $\mathrm{A}\mathrm{a}$ , さまざまなプロジエクトで数値実験が行われ成果を 挙げている . 離散対数問題は位数が大きくなると計算量が多くなり, ...
6
無理数の遷移確率を許すランダムウォークの脱乱択化 (理論計算機科学の新展開)
... $i= \sum_{j=.0}^{\lfloor 1gi.」}.\beta_{j}(i)\cdot 2^{j}$ はと表 i のす二進但 $| \frac{|\mathcal{I}_{v,u}[0,z)|}{z}-P\zeta v,$ $u)|> \frac{1}{3z}lg(\frac{3}{4}z+1)=\Omega(\frac{\log z}{z})$ 数表記 $\beta_{\lfloor ...
4
ランダムタイリングの数値シミュレーション (数学解析の理論的展開の計算機による支援・遂行可能性)
... 図 6: $\mathcal{G}$ の全域木と $\mathcal{H}(\mathcal{G})$ の完全マッチング 3 数値シミュレーション 高速にグラフの全域木全体から uniform sampling を行う Wilson[3] のアルゴリ ズムがあり、 この対応を用いて、 上述のグラフの完全マッチング、 つまりある領域 ...
8
部分IDの一意性を考慮したID集合生成に関する問題 (計算機科学基礎理論とその応用)
... の長さを $m$ , サービス受領者数を $u$ , 同時に受けられ るサービスの数の最大値を $p$ とおくと , ランダムに $\mathrm{I}\mathrm{D}$ を作成したときそれが本物の JD と一致する確率 は, 提案アルゴリズムを用いた場合は $u/\underline{\eta}\cdot m$ ...
5
ランダムの程度の助言付き計算 (理論計算機科学の新展開)
... 一方，筆者は Nies の講演を聞き，積分テストとの類似性が気にかかった．関数 $t:2^{\omega}arrow\overline{\mathbb{R}}^{+}$ が積分テストであるとは，積分可能な下側半計算可能関数であることを言う．実数 $x\in[0,1]$ が Martin-L\"of ...
7
安定結婚問題の近似可能性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... ラルを持ち , さらに各変数の出現回数は高々 $t$ 回であ る. もし $\mathrm{P}\neq \mathrm{N}\mathrm{P}$ ならば , MAX $\mathrm{E}3\mathrm{S}\mathrm{A}\mathrm{T}(t)$ は , ある正 の定数 $\alpha$ と整数 $t$ に対して $1+\alpha$ では近似できない ということが知られている $[1, ...
6
一般化詰め将棋のPSPACE困難性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... 問題 QBF 入力 自由変数を持たない量限定フ : $-’\mathrm{s}$ 式 $\phi$ $=$ $Q_{1}x_{1}Q_{22}X\cdots Q_{n}x_{n}\psi$ 。ここで、 $Q_{i}=\forall$ または $\exists(i=$ $0,1,$ $\ldots,$ $n)_{\text{、}}\psi= \bigwedge_{J}^{m}=1c_{J^{\backslash ...
6
分散システムでの剛性グラフに対する局所交換可能性 (理論計算機科学の新展開)
... $=(V,\hat{E}_{i})$ を得る．その向き付けを保持した まま， $v$ からの有向パスをもつ頂点を探索し， $L_{n}\backslash$ 現 の無い辺 $f$ を見つけると， $L_{i}+e$ $f$ はラーマング ラフである．分散アルゴリズムにつ - いては ...
3