Transcript Introduction to Computer Science week 01 “Computing…it is all

Foundations of
Computer Science
Computing …it is all about
Data Representation,
Storage, Processing, and
Communication of Data
3/26/2016
CS 112 – Foundations of Computer Science
1
A Computational Machine


What capabilities should a computing machine have ?
Well..any computational problem involves two primary
elements:
 Data (numbers, text strings, or images, ...) used for input,
manipulation and output
 Instructions (that describes the operations (e.g. arithmetic
or comparison) that must be performed on data pertinent
to the problem being solved
 Von Neumann – provided the insight that both data and
instructions could be stored together in the computer
3/26/2016
CS 112 – Foundations of Computer Science
2
A Computational Machine

Thus, the machine must have the following capabilities:
 Representation & Storage (of both Data, and the
Instructions that defines operations on data, why?)
 Data Processing (interpret Instructions and carry out
operations defined by these instructions on Data)
 Data input and Data output (I/O) (why?)
 Data Communication (optional, if the machine is
connected to other similar machines – via a network)
3/26/2016
CS 112 – Foundations of Computer Science
3
Computer Capabilities

A transistor can be set to either on (1) or off (0) by controlling the
direction of the electric current passing through it

Hundreds of Millions of transistors can be packed into a small
‘compact’ unit called the integrated circuit (IC) (a.k.a chips)
0 Volts
=
0 is stored
5 Volts
=
1 is stored
Electric current
No resistance
Electric current
resistance
transistor
Power source
Transistor is said to
be storing a 0 here
3/26/2016
transistor
Power source
Transistor is said to
be storing a 1 here
CS 112 – Foundations of Computer Science
4
Computer Capabilities
“Information in the Computer is bits + context”

Both data and instructions are encoded in the computer using
Bits (Binary digits)

Think of a Bit as a code that can be either equal to 0 or 1

Encoding means that for each data value or algorithm instruction
you use a code consisting of one or more bits to represent it.
 For example, Street Traffic lights is a form of encoding for instructions to
motorists (red = ‘stop’, yellow = ‘slow down’, green = ‘go’)

In computers bits are grouped together in 8-bit chunks called
Bytes (e.g. 00101010, 11111111, and 00000000)
3/26/2016
CS 112 – Foundations of Computer Science
5
Computer Capabilities
Representation
the encoding data using bits, and the
encoding instructions using bits
Storage
storing bits used to encode data and
instructions
Data Processing
for each instruction:
1) Interpreting the bits of the instruction, and
2) doing the operation specified in the
instruction on the bits of the data specified
in the instruction
3/26/2016
CS 112 – Foundations of Computer Science
6
Computer Capabilities
Data Input
converting data transferred into the machine
(say through a keyboard or mouse) into bits
(and storing these bits)
Data Output
converting bits of data into appropriate format
for transfer outside the machine (e.g. to the
screen)
Data Communication Transfer bits of data from one computer to
another
3/26/2016
CS 112 – Foundations of Computer Science
7
Computer Capabilities

What are some of the different types of data that may be
encountered?
 Text (sequences of characters used to represent names,
descriptions, etc.)
 Numeric (to represent different quantities, e.g. age, length,
height, amount of money, growth rates)
 Image (to represent photographic or synthesized pictures)
 Audio (to represent audio signals of humans and otherwise)
 Video (to represent video signals)
3/26/2016
CS 112 – Foundations of Computer Science
8
Computer Capabilities

What are some of the different types of instructions that may be
used on this data?
 Text (extracting characters, Concatenating characters
together, comparing characters)
 Numeric (arithmetic +, -, *, , comparison among other
operations)
 Audio (manipulate pitch, volume, high or low frequencies in an
audio signal)
 Image (manipulate pixels properties, e.g. color)
3/26/2016
CS 112 – Foundations of Computer Science
9
Data Representation & Storage
Representation by encoding works as follows:

First you have a value set; a fixed set of values you want to
encode (data values likes numbers, characters, instructions
to motorists,etc.).

You have a symbol set; a fixed set of symbols to use in
constructing codes for these values (for computers this is
generally the symbols {0,1}).

