A-35 論理回路の最大遅延分布の下限を与える正規分布(最適化,A.アルゴリズム・基礎)
スポンサーリンク
概要
- 論文の詳細を見る
正規分布に従う互いに独立な確率変数で与えられる枝重みを持つDAG(有向非巡回グラフ)を考える.このとき,グラフの入り口から出口までの最長路の長さは必ずしも正規分布に従うわけではない.本稿では,定数αより大きい範囲で最長路の長さが高々xである確率F(x)の下限を与える正規分布関数F^^~(x)を計算する方法を提案する.
- FIT(電子情報通信学会・情報処理学会)推進委員会の論文
- 2002-09-13
著者
-
山下 雅史
九州大学大学院システム情報科学研究院
-
安藤 映
Department of Computer Science and Communication Engineering, Kyushu University
-
松永 裕介
九州大学大学院システム情報科学研究院
-
安藤 映
Department Of Computer Science And Communication Engineering Kyushu University
-
安藤 映
九州大学大学院システム情報科学府
-
中田 寿夫
福岡教育大学教育学部
-
山下 雅史
九州大学大学院システム情報学府
-
中田 寿夫
福岡教育大学数学教育講座
関連論文
- 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)
- Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)
- 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)
- DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths
- RA-003 A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 部分一括描画装置の処理能力向上のための描画面積最適化(計算機システム化技術,システムLSI設計とその技術)
- DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting
- マルチプレクサの削減を目的としたバインディング改善手法(合成及び演算器最適化,システム設計及び一般)
- マルチプレクサの削減を目的としたバインディング改善手法(システム設計及び一般)
- DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(システム設計及び一般)
- DAGカバリング問題の下限とそれを用いた厳密アルゴリズムについて(検証/最適化,システム設計及び一般)
- FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法(FPGA実装設計,FPGA応用及び一般)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 順序回路のタイミング例外パス検出のための実用的方法(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 信号線間の含意関係に着目したフォールスパス検出手法(VLSIの設計/検証/テスト及び一般論理合成及び高位合成)
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- 目的関数調整法を用いたスケジューリング問題の一解法(アルゴリズム理論)
- ラグランジュ目的緩和法を用いた組合せ最適化問題の解法(数理モデル一般)
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- 高信頼性XCASTプロトコルの設計(e-Japan時代のインターネット/分散システムの構築運用技術)
- [チュートリアル講演]局所情報を用いる有限グラフ上の乱歩のヒッティング時間とカバー時間
- 無線通信プロトコルの理論的研究の現状(オピニオン)
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- トーラス型ネットワーク上の効率的なブロードキャスト方式について
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- 匿名ネットワーク上のリーダー選出問題の空間計算量 (計算機科学基礎理論の新展開)
- A-35 論理回路の最大遅延分布の下限を与える正規分布(最適化,A.アルゴリズム・基礎)
- データの論理的解析における正関数発見の並列化 (計算機科学基礎理論の新展開)
- ハウ・ツー・ランデブー
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- k-集合合意問題を解く故障検知器
- 移動物体回収問題
- 動的近傍操作を用いたDNA塩基配列設計
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 故障数制限付きリーダー選挙問題に対する故障検知器
- DNA形態変化におけるエネルギー障壁値の高速近似計算 (計算機科学基礎理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- Minimum Universal Evaluation Tree for Boolean Circuits (Evolutionary Advancement in Fundamental Theories of Computer Science)
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用)
- 量子回路における定数段加算器の設計(計算理論)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- マッチングを用いたパターン形成アルゴリズム
- 2010年度冬のシンポジウム 大規模分散フレームワークHadoopを用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用--RIMS研究集会報告集)
- 2010年度冬のシンポジウム ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用--RIMS研究集会報告集)
- IEICEフェロー記念講演
- 局所情報を用いたランダムウォークの拡張
- ストリーム中の頻出アイテム発見に対するO(loglogN) 領域乱択アルゴリズム
- ワイヤレスネットワークにおけるエネルギー効率の良いオンラインブロードキャスト
- ワイヤレスネットワークにおけるエネルギー効率の良いオンラインブロードキャスト
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 分子構造変化のモデル化と反応速度の理論的解析 (計算機科学基礎理論とその応用)
- 進化的ネットワークにおける探索アルゴリズムの提案 (計算機科学基礎理論とその応用)
- 局所情報を用いたランダムウォークの拡張
- 最小重み負荷分散枝被覆について
- 1-D-3 グラフ上のランダムウォークとその高速化(特別セッション 若手によるOR横断研究)
- Pattern Formation by Fully Asynchronous Mobile Robots (New Trends in Algorithms and Theory of Computation)
- ストリーム中の頻出アイテム発見に対するO(loglog$N$)領域乱択アルゴリズム (アルゴリズムと計算理論の新展開)
- ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)
- Probabilistic Stabilization under Probabilistic Schedulers (New Trends in Algorithms and Theory of Computation)
- DS-1-16 完全非同期ロボットによるパターン形成(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 ストリーム中の頻出アイテム発見に対するO(loglogN)領域乱択アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 無理数遷移確率ランダムウォークの脱乱択化
- 一般のネットワーク上の移動ビザンチン合意問題について
- 複数ストリーム間の特徴比較に対する乱択アルゴリズム (理論計算機科学の新展開)
- 動的グラフ上のランダムウォークの到達時間と全訪問時間 (理論計算機科学の新展開)
- 無理数の遷移確率を許すランダムウォークの脱乱択化 (理論計算機科学の新展開)
- 分散システムでの剛性グラフに対する局所交換可能性 (理論計算機科学の新展開)
- 森および連結全域部分グラフの乱択近似数え上げ (理論計算機科学の新展開)
- RA-002 文字列圧縮を用いたネットワークセキュリティにおけるインシデント検出(アルゴリズムと応用(2),A分野:モデル・アルゴリズム・プログラミング)
- ストリームに対するO(loglogn)領域を用いたReservoir sampling(一般)
- 関数ルーターモデルによるハイパーキューブ上ランダムウォークの脱乱択化(一般)