知识卡片

普通读书笔记卡 · 3588.b · 生成模型:未记录

随机算法需明确随机性与保证

理解等级:中级

随机算法在运行中使用随机选择,同一输入可能产生不同运行时间或结果。设计时应区分结果是否总正确、错误概率或期望成本,并明确随机数来源和生成开销;伪随机序列的性质与可复现性也应符合用途。

286列出结果准确性、实例处理方式、顺序执行和确定性四项假设;放宽任一项都需重新定义成本及正确性要求。

290强调随机数生成和伪随机序列;是否需要不可预测性、统计独立性或可复现实验应由用途决定。

293指出重复实验可降低错误率,但需要给出单次错误模型、独立性和组合规则,不能对任意相关实验直接套乘法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      概率算法是确定性算法一个很有趣的替代方案。同样的输入同样的算法,运行两次的结果可能是不一样的,有时候我们会容忍错误的发生,也会接受算法最终告知问题无法解决。 一个重要假设是,算法可以利用随机位序列。其实随机性很难定义,虽然我们已经有几个用于检测随机性的测试,不过实际上很难生成满足这些测试的比特串。

    • · 查看原书依据

      四大设定的算法。 ·结果必须是正确的。 ·每次只解决一个实例。 ·顺序的。 ·确定性的。 抛开这些设定使我们能够创造出各种各样不同类型的算法。

    • · 查看原书依据

      伪随机序列,来替代真正的随机字节序列,然而生成这些随机序列的成本却是不可忽视的。

    • · 查看原书依据

      衰减错误率的算法 在这个小节中,我们要学习的是这样一种算法:它的结果可能是错的,但是会衰减错误率。通过适度的计算,它的错误率可以非常低。

    参考来源

    - 位置:《算法技术手册》第10章《第10章 最后的招数》(spine1676;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1638_split_001.html;u285-ch10-001)。 - 结论依据:285全文及286、290对照实读。 - 原始内容:概率算法是确定性算法一个很有趣的替代方案。同样的输入同样的算法,运行两次的结果可能是不一样的,有时候我们会容忍错误的发生,也会接受算法最终告知问题无法解决。 一个重要假设是,算法可以利用随机位序列。其实随机性很难定义,虽然我们已经有几个用于检测随机性的测试,不过实际上很难生成满足这些测试的比特串。 - 位置:《算法技术手册》第10章《另类算法》(spine1676;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1638_split_001.html;u286-ch10-001)。 - 结论依据:286列出结果准确性、实例处理方式、顺序执行和确定性四项假设;放宽任一项都需重新定义成本及正确性要求。 - 原始内容:四大设定的算法。 ·结果必须是正确的。 ·每次只解决一个实例。 ·顺序的。 ·确定性的。 抛开这些设定使我们能够创造出各种各样不同类型的算法。 - 位置:《算法技术手册》第10章《随机算法》(spine1680;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1642.html;u290-ch10-001)。 - 结论依据:290强调随机数生成和伪随机序列;是否需要不可预测性、统计独立性或可复现实验应由用途决定。 - 原始内容:伪随机序列,来替代真正的随机字节序列,然而生成这些随机序列的成本却是不可忽视的。 - 位置:《算法技术手册》第10章《结果可能出错却可以衰减错误率的算法》(spine1682;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1644.html;u293-ch10-001)。 - 结论依据:293指出重复实验可降低错误率,但需要给出单次错误模型、独立性和组合规则,不能对任意相关实验直接套乘法。 - 原始内容:衰减错误率的算法 在这个小节中,我们要学习的是这样一种算法:它的结果可能是错的,但是会衰减错误率。通过适度的计算,它的错误率可以非常低。