展开查看详情
1 .Counting First Principles 3/22/12 1
2 .Counting in Gambling What fraction of poker hands are “a pair of Jacks?” ( probability of a pair of Jacks) 3/22/12 2
3 .# ops to update a data structure (# comparisons needed to sort n items) # steps in a computation (# multiplies to compute d n ) Counting in Algorithms 3/22/12 3
4 .Counting in Cryptography # possible passwords # possible keys lec 10W. 4 3/22/12
5 .Sum Rule If sets A and B are disjoint , then | A ∪ B | = | A | + | B | A B 3/22/12 5
6 .lec 10W. 6 The Sum Rule Class has 17 women, 25 men so total enrollment = 17 + 25 = 42 26 lower case letters, 26 upper case letters, and 10 digits, so # characters = 26+26+10 = 62 3/22/12
7 .If there are 4 men and 3 women, there are 4 ⋅ 3 = 12 different man/woman couples The Product Rule 3/22/12 7
8 .Product Rule If | A | = m and | B | = n , then | A × B | = m ⋅ n A = { a, b, c, d }, B = { 1, 2, 3 } A × B = {( a , 1 ) ,( a , 2 ) ,( a , 3 ), ( b , 1 ) ,( b ,2 ),( b , 3 ), ( c , 1 ) ,( c , 2 ) ,( c , 3 ), ( d , 1 ) ,( d , 2 ) ,( d , 3 ) } 3/22/12 8
9 .Product Rule: Counting Strings # length- 4 binary strings = | B × B × B × B | = | B 4 | where B ::= { 0 , 1 } = 2 · 2 · 2 · 2 = 2 4 3/22/12 9
10 .Product Rule: Counting Strings # length n strings from an alphabet of size m is m n 3/22/12 10
11 .Example: Counting Passwords characters are digits & letters between 6 & 8 characters long starts with a letter case sensitive Password conditions: 3/22/12 11
12 .L ::= { a,b , … , z,A,B , … ,Z} D ::= {0,1, …… ,9} P n ::= length n words starting w/letter = L × (L ∪ D) n-1 Counting Passwords 3/22/12 12
13 .|L × (L ∪ D) n-1 | = |L| · |(L ∪ D)| n-1 = |L| · (|L| + |D|) n-1 = 52 · (5 2+10) n-1 Counting Passwords 3/22/12 13
14 .Counting Passwords set of passwords : P ::= P 6 ∪ P 7 ∪ P 8 | P | = |P 6 |+| P 7 | +| P 8 | = 52 · (62 5 +62 6 +62 7 ) ≈ 19 · 10 14 3/22/12 14
15 .cases by 1st occurrence of 7 : x : any digit o : any digit ≠ 7 7 xxx or o 7 xx or oo 7 x or ooo 7 10 3 = 3439 # 4 -digit nums w / ≥ one 7 + 9 · 10 2 + 9 2 · 10 + 9 3 3/22/12 15
16 .at least one 7 : another way | 4 -digit nums w/ ≥ one 7 | = | 4 -digit nums | − | those w/ no 7 | = 10 4 − 9 4 = 3439 3/22/12 16
17 .Cracking Passwords by Exhaustive Search Suppose a password has to be a string of letters and digits beginning with a letter So there are 52∙ 62 n-1 passwords of length n Suppose a computer can try a password every billionth of a second (one nanosecond per try) How big does n have to be for it to take more than a day to try them all? 3/22/12 17
18 .More than a day: 52∙ 62 n-1 > number of nanoseconds in a day = 24∙60∙60∙10 9 62 n-1 > 1.66∙10 12 n -1 > log (1.66∙10 12 )/log 62 ≈ 6.8 So if passwords are at least 8 characters long it would take more than a day to try them all by exhaustive search. 3/22/12 18
热门城市
