Research on explicit construction of worst imputs for algorithms

算法最坏输入的显式构造研究

• 批准号: 13680426
• 负责人: KOBAYASHI Kojiro
• 金额: $ 0.96万
• 依托单位: Soka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680426/
• 关键词: worst input; worst computation time; heapsort; Burrows-Wheeler transform; block sorting; アルゴリズムの効率; ソーティング; 事前整列性測度; ブロックソーティング; 逆転; 情報圧縮; 整列性測度; 連

1. Explicit construction of worst inputs for HeapsortWe explicitly constructed a class of worst inputs for Heapsort by the following steps : (1)the explicit construction of some of the worst inputs for phase 2, (2)the analysis of the transformation realized by phase 1, (3)the explicit construction of some of the worst inputs for phase 1, (4)the proof that there exist worst inputs for phase 1 constructed in (3)that are transformed into worst inputs for phase 2 constructed in (1)by the transforamtion of phase 1.2. Analysis of the structures in the inputs to block sortingBlock sorting is a part of the Burrows-Wheeler transformation that is used in several recent data compression algorithms. An input to block sorting is the sequence of sequences that are circular shifts of the sequence to be compressed. Such sequences have some structures in themselves and it is possible to design a fast sorting algorithm that utilized these structures. We analyzed the numbers of inversions and the runs in the inputs to block sorting for compressing randomly generated sequences.

1.显式构造堆排序的最差输入我们通过以下步骤显式构造了一类堆排序的最差输入：（1）阶段2的一些最差输入的显式构造，（2）阶段1实现的变换的分析，（3）阶段1的一些最差输入的显式构造，（4）证明了存在（3）中构造的阶段1的最坏输入，通过阶段1.2的变换，这些最坏输入被变换为（1）中构造的阶段2的最坏输入。块排序的输入结构分析块排序是Burrows-Wheeler变换的一部分，用于最近的几种数据压缩算法。块排序的输入是作为要压缩的序列的循环移位的序列的序列。这样的序列本身具有一些结构，并且可以设计利用这些结构的快速排序算法。我们分析了块排序压缩随机生成序列的输入中的反转数和游程数。

项目成果

Kojiro Kobayashi: "On time optimal solutions of the firing squad synchronization problem for two-dimensional oaths"Theoretical Computer Science. vol.259. 129-143 (2001)

小林小次郎：《二维誓言行刑队同步问题的准时最优解》理论计算机科学。

辻誠一, 小林孝次郎: "因数分解問題を表す論理式の変数数について"FIT(情報科学技術フォーラム)2003講演論文集. 133-134 (2003)

Seiichi Tsuji、Kojiro Kobayashi：“论表达因式分解问题的逻辑公式中的变量数量”FIT（信息科学与技术论坛）2003 年讲座论文集 133-134（2003 年）。

中山伸一, 小林孝次郎: "ブロックソートへの入力における逆転の数について"FIT(情報科学技術フォーラム)2003講演論文集. 139-140 (2003)

Shinichi Nakayama、Kojiro Kobayashi：“关于块排序输入中的反转次数”FIT（信息科学与技术论坛）2003 年论文集 139-140（2003）。

Kojiro Kobayashi: "On time optimal solutions of the firing squad synchronization problem for two-dimensional paths"Theoretical Computer Science. 259. 129-143 (2001)

小林小次郎：“二维路径行刑队同步问题的时间最优解”理论计算机科学。

稲垣敏夫, 中根茂雄, 小林孝次郎: "ほぼ整列済みの入力の事前整列性測度について"2003年夏のLAシンポジウム予講集. 18-1-18-22 (2003)

Toshio Inagaki、Shigeo Nakane、Kojiro Kobayashi：“关于几乎对齐投入的预调整措施”2003 年夏季洛杉矶研讨会初步讲座 18-1-18-22 (2003)。