2008年12月30日 星期二

Network(一)---Topology

電腦網絡分硬體與軟體

分散式網絡=中央電腦具備計算功能的電腦.其他外部電腦只能叫終端機(terminal),非一台具備獨立功能的電腦,因為這些終端機並不能進行運算,只把資料透過線路傳送到中央電腦上.等待中央電腦進行處理,處理完畢後的結果,再透過線路,傳回送終端機.


client/server架構=每一台電腦都有獨立處理,儲存資料的能力.


Network Topology


Bus Network Topology=把多台電腦連接到單一通訊媒體上網路連線上.











優點:
成本低,不需集線器或交換器等等,網路連線耗材較少.

缺點:
1.電腦數量上升,網路傳輸衝突大增,傳輸效能會下降.
2.當某一網路線中斷時,由於訊號反射影響,整個網路的通訊都會中斷.


Star Network Topology

Star Network Topology=把所有電腦連接到一個中央裝置(集線器,交換器,路由器)所組成的Topology結構.








優點:

1.中央裝置型以方便網絡管理,限制節點存取.
2.中央節點外的連線故障只會影響使用該連線的電腦,不會影響網路其他電腦.
3.只要中央裝置支援,不同目的地通訊可以同時進行.


缺點:
1.較BUS貴,另行購置中央裝置,所需的網路連線較長.
2.中央節點發生故障,整個網路就不能通訊.


Ring Topology


Ring Topology=透過網路媒首尾連接,組成的一個環狀網路.









優點:

1.單向傳輸的特點,可用光纖做為媒介.
2.不會產生傳輸衝突,在高負荷下保持較高的網路傳輸效能.

缺點:
1.任一節點出現故障,整個網路傳輸都會中斷.
2.增加或減少網路內的電腦時,需要中斷網路.


Mesh Topology


Mesh Topology=每一個節點與多個節點.



優點:
1.網路有最大的重疊性,某一節點或連線故障,不會影響網路正常通訊.
缺點:
1.需要大量網路連線,建置成本較高.
2.傳輸資料時需要進行路由選徑操作,需要設定路由表或路由器才能通訊.

2008年12月29日 星期一

Maths(四)---Probability and Statistics(9)

Standard Normal Distribution
例一.
Given Z is the normal distribution with μ = 0 and σ2 = 1, i.e. Z ~ N(0, 1), findthe following probabilities using the standard normal table.

(a) P(Z ≤ 1.25)
(b) P( Z >. 2.33)
(c) P(0.5 <. Z <. 1.5)
(d) P(Z <. -1.25)
(e) P(-1.5 <. Z <. -0.5)

Solution
(a) P(Z ≤ 1.25) = 0.8943

(b) P(Z > 2.33) = 1 – Φ(2.33) = 1 – 0.9901 = 0.0099

(c)P(0.5 <. Z <. 1.5) = Φ(1.5) – Φ(0.5)

= 0.9332 – 0.6915
= 0.2417


(d) P( Z <. -1.25) = P(z >. 1.25)= 1 – Φ(1.25)= 1 – 0.8944= 0.1056

(e)P(-1.5 <. Z <. -0.5) = P(0.5 <. Z <. 1.5) = 0.2417

例二.
Given Z is the normal distribution with μ = 0 and σ2 = 1, i.e. Z ~ N(0, 1), findthe value of c if
(a) P(Z ≤ c) = 0.8888
(b) P( Z > c) = 0.37
(c) P(Z <. c) = 0.025
(d) P(0 ≤ Z ≤ c) = 0.4924

Solution
(a) Φ(c) = 0.8888
c = 1.22

(b) 1 − Φ(c) = 0.37
Φ(c) = 0.63
c = 0.34

(c) Obviously c is negative and the standard normal table cannot be used directly.Recall that P(Z < -z) = P(Z > z) .
∴ 0.025 = P(Z <. c) = P(Z >. -c) = 1 – Φ(-c)
i.e. Φ(-c) = 0.975
-c = 1.96
c = -1.96

(d) P(0 ≤ Z ≤ c) = Φ(c) – 0.5 = 0.4924
Φ(c) = 0.992
c = 2.43