Using combinations of the symbols found in the symbol set
you construct a unique code corresponding to each value in
the value set.
3/26/2016
CS 112 – Foundations of Computer Science
10
Data Representation & Storage
Exercise I
To save Money a new traffic light device will be deployed
where only two colors are available red & green; propose
an encoding scheme that allows the stop, slow down, and
go instructions to be given to motorists using this new
traffic light device
Answer

What’s the value set ?

What’s the symbol set?

What’s the encoding scheme?
3/26/2016
CS 112 – Foundations of Computer Science
11
Data Representation & Storage
Exercise I
To save Money a new traffic light device will be deployed
where only two colors are available red & green; propose
an encoding scheme that allows the stop, slow down, and
go instructions to be given to motorists using this new
traffic light device
Answer

What’s the value set ? stop, slow down & go

What’s the symbol set? red & green

What’s the encoding scheme? stop = red, go = green &
slow down = red & green
3/26/2016
CS 112 – Foundations of Computer Science
12
Numeric Representation
What does 943 mean?
 As a decimal number

3/26/2016
CS 112 – Foundations of Computer Science
13
Numeric Representation
What does 943 mean?
 As a decimal number

9 * 102 = 9 * 100
+ 4 * 101 = 4 * 10
+ 3 * 100 = 3 * 1
= 900
= 40
= 3
943
called positional notation
here represented in base 10
3/26/2016
CS 112 – Foundations of Computer Science
14
Binary Representation

Generally speaking binary representation
(base 2) of integers will use the symbols
0 & 1 in a positional representation where
positions represent powers of 2.
24 23 22 21 20 or 16 8 4 2 1
thus 11001 = 16 + 8 + 0 + 0 + 1 = 25
3/26/2016
CS 112 – Foundations of Computer Science
15
Binary Representation

Represent the decimal number 125 in binary

The standard algorithm
(1) Start with your number, here 125, in base 10
(2) Divide the number (125) by 2 and record the remainder
125 / 2 has a quotient of 62 and a remainder of 1
(3) If the quotient = 0 stop,
else
Go to step 2 and repeat using the quotient as the
number
(4) Record the remainders recorded from right to left
3/26/2016
CS 112 – Foundations of Computer Science
16
Binary Representation
Q
R
125 / 2
62 1
62 / 2
31 0
31 / 2
15 1
15 / 2
7
1
7/2
3
1
3/2
1
1
1/2
0
1
12510 = 11111012
3/26/2016
CS 112 – Foundations of Computer Science
17
Binary Addition
How did we learn to add?
?? Do you remember the tables ??
0+0=0
0+1=1
1+0=0
1 + 1 = 10
carry (hmmm… why didn’t they
give us this in grade school?)
3/26/2016
CS 112 – Foundations of Computer Science
18
Binary Addition

Example
11111
101110
11011
1001001
3/26/2016
carry
CS 112 – Foundations of Computer Science
19
Negative Numbers
Sign and Magnitude
It's what we're used to: +17 -45
Fortunately there are only two choices for the sign: + and So why no add a bit, and then use
0 for + and 1 for Thus
magnitude
1 0100110 -> - 38
sign bit
3/26/2016
CS 112 – Foundations of Computer Science
20
Negative Numbers
Among other things this leads to two zeros
0 0000000 = +0 and 1 0000000 = -0
that aren't really different numbers.
Try instead something called 2’s complement
3/26/2016
CS 112 – Foundations of Computer Science
21
Negative Numbers
Might think of as clock arithmetic
-1
0
1
-2
1111
2
3
-4
4
5
-6
6
-7
3/26/2016
-8
7
0001
1110
-3
-5
0000
0010
1101
0011
1100
0100
1011
0101
1010
0110
1001 1000
CS 112 – Foundations of Computer Science
0111
22
Addition and Subtraction
3 + 2 = 5 or 0011 + 0010 = 0101
1111
0000
0001
1110
0010
1101
0011
1100
0100
1011
0101
1010
0110
1001 1000
3/26/2016
0111
CS 112 – Foundations of Computer Science
23
Addition and Subtraction
7 - 4 = 3 or 0111 - 0100 = 0011
1111
0000
0001
1110
0010
1101
0011
1100
0100
1011
0101
1010
0110
1001 1000
3/26/2016
0111
CS 112 – Foundations of Computer Science
24
Addition and Subtraction
-7 + 4 = -3 or 1001 + 0100 = 1101
1111
0000
0001
1110
0010
1101
0011
1100
0100
1011
0101
1010
0110
1001 1000
3/26/2016
0111
CS 112 – Foundations of Computer Science
25
Negative Numbers
2’s Complement
 Take the 1’s complement and add 1
