Foundations-of-computer-science.docx

※Chapter 1
一、The Von Neumann model
Three idea:
1. Four subsystem
Memory→store data and program
ALU→calculations and logic operations take place
Control→control the operations of Memory,ALU,input/output
Input /output→accept input data and program / send the result out
2. Stored program concept
3. Squential execution of instructions
二、Programming was a task done by an operator or engineer before the actual data processing began.
三、Program must be a sequence of instructions. A program is a set of instructions executed sequentially that tells the computer what to do with the data.
四、A step-by-step solution to a problem is called an algorithm.
五、Software engineering is the design and writing of programs in a structured form.
六、History.
1. First mechanical calculator Pascaline
2. Structured programming language Pascal
3. First machine that used the idea of storage and programming was the Jacquard loom.
4 .First special-purpose computer that encoded information electrically was called ABC ( solve a system of linear equations )
5 .First general-purpose machines named Z1
6 .First general-purpose electronic computer was called ENIAC.
7 .First computer based on Von Neumann model was called EDVAC and EDSAC.
8. First generation: vacuum tubes as electronic switches
9. Second generation: transistors instead of vacuum tubes
10. Third generation: integrated circuit
11. Fourth generation: microcomputers
12. High-level programming languages FORTRAN and COBOL separated the programming task from the computer operation.

※Chapter 2 ( Data Representation )
一、Different data types
1. text
2. number
3. image
4. audio
5. video
二、A bit is the smallest unit of data that can be stored in computer.
三、All data from outside are transformed into an uniform representation called a bit pattern.
四、A bit pattern of length 8 is called a byte.
五、Codes is different sets of bit patterns have been designed to represent text symbols. The process of transforming data into a bit pattern is called coding.
1. (ASCII) Use a 7-bit pattern. The only difference between upper- and lowercase characters are distinguished by the sixth bit from the right.
2. (Extended ASCII) a code uses 8-bit patterns. A extra 0 is added to the left. I
3. (EBCDIC) a code uses 8-bit patterns. It was used in IBM mainframes.
4. (Unicode) use 16-bit patterns。
5. (ISO) use 32-bit patterns.
六、JAVA language uses unicode to represent characters.
七、Images represented by one of two methods: bitmap graphic or vector graphic.
1. bitmap
①Divided into a matrix of pixels→Each pixel is assigned a bit pattern (to represent color images, each pixel is assigned to three bit pattern RGB)→bit patterns is stored in computer
②Can rescale the image by changing the size of the pixels,which creates a ragged or grainy look.
2. vector: Decomposed into a combination of curves and lines→formulas is stored in a computer
八、Audio(representation of music or sound) data are transformed to bit patterns through sampling, quantization, and coding.
1. Sampling : The magnitude of the signal is measured at equal intervals.
2. Quantization : The sample is assigned a value from a set.
3. Coding : The quantized values are changed into binary patterns.

※Chapter 3 ( Number Representation )
一、integer representation
1. Unsigned:
①range: 0 ~ 2N-1
②application: counting and addressing
2. Signed:
⑴Sign-and-Magnitude:
①range: -(2N-1-1)~ +(2N-1-1)
②application: changing analog signals to digital signals.
⑵One’s Complement
①range: -(2N-1-1)~ +(2N-1-1)
②application: error detection and correction.
⑶Two’s Complement
①range: -(2N-1)~+(2N-1-1) (负数多了一位)
②application: standard representation for storing integers today
3. The maximum unsigned integer depends on the number of bits the computer allocates to store an unsigned integer.
4. Bit allocation is the number of bits used to represent an integer(N)
二、Floating-point representation
1. Excess_X system
⑴ store both positive and negative numbers
⑵ Application: store the exponential value of fraction.
⑶ magic number: a positive number used(added) in conversion process. Normally 2N-1 or 2N-1-1 (N is the bit allocation)
2. Normalization
⑴ standard representation for floating-point numbers.
⑵ make operations on numbers easier.
⑶ three pieces of information : sign, exponent and mantissa
⑴sign : 0 or 1
⑵exponent : define the movement of the decimal point.
⑶mantissa: the bits to the right of the decimal point. It define the precision of the number.
3. IEEE standards
( standard representation for floating-point numbers )
1. Excess_127 : 1 / 8 / 23
2. Excess_1023 : 1 / 11 / 52

※Chapter 4 ( Operations on bits )
一、Arithmetic operations
1. including adding, subtracting, multiplying, dividing
⑴adding : If there is a final carry after the leftmost column addition, discard it.(最后的进位忽略)
⑵subtracting : a - b changed into a + (-b)
2. The steps
⑴Check the sign
⑵Move the decimal points
⑶Add or subtract the mantissa
⑷Normalize the result
⑸Check for any overflow
二、Overflow
1. Overflow is an error that occurs when you try to store a number that is not within the range defined by bit allocation.
三、Logical Operation
1. accept 1 or 2 bits to create only 1 bit.
2. NOT : inverse all bits
3. AND : 有0必0
Unset ( force to 0 )
3. OR : 有1必1
Set ( force to 1 )
4. XOR : 1 & X→NOT (X)
Flip bits
四、Shift Operation ( on unsigned number )
1. Right-shift operation discards the rightmost bit.( divide )减少
2. Left-shift operation discards the leftmost bit.( multiple )增加
五、Truth table
1. all the possible input combinations with the corresponding output.