Standardization of Normal Random Variables
例一.


Suppose X ~ N(10, 6.25).
Find the following probabilities
(a) P(X <. 13)

(b) P(X > 5)
(c) P(8 <. X <. 15)


Solution

Let Z =(X -10)/2.5

(a) P(X <. 13) = P(Z <(13−10)/2.5)= P(Z <.1.2) = 0.8849

(b)P(X > 5) = P(Z >(5 −10)/2.5)= P(Z > -2) = P(Z <.2) = 0.9773

(c) P(8 <.X <.15)=P((8-10)/2.5<.Z<.(15-10)/2.5) = P(-0.8 <.Z <.2) = Φ(2) – Φ(-0.8) = Φ(2) – (1 – Φ(0.8))
= 0.9772 – (1 – 0.7881)
= 0.7653

例二.
The lifetime of light bulbs produced in a certain factory is normally distributed withmean 3000 hours and standard deviation 50 hours. Find the probability that arandomly chosen light bulb has a lifetime less than 2900 hours.

Solution
Let X be the lifetime of a randomly chosen light bulb. Then X ~ N(3000, 502).
Let Z =(X − 3000)/50
P(X <.2900) = P(Z <.-2) = 1 – 0.9772 = 0.0228



例三. If a random variable has the normal distribution with μ = 40 and σ = 2.4, find theprobabilities that it will take a value (a) less than 43.6 (b) greater than 38.2 (c) between 40.6 and 43.0 (d) between 35.8 and 44.2. Solution Let X be the random variable.


(a) P(X <.43.6) = P(Z <.(43.6− 40)/2.4)= P(Z <.1.5) = 0.9332



(b) P(X > 38.2) = P(Z >(38.2 − 40)/2.4) = P(Z > -0.75) = P(Z <.0.75) = 0.7734


(c) P(40.6 <.X <.43.0) = P((40.6 -40)/2.4<.Z<.(43.0-40)/2.4)

= P(0.25 <.Z <.1.25)

= 0.2957

(d)P(35.8 <.X <.44.2) = P((35.8-40)/2.4<.z<.(44.2-40)/2.4)

= P(-1.75 <.Z <.1.75)

= 0.9198








Maths(四)---Probability and Statistics(8)

Poisson Distribution

The probability distribution for a Poisson random variable X iS



例一.


A manufacturer of a certain type of LCD-screen finds that the number of “deadspots” on a screen is a Po(0.8) random variable. A screen with more than 3 “deadspots” has to be sold at a discount. Find the proportion of screens that are sold at a discount.


Solution

Let X be the number of “dead spots” on a screen. Then X ~ Po(0.8).

The proportion of screens that are sold at a discount
= P( X > 3)
= 1 – p(0) – p(1) – p(2) – p(3)







= 0.00908


例二.
A radio active source is emitting α-particles at an average of 2.6 particles per minute.Find the probability that the number of particles emitted in one minute is

(a) 0

(b) 1

(c) more than 1

Solution

Let X be the number of particles emitted in one minute.







(c) P(X > 1) = 1 – 0.0743 – 0.193 = 0.7327


Poisson Approximation to Binomial Distribution

A rule of thumb for the conditions under which this approximation may be used is

n ≥ 100, np <>

例一.

A company ships memory chips in boxes of 200. It is known that 0.001 of all thechips are defective. Find the probability that less than 3 chips in a box aredefective.

Solution
Let X be the number of defective chips in a box. Then X ~ Bin(200, 0.001).The average number of defective chips in a box = 200 × 0.001 = 0.2The distribution of X may be approximated by Po(0.2).


2008年12月28日 星期日

Maths(四)---Probability and Statistics(7)

The Probability Distribution of a Binomial Random Variable

例一.

A fair coin is tossed 8 times. Find the probability of obtaining 5 heads

Solution


Let X be the number of heads obtained in 8 tosses.Then X~Bin(8,1/2)






例二.


There are 10 multiple-choice questions in a test and each question has 5 options.Suppose a student answers all 10 questions by randomly picking an option in eachquestion.


Find the probability that(a) he will answer six questions correctly,(b) he will get at least 3 correct answers.