5 -> 0101
1’s comp -> 1010
add 1
1
1011 -> -5
 Now go the other way
-5 -> 1011
1’s comp -> 0100
add 1
1
0101 -> 5
Thus the 2’s complement of a 2’s complement is the
original number (same is true for the negative)
3/26/2016
CS 112 – Foundations of Computer Science
26
Negative Numbers
Find -56 using an eight bit representation
56
->
00111000
1's comp
11000111
add 1
1
11001000 -> -56
What does 10111001 represent?
2's complement it
01000110
1
01000111 -> 71
so the original number must have been -71
3/26/2016
CS 112 – Foundations of Computer Science
27
Negative Numbers
Find -83 using an eight bit representation
What does 10010101 represent?
What does 11111111 represent?
3/26/2016
CS 112 – Foundations of Computer Science
28
Need More Bits
Positive Numbers – Fill new positions to the left with 0
7 in four bits
= 0111
7 in eight bits = 0000 0111
7 in sixteen bits = 0000 0000 0000 0111
Negative Numbers – Fill new positions to the left with 1
-7 in four bits = 1001
-7 in eight bits = 1111 1001
-7 in sixteen bits= 1111 1111 1111 1001
3/26/2016
CS 112 – Foundations of Computer Science
29
Addition and Subtraction
Addition – follow the usual rules
 5+2=7
