计数

本文主要学习计数的基本原理和第一定理。通过赌数引入了计数的概念。学习了计数方法和密码学计数。运用包括了和规则、乘积法则等的概念模型来讨论计数的应用。
展开查看详情

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

19.FINIS 3/22/12 19