著者

田岡 智志 渡邊 敏正

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.549, pp.73-80, 2000-01-19

参考文献数

24

---

k辺連結化問題とは、与えられた無向グラフG=(V, E)に付加して得られるグラフG'=(V, E∪E')がk辺連結となるような最小辺集合E'を求める問題である。本稿では、"辺付加により新たに多重辺を作らない"、という条件を加えたk辺連結化問題を扱う。一般には、この問題はNP-hardであり、Gの葉と呼ばれる点集合の総数により問題の難しさが変わることが知られている。本稿では、Gの辺連結度をσとするとき、k=σ+1且つGが2σ+6個未満の葉を持つ場合を考え、リーフグラフの最大マッチングにより生成される葉数と不飽和葉数の関係により、多項式時間の最適解法、あるいは、近似比3 / 2の近似解法、それぞれを提案する。

著者

土肥 義康 山田 敏規 上野 修一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.549, pp.17-24, 2000-01-19

---

シャッフル交換ネットワークとde BruijnネットワークはFFTなどの並列計算に適した構造としてよく知られている.N点から成るシャッフル交換ネットワークとde Bruijnネットワークの2次元VLSIの面積と配線長は, それぞれΘ(N^2 / log^2N)とΘ(N / logN)であることが知られている.本論文では, N点から成るシャッフル交換ネットワークとde Bruijnネットワークが3次元VLSIにO(N^<3 / 2> / log^<1 / 4>N)の面積とO(N^<1 / 2> / log^<1 / 4>N)の配線長でレイアウトできることを示す.

著者

岩間 一雄 Lingas Andrzej 沖田 正樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.499, pp.49-55, 2005-12-15

参考文献数

17

---

