计算机科学和python编程学习（week1）

Week 1

What does a computer do?

• Fundamentally

1.Performs calculation

2.Remembers the results

What calulations?

• Built in primitives
• Creating our own methods of calculating

So are there limits?

• Despite its speed and storage, a computer does have limitations.
  • Some problems still too complex ( Accurate weather predictation 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图灵停机问题)

Computational problem solving

• What is computation?

-What is knowledge?

Declarative knowledge (statement of fact)

Imperative knowledge (how to methods or recipes) can create new information

Declarative knowledge

• The square root of a number X is a number y such that y*y =X
• We cannot use this to find the square root of a particular instance of X.

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

1.Sart with a guess, called g

2.If g*g is close enough to X, stop and stay that g is the answer

3.Otherwise make a new guess, by averaging g and X/g

4.Using this new guess, repeat the process untill we get close enough

How do we capture a recipe in a mechanical process?

• Build a machine to compute square roots

Fixed Program Computers

Eg.Caculator

• Use a machine that stores and manipulates instructions

Stored program computer(现代计算机的雏形)

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.

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.

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 mechanims for deducing meanings or values associated with computations or expressions

Aspects of lamguages

• Primitive constructs. 1.Programming language(numbers, strings, simple operators 2.English(words)
• Syntax句法 (which strings of characters and symbols are well- formed) 1. Programming language eg. We'll get to specifies shortly, but for example 3.2+3.2 is a valid Python expression 2. English, 'cat dog boy' is not syntactically valid, as not in form of an acceptable sentence.
• Static semantics静态语义- which syntactically valid strings have a meaning 1. English- 'I are big' has orm<noun><intransitive verb><noun>, so syntactically valid, but is not valid English because 'I' is singular, 'are' is plural 2. Programming language- for example,<literal><operator><literal> is a valid syntactic form, but 2.3/'abc' is a stactic semantic error.
• Semantics语义- what is the meaning associated with a syntactically correct string of symbols with no static semantic errors 1.English can be ambiguous 2.Programming languages-always has exactly one meaning But meaning(or value) may not be what programmer intended

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)

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.

Programming languages

• Goal:

Need a way to describe algorithmic steps such that computer can use them to execute process

Programming language defines syntax and semantics needed to translate our computational ideas into mechanical steps

Options for programming languages

快速，然而很难定位出错的地方。

运行速度稍慢，但是容易找到出错的地方因为指令是一条一条地执行的。

Python programs

• Program (or script) is a sequence of definitions and commands

1. Definitions evaluated and commmands executed by Python interpreter in a shell
2. Can be typed directly into a shell, or stored in a file that is read into the shell and evaluated

• Command (or statement) instructs interpreter to do something

Objects

• At heart, programs will manipulate data objects
• Each object has a type that defines the kinds of things programs can do to it.
• Objects are: Scalar (i.e. cannot be subdivided) Non-scalar (i.e. have internal structure that can be accessed)

Scalar objects

• Int-used to represent intergers,eg. 5 or 10086
• Float-used to represent real numbers, eg. 3.14 or 27.0
• Bool-used to represent Boolean values True and False
• The built in Python function type returns the type of an object

Expressions

• Objects and operators can be combined to form expressions, each of which denotes an object of some type
• The syntax for most simple expressions is: <object><operator><object>

Operators on ints and floats

• i+j-sum, if both are ints, result is int, if either is float, result is float.
• i-j-difference
• i*j-product
• i/j-division-if both are ints, result is int, representing quotient without remainder
• i%j-remainder
• i**j- I raised to the power of j (阶乘)

Performing simple operations

• Parentheses define sub-computations-complete these to get values before evaluating larger expression

1.(2+3)*4

2.5*4

3.20

• Operator precedence:

In the absence of parentheses (within which expressions are first reduced), operators are executed left to right, first using** then*and/, and then +and -.

Comparison operators on ints and floats

• i>j-returns True if strictly greater than
• i>=j-returns True if greater than or equal
• i<j
• i<=j
• i==j-returns True if equal
• i!=j-returns True if not equal

Operators on bools

• A and B is True if both are True
• A or B is True if either is True
• Not A is True if A is False, and False if A is True

Type conversions (type casting)

• We can often convert an object of one type to another, by using the name of the type as a function

Eg.float(3) has the value of 3.0;Int(3.9) truncates to 3

Simple means of abstraction

• While we can write arbitrary expressions, it is useful to give names to values of expressions, and to be able to reuse those names in place of values
• Pi=3.14159
• Radius=11.2
• Area=pi*(radius**2)

Binding variables and values

• The statement pi = 3.14159 assigns the name pi to the value of the expression to the right of the=
• Think of each assignment statement as creating a binding between a name and a value stored somewhere in the computer
• We can retrive the value associated with a name or variable by simply invoking that name