-4 + 5 = 1
0101
1100
0010
0101
0111
10001
0000
0001
1111
carry out – ignored, it means
1110
0010
you passed 0
1101
0011
0100
1100
1011
0101
1010
0110
1001 1000
3/26/2016
0111
CS 112 – Foundations of Computer Science
30
Addition and Subtraction
Subtraction can be represented as the addition of the
negative
7-5
->
7 + (-5)
0111
0111
- 0101
+ 1011
10010
-4 - 3
3/26/2016
->
-4 + (-3)
1100
1101
11001
CS 112 – Foundations of Computer Science
31
Addition and Subtraction
So is there any concern?
Yes – no matter how many bits you use there is some
maximum and some minimum number that can be
represented.
For four bits those are +7 and -8 respectively.
5 + 6 = 11 and -6 + (-4) = -10 are beyond a 4-bit rep.
0101
1010
0110
1100
1011
10110
3/26/2016
CS 112 – Foundations of Computer Science
32
Addition and Subtraction
So is there any concern?
Yes – no matter how many bits you use there is some
maximum and some minimum number that can be
represented.
For four bits those are +7 and -8 respectively.
5 + 6 = 11 and -6 + (-4) = -10 are beyond a 4-bit rep.
0101
1010
0110
1100
1011
10110
two positives added to
a negative
3/26/2016
CS 112 – Foundations of Computer Science
33
Addition and Subtraction
So is there any concern?
Yes – no matter how many bits you use there is some
maximum and some minimum number that can be
represented.
For four bits those are +7 and -8 respectively.
5 + 6 = 11 and -6 + (-4) = -10 are beyond a 4-bit rep.
0101
1010
0110
1100
1011
10110
two negatives added to
a positive
3/26/2016
CS 112 – Foundations of Computer Science
34
Addition and Subtraction
So is there any concern?
Yes – no matter how many bits you use there is some
maximum and some minimum number that can be
represented.
For four bits those are +7 and -8 respectively.
5 + 6 = 11 and -6 + (-4) = -10 are beyond a 4-bit rep.
0101
1010
0110
1100
1011
10110
Both cases are called overflow.
3/26/2016
CS 112 – Foundations of Computer Science
35
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there
is no overflow interpret your answer in decimal form. Numbers
are listed in 2's complement.
1001
0101
0011
0110
0111
0011
1111
1000
1010
0011
1001
- 0101
0011
- 0110
0111
- 0011
1111
- 1000
1010
- 0011
3/26/2016
CS 112 – Foundations of Computer Science
36
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001
- 0101
3/26/2016
0011
0110
0111
0011
1111
1000
1010
0011
0011
- 0110
0111
- 0011
1111
- 1001
1010
- 0011
CS 112 – Foundations of Computer Science
37
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001
- 0101
3/26/2016
0011(3)
0110(6)
1001(X)
0011
- 0110
0111
0011
1111
1000
1010
0011
0111
- 0011
1111
- 1001
1010
- 0011
CS 112 – Foundations of Computer Science
38
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001
- 0101
3/26/2016
0011(3)
0110(6)
1001(X)
0011
- 0110
0111(7)
0011(3)
1010(X)
0111
- 0011
1111
1000
1010
0011
1111
- 1001
1010
- 0011
CS 112 – Foundations of Computer Science
39
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001
- 0101
3/26/2016
0011(3)
0110(6)
1001(X)
0011
- 0110
0111(7)
0011(3)
1010(X)
0111
- 0011
1111(-1)
1000(-8)
10111(X)
1111
- 1001
CS 112 – Foundations of Computer Science
1010
0011
1010
- 0011
40
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001
- 0101
3/26/2016
0011(3)
0110(6)
1001(X)
0011
- 0110
0111(7)
0011(3)
1010(X)
0111
- 0011
1111(-1)
1000(-8)
10111(X)
1111
- 1001
CS 112 – Foundations of Computer Science
1010(-6)
0011(3)
1101(-3)
1010
- 0011
41
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
1001(-7)
1011(-5)
10011(X)
3/26/2016
0011(3)
0110(6)
1001(X)
0011
- 0110
0111(7)
0011(3)
1010(X)
0111
- 0011
1111(-1)
1000(-8)
10111(X)
1111
- 1001
CS 112 – Foundations of Computer Science
1010(-6)
0011(3)
1101(-3)
1010
- 0011
42
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
0011(3)
0110(6)
1001(X)
1001(-7)
1011(-5)
10011(X)
0011(3)
1010(-6)
1101(-3)
3/26/2016
0111(7)
0011(3)
1010(X)
0111
- 0011
1111(-1)
1000(-8)
10111(X)
1111
- 1001
CS 112 – Foundations of Computer Science
1010(-6)
0011(3)
1101(-3)
1010
- 0011
43
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
0011(3)
0110(6)
1001(X)
0111(7)
0011(3)
1010(X)
1001(-7)
1011(-5)
10011(X)
0011(3)
1010(-6)
1101(-3)
0111(7)
1101(-3)
10100(4)
3/26/2016
1111(-1)
1000(-8)
10111(X)
1111
- 1001
CS 112 – Foundations of Computer Science
1010(-6)
0011(3)
1101(-3)
1010
- 0011
44
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
0011(3)
0110(6)
1001(X)
0111(7)
0011(3)
1010(X)
1111(-1)
1000(-8)
10111(X)
1001(-7)
1011(-5)
10011(X)
0011(3)
1010(-6)
1101(-3)
0111(7)
1101(-3)
10100(4)
1111(-1)
0111(7)
10110(6)
3/26/2016
CS 112 – Foundations of Computer Science
1010(-6)
0011(3)
1101(-3)
1010
- 0011
45
Addition and Subtraction
Carry out the following – if there is overflow indicate that – if there is
no overflow interpret your answer in decimal form. Numbers are
listed in 2's complement.
1001(-7)
0101(5)
1110(-2)
0011(3)
0110(6)
1001(X)
0111(7)
0011(3)
1010(X)
1111(-1)
1000(-8)
10111(X)
1010(-6)
0011(3)
1101(-3)
1001(-7)
1011(-5)
10011(X)
0011(3)
1010(-6)
1101(-3)
0111(7)
1101(-3)
10100(4)
1111(-1)
0111(7)
10110(6)
1010(-6)
1101(-3)
10111(X)
3/26/2016
CS 112 – Foundations of Computer Science
46