実数列の大域的丸めの数え上げ

• Item type: SIG Technical Reports(1)
• 公開日: 2001-03-12
• タイトル: 実数列の大域的丸めの数え上げ
• タイトル / 言語: en
• タイトル: Enumerating all low - discrepancy roudings of a real sequence
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学大学院情報科学研究科システム情報科学専攻
• 著者所属: 東北大学大学院情報科学研究科システム情報科学専攻
• 著者所属: 東北大学大学院情報科学研究科システム情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences, Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of System Information Sciences Graduate School of Information Sciences, Tohoku University
• 著者名: ChebihiNadiaTakki; 定兼, 邦彦; 徳山, 豪
• 著者名(英): Nadia, TakkiChebihi; Kunihiko, Sadakane; Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 長さnの実数列に対し，[1 n]の部分区間からなる区間族に対して，丸め誤差の区間和がどの区間に関しても1以下になるものを大域的丸めと呼ぶ．どのような区間族に対しても，大域的丸めが存在することは知られているが，特に，[1 n]の全ての区間からなる区間族に関しては，大域的丸めはn+1個しかなく，O(n^2)時間で列挙が出来ること，また，全ての長さk以下の区間族に関しては，大域的丸めを一様ランダムに生成するシステム（ネットワーク）をO(kn)時間で生成できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we discuss the problem of computing all the integral sequences obtained by rounding an input real valued sequence such that the discrepancy between the input sequence and each output integral sequence is less than one. We show that the number of such roundings is n+1 if we consider the discrepancy with respect to the set of all subintervals, and give an efficient algorithm to report all of them. Then, we give an optimal method to construct a compact graph to represent the set of global roundings satisfying a weaker discrepancy condition.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 25(2000-AL-077), p. 57-64, 発行日 2001-03-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会