发帖
雷达卡
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)
2 - Trivial compression
Compression is the act of taking data and encoding it (changing its form) in such a way that it takes up less space. Decompression is reversing the process, returning the data to its original form.
- There is a tradeoff between time and space. It takes time to compress a piece of data and to decompress it back into its original form. Therefore, data compression only makes sense in situations where small size is prioritized over fast execution.
3 - Unbreakable encryption
A one-time pad is a way of encrypting a piece of data by combining it with meaningless random dummy data in such a way that the original cannot be reconstituted without access to both the product and the dummy data - In essence, this leaves the encrypter with a key pair. One key is the product, and the other is the random dummy data. One key on its own is useless; only the combination of both keys can unlock the original data. When performed correctly, a one-time pad is a form of unbreakable encryption.
- One way of thinking about a Python 3 str is as a sequence of UTF-8 bytes. A str can be converted into a sequence of UTF-8 bytes (represented as the bytes type) through the encode() method. Likewise, a sequence of UTF-8 bytes can be converted back into a str using the decode() method on the bytes type.
- Three criteria that the dummy data used in a one-time pad encryption operation must meet for the resulting product to be unbreakable.
- same length as the original data
- truly random
- completely secret.
4 - Calculating pi
π = 4/1 - 4/3 + 4/5 - 4/7 + 4/9 - 4/11...
NOTE: This function is an example of how rote conversion between formula and programmatic code can be both simple and effective in modeling or simulating an interesting concept.
5 - The Towers of Hanoi
6 - Real-world applications
The techniques presented in this chapter (recursion, memoization, compression, and manipulation at the bit level)
- Recursion is at the heart of not just many algorithms, but even whole programming languages. In some functional programming languages, like Scheme and Haskell, recursion takes the place of the loops used in imperative languages. It is worth remembering, though, that anything accomplishable with a recursive technique is also accomplishable with an iterative technique.
- Memoization has been applied successfully to speed up the work of parsers (programs that interpret languages). It is useful in all problems where the result of a recent calculation will likely be asked for again. Another application of memoization is in language runtimes. Some language runtimes (versions of Prolog, for instance) will store the results of function calls automatically (auto-memoization), so that the function need not execute the next time the same call is made. This is similar to how the @lru_cache() decorator in fib6() worked.
- Compression has made an internet-connected world constrained by bandwidth more tolerable. The bit-string technique is usable for real-world simple data types that have a limited number of possible values, for which even a byte is overkill. The majority of compression algorithms operate by finding patterns or structures within a data set that allow for repeated information to be eliminated.
- One-time pads are not practical for general encryption. They require both the encrypter and the decrypter to have possession of one of the keys (the dummy data in our example) for the original data to be reconstructed, which is cumbersome and defeats the goal of most encryption schemes (keeping keys secret). But you may be interested to know that the name “one-time pad” comes from spies using real paper pads with dummy data on them to create encrypted communications during the Cold War. These techniques are programmatic building blocks that other algorithms are built on top of. In future chapters you will see them applied liberally.
京公网安备 11010802022788号
