1.Introduction to Computation an

结构图

抓住重点即可，不必再过渡去纠缠。

Key quotes：

• And like a good philosophical question, that leads to another, deeper philosophical question.

• Any interpreter that has that property is what we call Turing complete, which by the way says anything you compute in 1 programming language you can compute in any other programming language.
• The six basic operations/primitives that gives a language Turing completeness are:*

1. Right: Move the Machine’s head to the right of the current square

• Left: Move the Machine’s head to the left of the current square
• Print: Print a symbol on the current square
• Scan: Identify any symbols on the current square
• Erase: Erase any symbols presented on the current square
• Nothing/halt: Do nothing

思路分析：1.计算机的功能*4 2.算法*4 3.算法应用于计算机*3 4.构成语言的原材料等，初窥编程语言*4

一、Do and limits

第一部分*4： 思路分析：关键词：do and limits

• 从直观和可得性入手，从身边的电脑入手开始分析，
• 电脑能做什么？刨根问底，电脑的最基本功能是什么？
• 电脑能做的仅只是这些吗？还是从帮助直观理解的方面举例，在书中另外阐述了人类的发展曾经受限于计算能力。
• 进一步追问，只靠简单的计算能力就足够了吗？哪些是计算能力做不了的呢？
• 收到哪些限制呢？存储，计算速度，实际上受限于算法和数学的局限性

0.Goal:

• Become skillful at making a computer do what you want it to do
• Learn computational modes of thinking– Master the art of computational problem solving

1.What does a computer do?

• Fundamentally a computer:
• Performs calculations
• Remembers the results
• What calculations?
• Built in primitives
• Creating our own methods of calculating

2.Is that all it does?

• A billion calculations per second
• 100s of gigabytes of storage

3.Are simple calculations enough?

• Searching the World Wide Web
• Playing chess
• Good algorithm design also needed to accomplish a task!

4. So are there limits?

• Generally Limited by algorithm and capacity
• Despite its speed and storage, a computer does have limitations
• Some problems still too complex
• Accurate weather prediction at a local scale
• Cracking encryption schemes

• Some problems are fundamentally impossible to compute
  • Predicting whether a piece of code will always halt with an answer for any input

二、算法

第二部分*4 关键词：算法

• 思路分析：解释Computational Thikning和算法

5.Computational problem solving

• What is computation?

And like a good philosophical question, that leads to another, deeper philosophical question.

• What is knowledge?
• Declarative knowledge
• Statements of fact
• Imperative knowledge
• “how to” methods or recipes

6.Declarative knowledge

• “The square root of a number x is a number y such that y*y = x”
• Can you use this to find the square root of a particular instance of x?

7.Imperative knowledge

• Here is a “recipe” for deducing a square root of a number x – attributed to Heron of Alexandria in the first century AD
  • Start with a guess, called g
  • If g*g is close enough to x, stop and say that g is the answer Otherwise make a new guess, by averaging g and x/g
  • Using this new guess, repeat the process un(l we get close enough

8.Algorithms are recipes

1. Put custard mixture over heat
2. Str
3. Dip spoon in custard
4. Remove spoon and run finger across back of spoon
5. If clear path is leU, remove custard from heat and let cool
6. Otherwise repeat from step 2

三、算法在机器中的应用

第三部分*3 算法在电路和电子设备的最高级成果——计算机中的应用

9.How do we <u>capture</u> a recipe in a mechanical process?

• Build a machine to compute square roots
  • Fixed Program Computers
    • Calculator
    • Atanasoff and Berry’s (1941) computer for systems of linear equations
    • Alan Turing’s (1940’s) bombe – decode Enigma codes
• Use a machine that stores and manipulates instructions
  • Stored Program Computer

10.Stored program computer

• Sequence of instructions (program) stored inside computer

  • Built from predefined set of primitive instructions
    • Arithmetic and logic
    • Simple tests
    • Moving data

• Special program (interpreter) executes each instruction in order

  • Use tests to change flow of control through sequence, to stop when done

  这里的test是编程的关键，Conditional和Iterate都要用到Test

11.A basic machine architecture

四、编程语言的构成

第四部分*4：初窥编程语言

12.What are the basic primitives?

• Turing showed that using six primitives, can compute anything

• Turing complete

• Fortunately, modern programming languages have a more convenient set of primitives
• Also have ways to abstract methods to create new “primitives”

• But anything computable in one language is computable in any other programming language.

That is amazing!!!

13.Creating “recipes”

• Each programming language provides a set of primitive operations
• Each programming language provides mechanisms for combining primitives to form more complex, but legal, expressions
• Each programming language provides mechanisms for deducing meanings or values associated with computations or expressions

14.Aspects of languages

• Primitive constructs
  • Programming language – numbers, strings, simple operators
  • English – words
• Syntax – which strings of characters and symbols are well-formed
  • Programming language – we’ll get to specifics shortly, but for example 3.2 + 3.2 is a valid Python expression
  • English – “cat dog boy” is not syntactically valid, as not in form of acceptable sentence
• Static semantics – which syntactically valid strings have a meaning
  • English – “I are big” has form <noun> <intransitive verb> <noun>, so syntactically valid, but is not valid English because “I” is singular, “are” is plural
  • Programming language – for example, <literal> <operator> <literal> is a valid syntactic form, but 2.3/’abc’ is a static semantic error
• Semantics – what is the meaning associated with a syntactically correct string of symbols with no static semantic errors

• English – can be ambiguous
  • “I cannot praise this student too highly”
• Programming languages – always has exactly one meaning
  • But meaning (or value) may not be what programmer intended

15.Where can things go wrong?

• Syntactic errors
• Common but easily caught by computer
• Static semantic errors
  • Some languages check carefully before running, others check while interpreting the program
  • If not caught, behavior of program unpredictable
• • Programs don’t have semantic errors, but meaning may not be what was intended
  • – Crashes (stops running)
  • – Runs forever– Produces an answer, but not programmer’s intent

16.Our Goal

• Learn the syntax and semantics of a programming language
• Learn how to use those elements to translate “recipes” for solving a problem into a form that the computer can use to do the work for us
• Computational modes of thought enable us to use a suite of methods to solve problems

草稿图