CS61B 课程笔记（Lecture 39 Reductions, Algorithmic Bounds, NP Completeness)

1. 压缩与复杂性

压缩的基本概念：压缩是通过减少数据的冗余来缩短数据所占用的存储空间。其目标是将原始数据（如文本、图像等）转换为较小的表示形式，通常需要解压缩算法将其还原。
信息量：信息量的计算依赖于数据中可能存在的状态。例如，《白鲸》的文本可以被视为一个序列，压缩算法试图找到生成这个序列的最小比特数。
实例：使用不同的压缩算法对《白鲸》的文本进行比较，如LZ77、Huffman编码等，能够看出压缩效果差异。例如，bzip2算法通常能提供更好的压缩率。

2. 解压算法

解压算法的定义：给定一个比特序列 $ B $，寻找一个较短的序列 $ DA + C(B) $，使得输入到解释器中能够生成 $ B $。其中，$ DA $ 是解压算法的比特表示，$ C(B) $ 是压缩后的比特流。

例如，假设有以下解压算法：

public class Decompressor {
    public static String decompress(int input) {
        if (input == 0) {
            return "Call me Ishmael.";
        } else {
            return "Original text as is.";
        }
    }
}

在这个例子中，input参数决定了生成的文本。

3. 改进压缩

压缩效果的改善：通过改进算法，可以在相同数据量下实现更好的压缩效果。例如，使用Huffman编码算法对文本进行编码，能够减少其存储需求。

MysteryX算法：假设MysteryX是一种生成图像的算法，通过生成图像的Java代码，可以将图像文件压缩到一个较小的比特数。

示例代码：

public class MysteryX {
    public static void main(String[] args) {
        // 模拟图像生成
        generateImage();
    }

    public static void generateImage() {
        System.out.println("生成图像的逻辑");
        // 生成图像的具体实现
    }
}

4. 最优压缩与柯尔莫哥洛夫复杂性

柯尔莫哥洛夫复杂性：柯尔莫哥洛夫复杂性 $ K(B) $ 是生成比特流 $ B $ 的最短程序长度。它是衡量数据复杂性的一种方法。

例如，若存在程序 $ P $，能够生成比特流 $ B $，则其复杂性可以表示为：$K(B) |P|$
语言无关性：柯尔莫哥洛夫复杂性是语言无关的，因此任何编程语言都可以用来生成同样的比特流。

5. 不可计算性

不可计算性：证明柯尔莫哥洛夫复杂性不可计算意味着没有通用算法能够找出所有程序生成特定比特流的最短长度。例如，没有方法可以确定是否存在程序能够生成某个比特流。

6. 空间/时间有界压缩

空间有界压缩：给定比特流 $ B $ 和目标大小 $ S $，寻找不超过 $ S $ 的程序生成 $ B $。这是一个不可计算的问题。

示例代码：

public class BoundedCompression {
    public static void compress(String bitStream, int maxLength) {
        // 伪代码：遍历所有可能的程序
        for (int length = 1; length <= maxLength; length++) {
            for (String program : generatePrograms(length)) {
                if (generateBitStream(program).equals(bitStream)) {
                    System.out.println("找到程序: " + program);
                    return;
                }
            }
        }
        System.out.println("没有找到程序");
    }
    
    private static String[] generatePrograms(int length) {
        // 生成特定长度的所有程序（伪代码）
        return new String[]{"program1", "program2"};
    }
    
    private static String generateBitStream(String program) {
        // 执行程序并返回生成的比特流（伪代码）
        return "outputBitStream";
    }
}

7. 空间-时间有界压缩

空间-时间有界压缩：在有限的时间 $ T $ 内执行的程序，并且每个程序的空间限制在 $ S $ 之内。

示例伪代码：

public class TimeBoundedCompression {
    public static void compress(String targetBitStream, int maxLength, int maxTime) {
        for (int length = 1; length <= maxLength; length++) {
            for (String program : generatePrograms(length)) {
                int linesExecuted = 0;
                while (linesExecuted < maxTime) {
                    // 运行程序并检查输出
                    if (generateBitStream(program).equals(targetBitStream)) {
                        System.out.println("找到程序: " + program);
                        return;
                    }
                    linesExecuted++;
                }
            }
        }
        System.out.println("没有找到程序");
    }
}