a-level-miscellany.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>A Level Miscellany</title>
   5     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
   6     <style type="text/css">
   7       /* Slideshow styles */
   8       body {
   9         font-size: 20px;
  10       }
  11       h1, h2, h3 {
  12         font-weight: 400;
  13         margin-bottom: 0;
  14       }
  15       h1 { font-size: 3em; }
  16       h2 { font-size: 2em; }
  17       h3 { font-size: 1.6em; }
  18       a, a > code {
  19         text-decoration: none;
  20       }
  21       code {
  22         -moz-border-radius: 5px;
  23         -web-border-radius: 5px;
  24         background: #e7e8e2;
  25         border-radius: 5px;
  26         font-size: 16px;
  27       }
  28       .plaintext {
  29         background: #272822;
  30         color: #80ff80;
  31         text-shadow: 0 0 20px #333;
  32         padding: 2px 5px;
  33       }
  34       .ciphertext {
  35         background: #272822;
  36         color: #ff6666;
  37         text-shadow: 0 0 20px #333;
  38         padding: 2px 5px;
  39       }
  40       .indexlink {
  41         position: absolute;
  42         bottom: 1em;
  43         left: 1em;
  44       }
  45        .float-right {
  46         float: right;
  47       }
  48     </style>
  49   </head>
  50   <body>
  51     <textarea id="source">
  52
  53 # A-level Miscellany ![Open University logo](oulogo_hor.png)
  54
  55 * Hashing
  56 * Boolean algebra
  57 * Karnaugh maps
  58 * Python file handling
  59
  60 ---
  61
  62 layout: true
  63
  64 .indexlink[![Open University logo](oulogo_hor.png) [Index](index.html)]
  65
  66 ---
  67
  68 # Hashing
  69
  70 Convert any of a large range of value to a small range of values
  71
  72 Two purposes:
  73
  74 1. Putting many things in few buckets
  75 2. Cryptographic signing
  76
  77 ---
  78
  79 # Hashing many things into a few buckets
  80 Useful for dividing items into files, or balancing items across any data structure.
  81
  82 Some examples (from [Geoff Kuenning's old course notes](http://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html))
  83 .float-right[![Chaining hash table collisions: from https://commons.wikimedia.org/wiki/File:Hash_table_5_0_1_1_1_1_1_LL.svg#mediaviewer/File:Hash_table_5_0_1_1_1_1_1_LL.svg](Hash_table_5_0_1_1_1_1_1_LL.svg)]
  84
  85 * **Division method** (Cormen) Choose a prime that isn't close to a power of 2. h(k) = k mod m. Works badly for many types of patterns in the input data.
  86
  87 * **Knuth Variant on Division** h(k) = k(k+3) mod m. Supposedly works much better than the raw division method.
  88
  89 * **Multiplication Method** (Cormen). Choose m to be a power of 2. Let A be some random-looking real number. Knuth suggests M = 0.5*(sqrt(5) - 1). Then do the following:
  90     1. s = k × A
  91     2. x = fractional part of s
  92     3. h(k) = floor(m × x)
  93
  94 Problem of hash collisions, where multiple items provide the same hash value. In a data structure, do something like chain multiple values together.
  95
  96 ---
  97
  98 # Cryptographic hash functions
  99
 100 Maps a large file into a smaller space of values, e.g. SHA-256 maps any file to a 256-bit digest
 101
 102 Cryptographic hashes have additional features:
 103
 104 * Easy to compute
 105 * One way: can't derive a source from a hash
 106 * Sensitive: modifying a source changes the hash
 107 * Few collisions: different souces have different hashes
 108
 109 MD5, SHA-1 in common use, but broken. SHA-2 developed by NSA, but seems secure...
 110
 111 Useful for validating messages, downloaded files, etc.
 112
 113 * Alice posts message and hash
 114 * Bob downloads message and hash
 115 * Bob computes hash for message and compares to what Alice posted
 116 * If they're equal, Bob's happy that the download was successful
 117 * If Eve changed the message in transit, the hashes won't be the same
 118
 119 ---
 120
 121 # Signing messages: authentication
 122
 123 Assume a public key encryption scheme.
 124
 125 * Alice finds a message's hash, encrypts it with her private key
 126 * Alice sends the message plus encrypted hash to Bob
 127 * Bob decrypts the hash with Alice's public key
 128 * Bob hashes message and compares it what Alice sent
 129 * If they're the same, Bob knows
 130     1. The message wasn't changed in transit
 131     2. Alice must have sent the message, as only she had the private key
 132
 133 See also TU100 Block 5 Part 3 on cryptography and security.
 134
 135 ---
 136
 137 # Bitcoin
 138 Hashes used as proof of work for 'mining' bitcoins.
 139
 140 * Block is transaction history + nonce word
 141 * Challenge is to find a nonce word that gives a hash in the correct range
 142 * No shortcut: must try many, many nonces and see what works
 143
 144 ---
 145
 146  # Boolean algegra identities
 147
 148 |Rule | Left | Right |
 149 |------|----:|:----|
 150 |`\(\text{Associativity of } \vee                             \)`|`\( x \vee (y \vee z)     \)`|`\( = (x \vee y) \vee z \)`|
 151 |`\(\text{Associativity of } \wedge                           \)`|`\( x \wedge (y \wedge z) \)`|`\( = (x \wedge y) \wedge z \)`|
 152 |`\(\text{Commutativity of } \vee                             \)`|`\( x \vee y              \)`|`\( = y \vee x \)`|
 153 |`\(\text{Commutativity of } \wedge                           \)`|`\( x \wedge y            \)`|`\( = y \wedge x \)`|
 154 |`\(\text{Distributivity of } \wedge \text{ over } \vee \quad \)`|`\( x \wedge (y \vee z)   \)`|`\( = (x \wedge y) \vee (x \wedge z) \)`|
 155 |`\(\text{Identity for } \vee                                 \)`|`\( x \vee 0              \)`|`\( = x \)`|
 156 |`\(\text{Identity for } \wedge                               \)`|`\( x \wedge 1            \)`|`\( = x \)`|
 157 |`\(\text{Annihilator for } \wedge                            \)`|`\( x \wedge 0            \)`|`\( = 0 \)`|
 158 |`\(\text{Double negation }                                   \)`|`\( \neg \neg x           \)`|`\( = x \)`|
 159 |`\(\text{De Morgan's Law }                                   \)`|`\( \neg ( x \wedge y )   \)`|`\( = \neg x \vee \neg y \)`|
 160 |`\(\text{De Morgan's Law }                                   \)`|`\( \neg ( x \vee y )     \)`|`\( = \neg x \wedge \neg y \)`|
 161
 162 You can prove all these by truth tables.
 163
 164 ---
 165
 166 # Boolean Notation
 167
 168 `\( \wedge = \& = × = \cdot  = \text{and}\)` ; `\( \vee = | = + = \text{or}\)` ; `\( \neg x = \: \sim x = x' = \overline x = \text{not}\)`
 169
 170 ## implies
 171
 172 `implies` is a connective: `\(a \text{ implies } b = a \rightarrow b = a \supset b = \neg a \vee b \)`
 173
 174 `\( A \)` | `\( B \)` | `\( \neg A \)` | `\( \neg A \vee B \)` | `\( A \rightarrow B \)`
 175 :--------:|:---------:|:--------------:|:---------------------:|:-----------------------:
 176     F     |     F     |       T        |           T           |          T
 177     F     |     T     |       T        |           T           |          T
 178     T     |     F     |       F        |           F           |          F
 179     T     |     T     |       T        |           T           |          T
 180
 181 If A is true, B must be true. If A is false, B can be anything.
 182
 183 Use other notation for derivations and proofs: see your friendly mathematicians.
 184
 185 ---
 186
 187 #Karnaugh maps
 188
 189 .float-right[![Karnaugh maps](Karnaugh_map2.png)]
 190
 191 A way of visually simplifying Boolean expressions.
 192
 193 Draw the biggest loops you can, don't worry if the overlap.
 194
 195 ---
 196
 197 # File handling in Python
 198
 199 * Reading, writing appending
 200 * `read()` and `readlines()`
 201 * Text and binary
 202 * Text encodings
 203
 204
 205
 206
 207     </textarea>
 208     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
 209     </script>
 210
 211     <script type="text/javascript"
 212       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
 213
 214     <script type="text/javascript">
 215       var slideshow = remark.create({ ratio: "16:9" });
 216
 217       // Setup MathJax
 218       MathJax.Hub.Config({
 219         tex2jax: {
 220         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
 221         }
 222       });
 223       MathJax.Hub.Queue(function() {
 224         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 225             return(elem.SourceElement());
 226         }).parent().addClass('has-jax');
 227       });
 228       MathJax.Hub.Configured();
 229     </script>
 230   </body>
 231 </html>