Solution
Let X be the number of correct answers he will get.Then X ~ Bin(10, 0.2).











例三.


Binary digits 0 and 1 are transmitted along a data channel in which the presence ofnoise results in the fact that each digit may be wrongly received with a probabilty of0.00002. Each message is transmitted in blocks of 2000 digits.

(a) What is the probabilty that at least one digit in a block is wrongly received?

(b) If a certain message has a length of 20 blocks, find the probability that 2 ormore blocks are wrongly received.
Solution

(a) Then X ~ Bin(2000, 0.00002).




(b) Then Y~ Bin(20, 0.0392).



2008年12月27日 星期六

Maths(四)---Probability and Statistics(6)

Expected Value

例一.
The random variable X has the distribution shown below







Solution

The expected value of X = E(X) = 1 × 0.3 + 2 × 0.2 + 3 × 0.4 + 4 × 0.1 = 2.3

例二.

The random variable X a probability distribution given by

P(X = x) =c/x ,where x = 1, 2, 3, 4, 5.


(a) Find c.

(b) Find E(X)

Solution

(a) c(1+1/2+1/3+1/4+1/5)=1
c =60/137

(b) E(X) =1× c + 2 ×c/2+3×c/3+4×c/4+5×c/5=5c=300/13

例三.

In a game, a player tosses 3 fair coins. He wins $10 if 3 heads occur, $5 if 2heads occur, $2 if only 1 head occurs and losses $15 if no heads occur. What ishis expected gain?

Solution

His expected gain =10×1/8+5×3/8+2×3/8-15×1/8=2(dollars)

Function of a Random Variable

例一.

A salesman is employed by a computer manufacturer to sell PC’s. The salary hegets in a day is calculated by the formulag(x) = 90 + 60xwhere x is the number of PC’s he sells in that day.

Assume that in each day he may sell zero to four PC’s with probabilities listed inthe table below:








Let X be the number of PC’s sold in a day.
His expected daily salary is


E[g(X)] = g(0) p(0) + g(1) p(1) + g(2) p(2) + g(3) p(3) +g(4) p(4)
= (90)(0.05) + (90+60)(0.2) + (90+120)(0.4) + (90+180)(0.2)+ (90+240)(0.15)= 222 (dollars)


E(aX + b) = aE(X) + b .
expected daily salary=
E(90+60X)= 90 + 60E(X)= 90 + 60[(0)(0.05) + (1)(0.2) + + (2)(0.4) + (3)(0.2) + (4)(0.15)]= 222 (dollars)

Variance of a Random Variable

例一.

The probability distribution of the random variable X is shown below:









Find E(X) and V(X).


Solution

E(X) =1(0.1) + 2(0.5) + 3(0.4) = 2.3

V(X) = (1− 2.3)2 (0.1) + (2 − 2.3)2 (0.5) + (3 − 2.3)2 (0.4)= 0.41


例二.

Daily sales records for a shop selling electric appliances show that it will sell zero,one, two or three air-conditioners with the probabilities:


Solution
Expected value = (0)(0.5) + (1)(0.3) + (2)(0.15) + (3)(0.05)= 0.75
Variance= (0 – 0.75)2(0.5) + (1 – 0.75)2(0.3) + (2 – 0.75)2(0.15) + (3 – 0.75)2(0.05)= 0.7875
Standard deviation = 0.7875 = 0.8874

2008年12月26日 星期五

Maths(四)---Probability and Statistics(5)

Exhaustive Events

例一.

Two fair coins are tossed. A is the event that at least one tail is obtained

(a) Describe an event B such that A and B are exhaustive events only.

(b) Describe an event C such that A and C are both mutually exclusive andexhaustive.

Solution
(a)The possibility space S = {HH, HT, TH, TT} and the event A = {HT, TH, TT}.Let B be the event that at least one head is obtained, then B = {HH, HT, TH}.Since A ∪ B = {HH, HT, TH, TT} = S, A and B are exhaustive events.

(b)Let C be the event that no tail is obtained, then C = {HH}. Since A ∪ C ={HH, HT, TH, TT} = S and A ∩ C = φ, A and C are both mutuallyexclusive and exhaustive.

