X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=algorithms.html;h=bbe92f16b0480599da0df4e0230dec35e79a6ad0;hb=fc01177820fbcb4d4abba6afc772786f162b5b2e;hp=57fdbae668b0cc1a78a09b1ce7c5e43ff7b6ce60;hpb=c83ef2510a03a1727b4ef7367edd179fab6c37a6;p=cas-master-teacher-training.git diff --git a/algorithms.html b/algorithms.html index 57fdbae..bbe92f1 100644 --- a/algorithms.html +++ b/algorithms.html @@ -54,6 +54,8 @@ ## What's all the fuss about? +![Alan Turing](alan-turing.jpg) + --- layout: true @@ -71,6 +73,7 @@ Back when computers were human... * As much notepaper as you wanted * Input → output +.float-right[![right-aligned Growth rates ](turing-machine.jpg)] ## Turing machines Simplified human computer. @@ -89,6 +92,14 @@ Algorithm is the instructions Repetition == iteration or recursion +What questions can we ask about algorithms? + +* Is it correct? +* Does it terminate? +* How long does it take? + +Different hardware works at different rates, so ask about how the run time changes with input size. + --- # Growth rates @@ -143,6 +154,9 @@ word1 = "cat", word2 = "catty" # Anagrams version 1a: checking off (fixed) + + + + + +
``` Given word1, word2 @@ -158,6 +172,26 @@ for pointer in range(len(word2)): anagram? = False return anagram? ``` + +``` +Given word1, word2 + +if len(word1) == len(word2): + anagram? = True + for character in word1: + for pointer in range(len(word2)): + if character == word2[pointer]: + word2[pointer] = None + else: + anagram? = False + return anagram? +else: + return False +``` +
--- @@ -300,7 +334,8 @@ Don't forget bogosort! * Often leads to logarithmic growth "Guess the number" game - * What if I don't tell you the upper limit? + +* What if I don't tell you the upper limit? ## Dynamic programming @@ -314,6 +349,13 @@ Build a soluion bottom-up from subparts * Greedy algorithms * Backtracking +# Parallelism vs concurrency + +* Parallelism is implementation + * spread the load +* Concurrency is domain + * new task arrives before you've finished this one + --- # Making change @@ -369,19 +411,19 @@ Initial: ---- 0 | 1* | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... -|-|-|-|-|-|-|-|-|-|-|- -(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ... +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 0, 0) | (0, 0, 1) | (1, 0, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ... -- ---- 0 | 1 | 2* | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... -|-|-|-|-|-|-|-|-|-|-|- -(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ... +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (1, 0, 1) | (0, 1, 1) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | ... -- ---- 0 | 1 | 2 | 3* | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ... -|-|-|-|-|-|-|-|-|-|-|- -(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (0, 0, 0) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ... +(0, 0, 0) | (1, 0, 0) | (0, 1, 0) | (1, 1, 0) | (0, 2, 0) | (0, 0, 1) | (1, 0, 1) | (0, 1, 1) | (1, 1, 1) | (0, 0, 0) | (0, 0, 0) | ... --- @@ -421,6 +463,14 @@ The computer would either answer "Yes," "No," or never stop working. This is the Halting problem. +```python +while i != 0: + print(i) + i -= 1 +``` + +Will this halt? When will it not? + --- # Universal Turing machine @@ -440,7 +490,146 @@ A *universal* Turing machine can take the description of any Turing machine and *This* shows that computing as we know it is possible. +* Programming +* Abstraction +* Virtual machines +* ... + +--- + +# Back to halting + +* Universal Turing machine can do any possible computation +* Has the same halting behaviour of the emulated machine + +Can we build another machine that detects if a machine halts when given some input? + +Assume we can... + +```python +def does_it_stop(program, input): + if very_clever_decision: + return True + else: + return False +``` + +But I can use the program listing as an input: + +```python +def stops_on_self(program): + return does_it_stop(program, program) +``` + +--- + +# Halting: the clever bit + + + + + + +
+```python +def does_it_stop(program, input): + if very_clever_decision: + return True + else: + return False +``` + +```python +def stops_on_self(program): + return does_it_stop(program, program) +``` +
+ +Let's put an infinite loop in a program that detects infinite loops! + +```python +def bobs_yer_uncle(program): + if stops_on_self(program): + while True: + pass + else: + return True +``` + +If a `program` halts on on itself, `bobs_yer_uncle` doesn't halt. If `program` doesn't halt, `bobs_yer_uncle` returns `True`. + +-- + +What does this do? +```python +bobs_yer_uncle(bobs_yer_uncle) +``` + +--- + + + + + + + +
+```python +def does_it_stop(program, input): + if very_clever_decision: + return True + else: + return False +``` + +```python +def stops_on_self(program): + return does_it_stop(program, program) +``` + +```python +def bobs_yer_uncle(program): + if stops_on_self(program): + while True: + pass + else: + return True +``` +
+ +What does this do? +```python +bobs_yer_uncle(bobs_yer_uncle) +``` + + + + + + + + + +
If it halts...If doesn't halt...
+
    +
  • `stops_on_self(bobs_yer_uncle)` returns `False`
    • +
  • `does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `False`
    • +
  • `bobs_yer_uncle(bobs_yer_uncle)` must loop forever
    • +
+Contradiction! +		 +
    +
  • `stops_on_self(bobs_yer_uncle)` returns `True`
    • +
  • `does_it_stop(bobs_yer_uncle, bobs_yer_uncle)` returns `True`
    • +
  • `bobs_yer_uncle(bobs_yer_uncle)` must halt
    • +
+Contradiction! +
+ +No flaw in the logic. The only place there could be a mistake is our assumption that `does_it_stop` is possible. + +(M269 has a different proof based on different sizes of infinity, and showing that there are infinitely more problems than there are Turing machines to solve them.)