Changing bindings

• Variable names can be rebound, by invoking new assignments statements.
• For exampke, if we now execute:Radius=14.3
• Note that this doesn't change the value associated with area.(容易错误的地方)

Non-scalar objects

• We will see many different kinds of compound objects
• The simplest of these are strings, objects of type str
• Literals of type string can be written using single or double quotes

-'abc'

-"abc"

-'123'-this is a string of characters, not the number

Extracting parts of strings

• Indexing:

'abc'[0] returns the string 'a'

'abc'[2] returns the string 'c'

'abc'[3] is an error (as we cannot go beyond the boundaries of the string)

'abc'[-1] returns the string 'c' (essentially counting backwards from the start of the string)

• Slicing:

If s is a string, the expression s[start:end] denotes the substring that starts at start, and ends at end -1.

Eg.'abc'[1:3] returns the value of 'bc'

Programs (or scripts)

• While we can type expressions directly to a Python interpreter (for example using an interface such as an IDLE shell), in general we will want to include statements in a program file,F5=restart
• Executing an expression from a script will not produce any output; for that we need statements (not expressions), such as

Print('ab')

Print('3'*3)

Some simple code

• One can use variable names anywhere you might use the expression whose value it holds

myString = 'too much'

Weather = 'snow'

Print(myString + '' + Weather) output: too much snow

Some observations

• Comments appear after a #

These are very valuable, as they help a user understand decisions the programmer has made in creating the program

Well commented code should be very readable by a user

• A straight line program simply executes each statement in order, with no variation in order
• Most programs require more sophisticated flow control

Branching programs

• The simplest branching statement is a conditional if

1.A test (expression that evaluates to True or False)

2.A block of code to execute if the test is True

3.An optional block of code to execute if the test is False

Some observations

• The expression x%2==0 evaluates to True when the remainder of x divided by 2 is 0
• Note that== is used for comparison, since = is reserved for assignment
• The indentation is important缩进很重要 1.each indented set of expression denotes a block of instructions 2.For example, if the last statement were indented, it would be executed as part of the else block of code

Note how this indentation provides a visual structure that reflects the semantic structure of the program

Nested conditionals : 嵌套条件

Compound Booleans : 复合布尔

What have we added?

• Branching programs allow us to make choices and do different things
• But still the case that at most, each statement gets executed once
• So maximum time to run the program depends only on the length of the program
• These programs run in constant time

Iteration迭代

• Need one more concept to be able to write programs of arbitrary complexity任意复杂度

1.start with a test

2.if evaluates to True, then execute loop body once, and go back to reevaluate the test

3.Repeat until test evaluates to False, after which code following iteration statement is executed

Some properities of iteration loops:

• Need to set an iteration variable outside the loop,eg. itersLeft in the case
• Need to test that variable to determine when done, eg. itersLeft = 0
• Need to change that variable within the loop in addition to other work, eg. itersLeft = itersLeft -1

Iterative code迭代代码

• Branching structures (conditionals) let us jump to different pieces of code based on a test

Programs are constant time

• Looping structures (eg. while) let us repeat pieces of code until a condition is satisfied

Programs now take time that depends on values of variables, as well as length of program

Classes of algorithms

• Iterative algorithms allow us to do more complex things than simple arithmetic
• We can repeat a sequence of steps multiple times based on some decision; leads to new classes of algorithms
• One useful example are "guess and check" methods

Guess and check

• Remember our "declarative" definition of square root of X
• If we could guess possible values for square root (call it g), then can use definition to check if g*g =X
• We just need a good way to generate guesses

Finding a cube root (立方根) of an integer

• One way to use this idea of generation guesses in order to find a cube root of X is to first try 0**3,then 1**3,then 2**3, and so on
• Can stop when reach k such that k**3 >X
• Only a finite umber of cases to try

考虑当立方数为负整数时的情况：在原基础上修改程序，运用绝对值函数abs(x)

Loop characteristics

• Need a loop variable

1.Initialized outside loop

2.Changes within loop

3.Test for termination depends on variable

• Useful to think about a decrementing function(递减函数)

1.Maps set of program variables into an interger

2.When loop is entered, value计算式的值 is non-negative

3.When value计算式的值 is <=0, loop terminates, and

4.Value is decreased every time through loop

• Here we use abs(x)-ans**3

Exhaustive enumeration穷举

穷举搜索法是编程中常用到的一种方法，通常在找不到解决问题的规律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：

（1）顺序列举 是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

（2）排列列举 有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。

（3）组合列举 当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。

• Guess and check methods can work on problems with a finite number of possibilities
• Exhaustive enumeration is a good way to generate guesses in an organized manner