例二.
A and B are two events such that P( A ) =2/3 , P( B ) =2/5 and P( A ∩ B ) =1/15 .Are A and B exhaustive events?

Solution
2/3+2/5-1/15=1,A and B areexhaustive.

例三.
In a class of 40 students all study at least one of the subjects computer science anddiscrete mathematics. 27 attend the computer science class and 32 attend thediscrete mathematics class. Find the probability that a student chosen at randomstudies both computer science and discrete mathematics

Solution
40 = 27 + 32 − n( C ∩ M )
n( C ∩ M ) = 19
Therefore the probability that a student chosen at random studies both computer science and discrete mathematics is P( C ∩ M ) =19/40 .



Random Variables

例一.
Suppose 3 fair coins are tossed. The sample space of this experiment can be written as
S = {HHH, HHT, HTH, THH, HTT, THT, TTH, TTT}

Let the random variable X be the number of tails facing upwards. Then
X(HHH) = 0

X(HHT) = X(HTH) = X(THH) = 1

X(HTT) = X(THT) = X(TTH) = 2

X(TTT) = 3

The range space R = {0, 1, 2, 3}.


Probability Distributions

P(X = x) is often written as p(x).
p(0) = P(X = 0) = P(HHH) =1/8
p(1) = P(X = 1) = P(HHT, HTH, THH) =3/8
p(2) = P(X = 2) = P(HTT, THT, TTH) =3/8
p(3) = P(X = 3) = P(TTT)=1/8


例二.
Suppose two fair dice are tossed. Let the random variable X be the total score onthe two dices. The range space isR = {2, 3, 4, …, 12}.

The probability distribution of X is









例三.

A salesman visits 3 customers A, B and C to sell a product. The probabilities thatA, B and C will order the product are 0.2, 0.3 and 0.5 respectively. Let X be thenumber of customers that will order the product. Find the probability distributionof X.

Solution:

Let A, B and C be the events that customer A, B and C will order the product.

P(X = 0) = P(-A-B-C ) = (1 – 0.2)(1 – 0.3)(1 – 0.5) = 0.28

P(X = 1) = P(A-B-C or -AB-C or -A-BC)= (0.2)(0.7)(0.5) + (0.8)(0.3)(0.5) + (0.8)(0.7)(0.5)= 0.47

P(X = 2) = P(AB-C or A-BC or -ABC)= (0.2)(0.3)(0.5) + (0.2)(0.7)(0.5) + (0.8)(0.3)(0.5)= 0.22
P(X = 3) = P(ABC) = (0.2)(0.3)(0.5) = 0.03

例四.

In a test paper, there are five true-or-false questions. Two marks are awarded foreach correct answer and one mark is deducted for each wrong answer. Suppose astudent answers each question by choosing T or F randomly and let X be the totalmarks he gets.

Solution

The sample space can be wriiten asS = {WWWWW, WWWWC, WWWCW, …, CCCCC}where, for example, the outcome WWWWC means that the first 4 answers arewrong and the fifth answer is correct


Number of outcomes in S = 25 = 32Number of outcomes with k C’s = 5Ck , with k = 0, 1, 2, 3, 4, 5Obviously X = 2k – (5 – k) where k is the number of correct answers. The rangespace of X is R = {-5, -2, 1, 4, 7, 10}.


2008年12月25日 星期四

Maths(四)---Probability and Statistics(4)

Complementary Events

例一.
A sequence of 8 bits is randomly generated. What is the probability that at least one of these bits is 1?

Solution
Hence, the probability that the bit string will contain at least one 1 bit is 255/256 .

The Probability of Union
例一.
In a class of 40 students, 6 out of 15 boys and 13 out of 25 girls wear glass. Whatis the probability that a student chosen at random from the class is a boy or someonewho wears glasses?

Solution
15/40+19/40-6/40=28/40=7/40

例二.
What is the probability that a positive integer selected at random from the set of positive integers from 1 to 60 inclusive is divisible by either 3 or 4?

Solution
20/60+15/60-5/60=30/60=1/2

Mutually Exclusive Events

