Transcript Discrete Systems I

Discrete Systems I
Lecture 00
Number Systems and Counting
Profs. Koike and Yukita
Preparations for Lesson 00
• Number systems 数の表現法
• The decimal system (base 10 number system)
10進法
• Sumerians and Babylonians developed a base
60 number system.  現代に生きている
2
Preparation Task 1
この講義では以下のよ うな記法を用いる。
25610  100000000 2
は10進法で 256と表される数は 2進法で100000000と表される
数と同じであることを
言っている。右下につ いている
添え字 (suffix) は何進法であるかを表 す。これは底 (base)と
呼ばれる。
Fill in the blanks below.
(1) 10 7 
10
(2) 1010 
7
(3) 5010 
7
3
Preparation Task 2
Base 16 では数字 (digit )が0から 9まででは足りないので 10から 15までを
A, B, C, D, E, F で表すことにしよう。
Fill in the blanks below.
(1) 10016 
(2) FF16 
(3) 25610 
10
10
16
4
The Decimal System
The number 608 has three digit positions (numeral slots).
The 100s position contains "6."
The 10s position contains "0."
The ones position contains "8."
The total value is
(6  100)  (0 10)  (8  1)  608.
6
100s
0
10s
8
1s
10 2
101
100
Position 2
The most significan t digit
Position 1
Position 0

The least significan t digit
5
Base 7
Base 10
0
1
2
3
4
5
6
7
8
Base 7
0
1
2
3
4
5
6
10
11
9
10
11
12
13
14

14
15
20
21

49
100

343
1000
6
Converting from base 7 to base 10
(4  7 )  (6  7 )  (2  7 )  (5  7 )  1685
3
4
3
7
6
2
7
343 49
2
1
0
2 5
1
0
7 7
7
1
7
Converting from
base 10 to base 7
We introduce unknowns xi .
  ( x3  7 3 )  ( x2  7 2 )  ( x1  71 )  ( x0  7 0 )  1685
If we divide 1685 by 7, the quotient (商) is
  ( x3  7 2 )  ( x2  71 )  ( x1  7 0 )  240
and the remainder( 余り ) is x0  5.
If we divide 240 by 7, the quotient) is
  ( x4  7 2 )  ( x3  71 )  ( x2  7 0 )  34
and the remainder is x1  2.
If we divide 34 by 7, the quotient is
  ( x5  7 2 )  ( x4  71 )  ( x3  7 0 )  4
and the remainder is x2  6.
If we divide 4 by 7, the quotient is
  ( x6  7 2 )  ( x5  71 )  ( x4  7 0 )  0
and the remainder is x3  4. Thus, we have
46257  1685
8
Base 16
Hexadecimal
Base 10
0
1
2
Base 16
0
1
2

9
10
11
12
13
9
A
B
C
D
14
15
16
E
F
10

32
33
20
21

255
FF

4092
1000
9
Base 2
Binary
Base 10
Base 2
0
0
1
1
2
10

31
11111
32
100000

256
100000000
10
Exercise 0.2 A. Count from one to 2010
in the following bases.
1.
2.
3.
4.
5.
8
6
5
3
2
(octal, 8進法)
(binary)
11
Exercise 0.2 B. Convert the following
numbers to their base 10 equivalences.
6.
7.
8.
9.
10.
11.
12.
13.
31247
123324
153669
40005
71228
778
3334
1111112
12
Exercise 0.2 C. Convert the following
base 10 numbers to the indicated base.
14.
15.
16.
17.
18.
41310 to base 5
12810 to base 8
300010 to base 6
96310 to base 3
6710 to base 2
13
Exercise 0.2 D. Perform the indicated
base conversion.
19. 548 to base 5
20. 3124 to base 7
21. 5206 to base 7
22. 122123 to base 9
23. 1008 to base 2
24. What generalizations can you draw about
converting a number from one base to a
power of that base, e.g., from base 3 to 9
(32) or from base 2 to base 8 (23)?
14
Addition in various bases
Carrying (繰り上がり ) in base 4
1
3 2 1 1 3
 1 1 3 2 3

3 2 1 1 3
 1 1 3 2 3
2
1 1
3 2 1 1 3
 1 1 3 2 3
0 2

1 1 1 1 1

3 2 1 1 3
 1 1 3 2 3
1 1 0 1 0 2
15
Exercise 0.3 A. Perform the following
additions in the indicated bases. Check
your work in base 10.
1.
2.
3.
4.
5.
6.
168+58
245+1325
5246+3126
7139+2389
4426+1156
2556+3336
16
The Binary Number System
Applied to Combinatoric Problems
1. U.S. Presidential Election
2. Pizza
3. Hypercube
4. Binary Trees
17
U.S. Presidential Election
Given that in a presidential election, each state in the United
States votes Democrat or Republican, how many different ways
could all 50 states vote?
Assign one bit to each state in order, and let each state’s bit be
0 if that state votes Democrat, and 1 if it votes Republican.
Then the entire country may be thought of as one big 50-bit
binary number, and there are 250 (read as “two to fifty”)
different combinations of state-level outcomes in a national
election.
18
Pizza
If you were at a pizza parlor that sold one size of pizza and
seven toppings were available (mushroom, sausage,
pepperoni, onion, pepper, anchovies, and extra cheese), how
many different kinds of pizza could you order?
Let us reserve one bit for each topping, seven bits in all.
We can represent any particular kind of pizza by a seven-bit
binary number, in which each topping’s bit tells us whether
that topping is present on the pizza (1=topping is on the pizza,
0=topping is off the pizza).
There are as many different kinds of pizza as there are
combinations of seven bits, or 27=100000002=12810.
19
Hypercube
An n - dimensiona l hypercube is represente d by a product
[0,1]  [0,1]    [0,1],
where [0,1] means a closed interval on a real number line.
Computer scientists often replace the interval with {0,1},
obtaining a dicrete hypercube.
Any point in the n - dimensiona l hypercube is represente d as
an n - bit binary number.
20
Binary Trees
root node
level 0
level 1
level 2
level 3
leaf nodes
21
Exercise 0.5
1. How many combinations of heads and tails are possible if a
coin is flipped seven times? How many combinations if it is
flipped n times?
2. If a given radioactive substance has a half-life of one year,
then each year that passes leaves the substance half as
radioactive as it had been a year before and twice as
radioactive as it will be one year hence. Rounded up to the
nearest year, after how many years would such a substance
be one three-hundredth as radioactive as it was to begin
with? How long would it take for such a substance to lose all
of its radioactivity?
3. How many combinations of options are possible on a car
that has 37 optional features?
22
This lecture is based on the following
book.
Ones and Zeros – Understanding Boolean Algebra, Digital
Circuits, and the Logic of Sets,
J.R.Gregg,
IEEE Press.
23