结构图
抓住重点即可，不必再过渡去纠缠。
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:*
- 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
- Put custard mixture over heat
- Str
- Dip spoon in custard
- Remove spoon and run finger across back of spoon
- If clear path is leU, remove custard from heat and let cool
- 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
- Fixed Program Computers
- 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
- Built from predefined set of primitive instructions
-
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
草稿图
网友评论