例一.
Suppose that there are eight runners in a race including John, David and Albert.The probability that John wins the race is 1/2 . David wins the race is 1/4 and Albertwins the race is 1/8. Assume there are no dead heats, find the probability that (a)John or David or Albert wins, (b) neither John nor David wins.

Solution
(a)1/2+1/4 + 1/8=7/8

(b)1-{1/2+1/4}=1/4


例二.
A card is drawn at random from an ordinary pack of 52 playing cards. Find theprobability that the card is (a) a heart or a club, (b) a red card or a club, (c) a redcard or a king.

Solution
(a)13/52+13/52=1/2
(b)26/52+13/52=3/4
(c)26/52+4/52-2/52=7/13

2008年12月24日 星期三

Maths(四)---Probability and Statistics(3)

Combinations

An r-combination of elements of a set is an unordered selection of r elements fromthe set. Thus, an r-combination is simply a subset of the set with r elements

例一.
Find the number of combinations of choosing three letters from the five letters A, B,C, D, E.

Solution
Therefore C(5, 3) =10

例二.
How many different ways are there to select two class representatives from a classof 20 students?

Solution
The number of such combinations is C(20, 2) =190.

例三.
In how many ways can a hand of 5 cards be dealt from an ordinary pack of 52playing cards?

Solution
Therefore the number of ways is C(52, 5) = 2,598,960.

例四.
A committee of 5 members is chosen at random from 6 faculty members of themathematics department and 8 faculty members of the computer science department.In how many ways can the committee be chosen if (a) there are no restrictions; (b)there must be more faculty members of the computer science department than thefaculty members of the mathematics department?

Solution
(a)So the number of ways of choosing thecommittee is C(14, 5) = 2002.

(b)
If there are to be more faculty members of the computer science departmentthan the faculty members of the mathematics department, then the followingconditions must be fulfilled.
(i)The number of ways of choosing is C(8, 5) = 56.

(ii)The number of ways of choosing is C(8, 4) × C(6, 1) = 70 × 6 =420.

(iii)The number of ways of choosing is C(8, 3) × C(6, 2) = 56 × 15 = 840
Therefore the total number of ways of choosing the committee is 56 + 420+ 840 = 1316.


2008年12月23日 星期二

Maths(四)---Probability and Statistics(2)

Arrangements
例一.
Find the number of ways of arranging the letters A, B and C.

Solution
3 × 2 × 1 = 3! = 6.
The arrangements are ABC, ACB, BCA, BAC, CAB and CBA.

例二.
It is known that the password on a computer system contain the three letters A, Band C followed by the six digits 1, 2, 3, 4, 5, 6. Find the number of possiblepasswords.

Solution
Therefore the total number of possible passwords is 3! × 6!= 4320, i.e. 4320 different passwords can be formed.


例三.
Find the number of ways of arranging the letters A, B and B.

Solution
Therefore the number of arranging the 3 letters, of which 2 are alike, is3!/ 2!=3

例四.
Find the number of ways that the letters of the word STATISTICS can be arranged.

Solution
Therefore the number of ways is 10!/3!3!2 =50400
That is, there are 50400 ways of arranging the letter in the word STATISTICS.

例五.
A six-digit number is formed from the digits 1, 1, 2, 2, 2, 5 and repetitions are notallowed. How many these six-digit numbers are divisible by 5?

Solution
Then, the required number is 5!/2!3! = 10
That is, there are 10 of these six-digit numbers are divisible by 5.


Permutations
A permutation of a set of distinct objects is an ordered arrangement of these objects.An ordered arrangement of r elements of a set is called an r-permutation

例一.
Find the number of ways of placing 3 of the letters A, B, C, D, E in 3 empty spaces.

Solution
P(5, 3) = 5 × 4 × 3 = 60.

例二.
How many different ways are there to select one chairman and one vice chairman from a class of 20 students?

Solution
This is P(20, 2) = 20 × 19 = 380.

例三.

There are ten runners in a race and suppose that they have equal chance to win therace. The champion receives a gold medal, the runners-up receives a silver medal,and the second runners-up receives a bronze medal. How many different ways arethere to award these medals?

Hence, there are P(10, 3) = 10 × 9 × 8 = 720 possibleways to award the medals.

2008年12月22日 星期一