木t-スパナーとは, グラフGの全域木でその伸長度がt以内(2つの頂点間の木上での距離がグラフ上での距離のt倍以内)であるものを言う. Gが木t-スパナーを持ち, 木t-1-スパナーを持たないとき, Gの伸長度がtであるという. 本稿ではグラフの伸長度を枝を追加して減少させる問題を議論する. 円グラフやグリッドグラフ等の特殊なグラフに対して最適な枝の追加アルゴリズムを与える. 一般のグラフに対しては問題は困難になるが, それでも, O(n/s')本の枝を追加して伸長度をs'にするアルゴリズムを与える.

著者

須田 克朗 守屋 宣 井上 美智子 増澤 利光 藤原 秀雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.98, no.562, pp.9-15, 1999-01-23

---

時間タイマを持つ分散システム上での線形化可能性を保証する共有レジスタの無待機な実現を考察する.すべてのプロセスに既知で, 0<u<dである定数d, uに対し, すべてのメッセージ遅延は[d-u, d]の範囲であることを仮定する.本稿では, read操作の最悪応答時間がd, write操作の最悪応答時間がuであるような線形化可能な実現を示す.さらに, この実現は無待機であること, すなわち, 任意個のプロセスの停止故障に耐性があることを示す.

著者

朝廣 雄一 宮野 英次 宮崎 修一 吉牟田 拓朗

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.106, no.405, pp.15-22, 2006-11-27

---

グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.本問題に対する最も単純な方法の一つは,最近傍アルゴリズム(NN)であり,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動する戦略である.重み付き最近傍アルゴリズム(WNN)は,NNの拡張であり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,重み3であるWNNが16競合であることが知られている.本稿ではサイクルグラフについては,NNの競合比が1.5となること,その解析が厳密であることを示す.また,サイクルグラフに対してはWNNの中でNNが最適であることを示す.さらに,本問題に対しては,1.25競合よりも良いアルゴリズムが存在しないことを示す.

著者

萩原 洋一 池田 論 中森 眞理雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.98, no.442, pp.57-64, 1998-12-04

被引用文献数

1 1

---

マージソートは時間計算量が0(n log n)(nはソートされるレコードの個数)であり高速であるが, 内部ソートとして実行する場合, 作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では, 作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量は0(n log^2 n)であり, 従来のアルゴリズムより悪いが, これは作業場所とのトレードオフの結果である.

著者

右田 雅裕 多田 昭雄 中村 良三

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.538, pp.9-16, 2003-12-15

---

本橋では,CREW-PRAM並列計算機モデルのもとで,DAG (Directed Acyclic Graph)の最長路を求める効率よい並列アルゴリズムを提案する.また,従来の推移的閉包行列の計算方法を用いない並列トポロジカル整列アルゴリズムを示し,これを用いて最長路を求める並列アルゴリズムである.具体的には,はじめにDAGのトポロジカル整列を行い節点のランクを求め,次にその逆向き線形リストに対して同様の方法でランクを求めて,これらのランクを用いてすべての最長路を求める並列アルゴリズムである.DAGにおいて節点数n,辺数mとすると,提案するアルゴリズムの計算量はCREW-PRAM並列計算機モデルでプロセッサ数がO(n+m),時間量がO(log^2m)である.

著者

高木 一義 高木 直史 矢島 脩三

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.93, no.81, pp.85-92, 1993-05-27

---

最小カット線形配置問題は、グラフの節点の線形配列のうち、枝の重なりの最大値が最小のものを求める問題である。木に対しては、この問題を解く多項式時間アルゴリズムが知られているが、一般のグラフに対してはNP-完全である。本稿では、完全p-q dagに対する最小カット線形配置問題のアルゴリズムを二つ提案する。p-q dagは、有向非巡回グラフの一つのクラスであり、ある種の繰り返し構造を持つ回路の結合網として用いられる。第一のアルゴリズムは、動的計画法に基づくものであり、グラフのサイズに対して多項式オーダの計算時間と計算領域を要する。第二のアルゴリズムは、線形配置の性質に基づく近似アルゴリズムである。最後に、これらのアルゴリズムの応用として、多オペランド加算器の組織的なVLSIレイアウト手法を示す。

著者

小野 顕光 中野 眞一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.53-57, 2005-05-13

---

半順序集合Pが与えられたときに、すべてのトポロジカルソートを生成する幾つかのアルゴリズムが知られている.既知のアルゴリズムで最も高速なものは、各トポロジカルソートを"平均"定数時間で生成する.本文は, 各トポロジカルソートを定数時間で生成するアルゴリズムを与える.既知のアルゴリズムは, 各トポロジカルソートを丁度2回づつ生成し, そのうちの一方のみを出力するのに対し, 我々のアルゴリズムは各トポロジカルソートを丁度1回づつ生成する.

著者

伊東 利哉 武井 由智 垂井 淳

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.194, pp.39-46, 1999-07-21

参考文献数

13

---

置換族がk点独立性を持つとは, 直観的には, そこから置換を一様ランダムに選んだとき任意の異なるk点が任意の異なるk点に等確率に写像されることである. 類似概念として, 任意の異なるk点の像のなす相対順序が等確率にあらわれるという性質が定義でき, これをk順位独立性と呼ぶことにする. また, 任意の異なる高々k点の像の中で全ての点が等確率で最小値となる性質がk制限最小値独立性として定義されている. 本論文では, 集合{0,1,...,n-1}に作用する置換族Cが上記各独立性を満足するときの要素数∥C∥の限界を考察し, 以下の結果一(1)下界: k制限最小値独立性は∥C∥≧n-1, k順位独立性は∥C∥≧(n/2)^<&lfloor;k/4&rfloor;> がそれぞれ必要(2)上界: k制限最小値独立置換族は∥C∥= o((en)^k), k順位独立置換族は∥C∥=0(n^<k2/(21nk)>)でそれぞれ構成可能を示す.

著者

但馬 康宏 富田 悦次 若月 光夫

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.97, no.356, pp.111-118, 1997-10-31

参考文献数

4

被引用文献数

1

---

単純決定性言語の多項式時間MAT学習に関する新たな結果を示す。一般に等価性質問は、仮説文法の入力に対して学習対象の言語との等価性を出力とし、さらに非等価の場合には、その根拠となる反例も出力となる。ここで、反例が正の反例の場合、さらに学習対象における導出構造を出力する質問を構造反例付き等価性質問と新たに定義する。このとき、任意の単純決定性言語は、単純決定性言語の族を用いて、所属性質問および構造反例付き等価性質問から多項式時間で厳密学習可能であることを示す。この学習アルゴリズムの基本的な考え方はAngluin (1987) によるアルゴリズムの拡張である。

著者

中村 朋健 上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.468, pp.31-37, 2003-11-18

---

近年,巨大なデータベースが世界中の至るところで作成され,そこから役立つ情報を抽出するデータマイニング技術が実用に供されるようになった.規則性の見え難いデータベースからデータベースの性質を見つけ出す場合に,類似したデータ要素を集めるクラスタリングは有効である.特に,大規模な高次元データベースからの知識抽出において,実時間性や即時応答性が要求される分野ではメモリ使用量が少なく高速なクラスタリングが要求される.本稿では,実社会データを想定した高次元かつ疎なデータ空間を対象に,処理時間とデータ要素数が線形関係であるクラスタリング手法を提案する.また,数次元の入力データに対して提案手法を適用し,与えた評価基準により提案手法を評価する.提案手法では入力のデータ空間を階層的に不均一なサイズのセルに区切り,パラメータにより密と判断された隣接したセルを結合させることで,類似したデータ要素を集めるアルゴリズムである.

著者

日吉 久礎

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.317, pp.65-72, 2004-09-10

---

多次元空間上に与えられたデータを補間する際,データ点に間するvoronoi図を利用する補間法を自然近傍補間という.自然近傍補間公式としてよく知られているSibsonの補間公式は,いくつかの円上で滑らかでないことが知られている.より高い連続性を持つ自然近傍補間公式の列が,Hiyoshi-Sugiharaによって提案されたが,補間を計算するアルゴリズムが明らかにされていなかった.本研究では,Hiyoshi-Sugiharaの補間公式の計算アルゴリズムを提案する.また,Hiyoshi-Sugiharaの補間公式列の極限が,データ点のDelaunay三角形分割をメッシュとする線形三角要素に一致することを示す.

著者

森田 圭介 中脇 博文 渡辺 敏正

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.95, no.13, pp.11-20, 1995-04-21

被引用文献数

4

---

ペトリネットの発火系列問題とは与えられた初期マーキングから順次発火できるトランジションの系列で,各トランジションが予め指定された回数だけ出現するものを見つける問題である。まず,ステートマシン(トランジションの入出力枝がそれぞれ1本以下のペトリネット)の発火系列問題に対して,計算時間,記憶容量共にO(|X|)に短縮した解法を提案する。ここで|X|は各トランジションの出現回数の総和である。次に,その拡張である枝重み付ステートマシンの発火系列問題に関して,技重みが2種類であるいくつかの部分族に対する線形時間解法についても述べる。

著者

金井 昭人

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.707, pp.25-32, 2002-03-04

参考文献数

12

---

プログラムの図式表示は,可視化プログラミングには不可欠である,木構造図一般を表現する中間言語としてDXL(a Diagram eXchanged Language for tree-structured chartds)が1995年にJISX O 130として制定されている.一方,最近では,属性グラフ文法をソフトウェア環境など,様々な分野に応用する研究が始められている.また,属性edNCEグラフ文法に基づいたDXL対応Hichartの定式化と構文解析については既に発表済みである.本論文では,属性edNCEグラフ文法に基づくHichartエディタについて述べる.

著者

稲永 俊介 船本 崇 竹田 正幸 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.622, pp.29-36, 2004-01-22

---

文字列の文法に基づく圧縮とは,与えられたテキストを生成する文法を構築することによってデータのサイズを縮小する圧縮法である.この中で長さ優先置換法とは,テキスト中の部分文字列のうち,重複なく複数回現れている最長のものを生成規則として別の一文字に置換していくものである.本論文では,文字列に対する索引構造の一つである接尾辞木に対して極めて技巧的な構造の更新を行うことにより,この長さ優先置換を線形時間で行うアルゴリズムを提案する.

著者

韓 永楷 定兼 邦彦 宋 永健

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.55, pp.1-7, 2004-05-13

---

文字列検索のためのデータ構造としては接尾辞本,接尾辞配列などが有名であるが,これらにはデータ構造の必要とする記他領域が大きいという欠点がある.近年GrossiとVitterによって提案された圧縮接尾辞配列は検索速度を落とすことなく接尾辞配列を圧縮したものであり,サイズは長さnの文字列に対してO(nlog|A|)ビット(Aはアルファベット)である.これは文字列のサイズの線形となっている.圧鎔接尾辞配列を構築するアルゴリズムとして,Honらの提案したO(nlog|A|)ビットの一時的な記他領域を使用するO(nloglogUI)時間アルゴリズムが存在する,これは領域に関しては最適だが時間に関しては最適ではない,本論文ではアルファベットサイズが小さいとき(log|A| = O((log log n)^<1-ε>))に0(n)時間で動くアルゴリズムを提案する.

著者

後藤 隆元 小野 廣隆 定兼 邦彦 山下 雅史

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.1-8, 2005-05-13

---

計算機の性能の向上や, インターネットの普及により, 我々が扱うデータの量は急速に増加している.そしてそれに伴い, 大きなデータの中から必要なデータを探し出す機会も多くなっている.しかし, 扱うデータの量が増えるにつれて検索に必要な時間計算量や空間計算量も増加するため, より効率の良い検索アルゴリズムが求められている.一般に, 文字列検索を行う際にはあらかじめ対象となるファイルに対して索引付けを行って検索しやすくしている.そこで, 本研究では複数のファイルを格納した文書データベースに対して, 圧縮接尾辞配列を用いた索引付けを行うことにより, 時間的にも空間的にも効率が良く, 検索漏れが生じない文字列検索アルゴリズムを提案する.

著者

成澤 和志 稲永 俊介 坂内 英夫 竹田 正幸

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.24, pp.63-70, 2007-04-19

被引用文献数

1

---

本論文では,Blumerらによって提案された同値関係による同値類を計算する問題を考える.Blumerらはコンパクト有向無閉路文字列グラフ(CDAWG)と呼ばれる索引構造を定義するために同値類を利用した.同値類は本質的に等しく出現する冗長な部分文字列を集めた集合であるため,テキスト解析において有用である.本論文では,接尾辞配列を用いて同値類を計算するアルゴリズムを提案する.提案アルゴリズムでは,接尾辞木および接尾辞リンク木の巡回を模倣するため接尾辞配列の他に2つの補助配列を使用するが,これら以外のデータ構造を必要としない.このアルゴリズムは入力文字列に対して,線形時間および線形領域で動作する.本論文では,提案アルゴリズムと接尾辞木およびコンパクト有向無閉路文字列を用いたアルゴリズムとの計算時間・計算領域を計算機実験によって比較する.

著者

田口 敬教 都倉 信樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.24, pp.9-16, 2007-04-19

---

商品コードのEANコードは,白と黒のバーで表されるバーコードの代表的なものとして使われており,バーコードスキャナなどで読み込む.汚れなどの外的要因やスキャンしたデータのディジタルデータへの変換過程での誤りなどの要因により,本来EANコードの表しているデータと異なるデータを読み込んだ場合,それがEANコードの形式に反するなら誤りと判断でき,再読込をする.しかし,形式的には正しいとして誤ったデータを受け取ることもある.これを誤りを見逃し,あるいは誤読といい,その確率を前回報告した.本報告ではEANコードの誤読率をもとに,実際に汚れがバーコードシンボルに付着した場合の誤読率を報告する.