Maths(四)---Probability and Statistics(1)

The Sum Rule

例一.
A number is chosen from the set of integers from 1 to 20 inclusive. If it is either an odd number or a multiple of 4, find the number of ways to choose this number.

Solution
from the sum rule there are 10 + 5 = 15 possible ways tochoose this number.

例二.
A customer can choose a mobile phone number from one of four lists. The fourlists contain 24, 15, 32 and 10 possible numbers, respectively. How many possiblenumbers are there to choose from?

Solution
Hence, there are 24 + 15 + 32 + 10 = 81 numbers to choosefrom.

例三.
A card is drawn at random from an ordinary pack of 52 playing cards. Find the number of ways that the card is a diamond or a heart.

Solution
Let S be the set of the pack of 52 cards, D be the set of diamond cards and H be the set of heart cards
13 + 13 = 26
The Product Rule

例一.
The seats in a mass lecture hall are to be labeled with a letter and a positive integernot greater than 10. How many seats can be labeled differently?

Solution
By the product rule, there are 26 × 10 = 260 ways to label a seat.Therefore, 260 seats can be labeled differently

例二.
A password on a computer system consists of six characters. Each of thesecharacters must be a digit. How many passwords are there?

SolutionEach of the six characters can be chosen in 10 ways, since each digit is from 0 to 9.Therefore, by the product rule, there are 106 = 1,000,000 different passwords.

例三.
Suppose the name of a variable in a computer language can be either a single letteror a letter followed by a digit. Find the number of possible names

Solution
26 + 260 = 286.

The Inclusion-Exclusion Principle

例一.
Count the number of bit strings of length ten which begin with a 1010 or end with a 00.

Solution
64 + 256 – 16 = 304, i.e. there is 304 number of bit stringsof length ten begin with a 1010 or end with a 00.

例二.
In a class of 40 students, 25 students take computer science and 30 students takeadditional mathematics. All the 40 students must take at least one of these subjects.How many students take both subjects?

Solution
C ∪ A  =  C  +  A  - C ∩ A 
40 = 25 + 30 - C ∩ A 
C ∩ A  = 15
i.e. 15 students take both subjects.

2008年12月21日 星期日

Maths(三)---Graphs and Trees(7)

Minimum Spanning Tree

Let T be a spanning tree of minimum total weight in a connected weighted graph G.Then T is a minimum spanning tree of G.


















































































2008年12月20日 星期六

Maths(三)---Graphs and Trees(6)

Let G be a simple graph with n vertices, where n ≥ 3.

deg v + deg w ≥ n,


for each pair of non-adjacent vertices v and w, then G is Hamiltonian.













For figure 3.32, n = 5 but deg u = 2, so Dirac’s theorem does not apply.However, deg v + deg w ≥ 5 for all pairs of non-adjacent vertices v and w, so thisgraph is Hamiltonian by Ore’s theorem.

............................................................................................

Trees


A tree is a connected graph which contains no cycles.


􀂅 T is connected and has n − 1 edges.


􀂅 T has n − 1 edges and contains no cycles.


􀂅 T is connected and each edge is a bridge.


􀂅 Any two vertices of T are connected by exactly one path.


􀂅 T contains on cycles, but the addition of any new edges creates exactly onecycle.


Spanning Trees


Let G be a connected graph. A spanning tree in G is a subgraph of G that includesall the vertices of G and is also a tree. The edges of the tree are called branches.



2008年12月19日 星期五

Maths(三)---Graphs and Trees(5)

Eulerian Graphs

A connected graph G is Eulerian if there is a closed path which includes every edgeof G; such path is called an Eulerian path.












Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree.


例一.
















Which graph(s) is/are Eulerian?


Answer: Graph (a) and (b) are Eulerian


Hamiltonian Graphs

A connected graph G is Hamiltonian if there is a cycle which includes every vertexof G; such a cycle is called a Hamiltonian cycle













Let G be a simple graph with n vertices, where n ≥ 3. If deg v ≥ 21 n for eachvertex v, then G is Hamiltonian.

For the above graph, n = 6 and deg v = 3 for each vertex v, so this graph isHamitonian by Dirac’s theorem.