A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees

Chapter31Michelle Bodnar,Andrew LohrApril12,2016Exercise31.1-1By the given equation,we can write c=1·a+b,with0≥b<a.By the definition of remainders given just below the division theorem,this means that b is the remainder when c is divided by a,that is b=c mod a.Exercise31.1-2Suppose that there are onlyfinitely many primes p1,p2,...,p k.Then p= p1p2···p k+1isn’t prime,so there must be some p i which divides it.However, p i·(p1···p i−1p i+1···p k)<p and p·(p1···p i−1p i+1···p k+1)>p,so p i can’t divide p.Since this holds for any choice of i,we obtain a contradiction.Thus, there are infinitely many primes.Exercise31.1-3a|b means there exists k1∈Z so that k1a=b.b|c means there exists k2∈Z so that k2b=c.This means that(k1k2)a=c.Since the integers are a ring, k1k2∈Z,so,we have that a|c.Exercise31.1-4Let g=gcd(k,p).Then g|k and g|p.Since p is prime,g=p or g=1.Since 0<k<p,g<p.Thus,g=1.Exercise31.1-5By Theorem31.2,since gcd(a,n)=1,there exist integers p,q so that pa+qn=1,so,bpa+bqn=b.Since n|ab,there exists an integer k so that kn=ab.This means that knp+pqn=(k+q)pn=b.Since n divides the left hand side,it must divide the right hand side as well.Exercise31.1-61Observe that p k =p !k !(p −k )!=p (p −1)···(p −k +1)k !.Let q =(p −1)(p −2)···(p −k +1).Since p is prime,k !|p .However,we know that p k is an integer becauseit is also a counting formula.Thus,k !divides pq .By Corollary 31.5,k !|q .Write q =ck !.Then we have p k =pc ,which is divisible by p .By the binomial theorem and the fact that p | p k for 0<k <p ,(a +b )p =p k =0p k a k b p −k ≡a p +b p (mod p ).Exercise 31.1-7First,suppose that x =yb +(x mod b ),(x mod b )=za +((x mod b )mod a ),and ka =b .Then,we have x =yka +(x mod b )=(yk +z )a +((x mod b )mod a ).So,we have that x mod a =((x mod b )mod a ).For the second part of the problem,suppose that x mod b =y mod b .Then,by the first half of the problem,applied first to x and then to b,x mod a =(x mod b )mod a =(y mod b )mod a =y mod a .So,x ≡y mod a .Exercise 31.1-8We can test in time polynomial in βwhether or not a given β-bit number is a perfect k th power.Then,since two to the βth power is longer than the number we are given,we only need to test values of k between 2and β,thereby keeping the runtime polynomial in β.To check whether a given number n is a perfect k th power,we will be using a binary search like technique.That is,if we want to find the k-th root of a number,we initially know that it lies somewhere between 0and the number itself.We then look at the number of the current range of number under con-sideration,raise it to the k th power in time polynomial in β.We can do this by the method of repeated squaring discussed in section 31.6.Then,if we get a number larger than the given number when we perform repeated squaring,we know that the true k th root is in the lower half of the range in consideration,if it is equal,it is the midpoint,if larger,it is the upper half.Since each time,we are cutting down the range by a factor of two,and it is initially a range of length Θ(2β),the number of times that we need to raise a number the the k th power is Θ(β).Putting it all together,with the O (β3)time exponentiation,we get that the total runtime of this procedure is O (β5).Exercise 31.1-9For (31.6),we see that a and b in theorem 31.2which provides a characteri-zation of gcd appear symmetrically,so swapping the two won’t change anything.For (31.7),theorem 31.2tells us that gcd’s are defined in terms of integer linear combinations.If we had some integer linear combination involving a and2b,we can changed that into one involving(-a)and b by replacing the multiplier of a with its negation.For(31.8),by repeatedly applying(31.6)and(31.7),we can get this equality for all four possible cases based on the signs of both a and b.For(31.9),consider all integer linear combinations of a and0,the thing we multiply by will not affect thefinal linear combination,so,really we are just taking the set of all integer multiples of a andfinding the smallest element. We can never decrease the absolute value of a by multiplying by an integer (|ka|=|k||a|),so,the smallest element is just what is obtained by multiplying by1,which is|a|.For(31.10),again consider possible integer linear combinations na+mka, we can rewrite this as(n+km)a,so it has absolute value|n+km||a|.Since the first factor is an integer,we can’t have it with a value less than1and still have a positivefinal answer,this means that the smallest element is when thefirst factor is1,which is achievable by setting n=1,m=0.Exercise31.1-10Consider the prime factorization of each of a,b,and c,written as a= p1p2...p k where we allow repeats of primes.The gcd of b and c is just the product of all p i such that p i appears in both factorizations.If it appears multi-ple times,we include it as many times as it appears on the side with the fewest occurrences of p i.(Explicitly,see equation31.13on page934).To get the gcd of gcd(b,c)and a,we do this again.Thus,the left hand side is just equal to the intersection(with appropriate multiplicities)of the products of prime factors of a,b,and c.For the right hand side,we consider intersectingfirst the prime factors of a and b,and then the prime factors of c,but since intersections are associative,so is the gcd operator.Exercise31.1-11Suppose to a contradiction that we had two different prime decomposition. First,we know that the set of primes they both consist of are equal,because if there were any prime p in the symmetric difference,p would divide one of them but not the other.Suppose they are given by(e1,e2,...,e r)and(f1,f2,...,f r) and suppose that e i<f i for some position.Then,we either have that p e i+1i divides a or not.If it does,then the decomposition corresponding to{e i}is wrong because it doesn’t have enough factors of p i,otherwise,the one corre-sponding to{f i}is wrong because it has too many.Exercise31.1-12Standard long division runs in O(β2),and one can easily read offthe re-mainder term at the end.3Exercise 31.1-13First,we bump up the length of the original number until it is a power of two,this will not affect the asymptotics,and we just imagine padding it with zeroes on the most significant side,so it does not change its value as a number.We split the input binary integer,and split it into two segments,a less significant half and an more significant half m ,so that the input is equal to m 2β/2+ .Then,we recursively convert m and to decimal.Also,since we’ll need it later,we compute the decimal versions of all the values of 22i up to 2β.There are only lg(β)of these numbers,so,the straightforward approach only takes time O (lg 2(β))so will be overshadowed by the rest of the algorithm.Once we’ve done that,we evaluate m 2β/2+ ,which involves computing the product of two numbers and adding two numbers,so,we have the recurrenceT (β)=2T (β/2)+M (β/2)Since we have trouble separating M from linear by a n for some epsilon,the analysis gets easier if we just forget about the fact that the difficulty of the multiplication is going down in the subcases,this concession gets us the runtime that T (β)∈O (M (β)lg(β))by master theorem.Note that there is also a procedure to convert from binary to decimal that only takes time Θ(β),instead of the given algorithm which is Θ(M (β)lg(β))∈Ω(βlg(β))that is rooted in automata theory.We can construct a deterministic finite transducer between the two languages,then,since we only need to take as many steps as there are bits in the input,the runtime will be linear.We would have states to keep track of the carryover from each digit to the next.Exercise 31.2-1First,we show that the expression given in equation (31.13)is a common divisor.To see that we just notice thata =(r i =1p e i −min(e i ,f i )i )r i =1p min(e i ,f i )i andb =(r i =1p f i −min(e i ,f i )i )ri =1p min(e i ,f i )i Since none of the exponents showing up are negative,everything in sight is an integer.Now,we show that there is no larger common divisor.We will do this by showing that for each prime,the power can be no higher.Suppose we had some common divisor d of a and b .First note that d cannot have a prime factor that doesn’t appear in both a or b ,otherwise any integer times d would also have that factor,but being a common divisor means that we can write both a and b as an integer times d .So,there is some sequence {g i }so that d = r i =1p gi i .4Now,we claim that for every i,g i≤min(e i,f i).Suppose to a contradiction that there was some i so that g i>min(e i,f i).This means that d either has more factors of p i than a or than b.However,multiplying integers can’t cause the number of factors of each prime to decrease,so this is a contradiction,since we are claiming that d is a common divisor.Since the power of each prime in d is less than or equal to the power of each prime in c,we must have that d≤c. So,c is a GCD.Exercise31.2-2We’ll create a table similar to that offigure31.1:a b a/b d x y899493129-6114934061295-640687429-1587581291-1582922901290-2910Thus,(d,x,y)=(29,−6,11).Exercise31.2-3Let c be such that a=cn+(a mod n).If k=0,it is trivial,so suppose k< 0.Then,EUCLID(a+kn,n)goes to line3,so returns EUCLID(n,a mod n). Similarly,EUCLID(a,n)=EUCLID((a mod n)+cn,n)=EUCLID(n,a mod n).So,by correctness of the Euclidean algorithm,gcd(a+kn,n)=EUCLID(a+kn,n)=EUCLID(n,a mod n)=EUCLID(a,n)=gcd(a,n)Exercise31.2-4Algorithm1ITERATIVE-EUCLID(a,b)1:while b>0do2:(a,b)=(b,a mod b)3:end while4:return aExercise31.2-5We know that for all k,if b<F k+1<φk+1/√5,then it takes fewer than ksteps.If we let k=logφb+1,then,since b<φlogφb+2/√5=φ2√5·b,we havethat it only takes1+logφ(b)steps.5We can improve this bound to1+logφ(b/gcd(a,b)).This is because we knowthat the algorithm will terminate when it reaches gcd(a,b).We will emulate the proof of lemma31.10to show a slightly different claim that Euclid’s algorithm takes k recursive calls,then a≥gcd(a,b)F k+2and b≥gcd(a,b)F k+!.We will similarly do induction on k.If it takes one recursive call,and we have a>b,we have a≥2gcd(a,b)and b=gcd(a,b).Now,suppose it holds for k−1,we want to show it holds for k.Thefirst call that is made is of EUCLID(b,a mod b).Since this then only needsk−1recursive calls,we can apply the inductive hypothesis to get that b≥gcd(a,b)F k+1and a mod b≥gcd(a,b)F k.Since we had that a>b,we havethat a≥b+(a mod b)≥gcd(a,b)(F k+1+F k)=gcd(a,b)F k+2completing the induction.Since we have that we only need k steps so long as b<gcd(a,b)F k+1<gcd(a,b)φk+1.we have that logφ(b/gcd(a,b))<k+1.This is satisfied if we setk=1+logφ(b/gcd(a,b))Exercise31.2-6Since F k+1mod F k=F k−1we have gcd(F k+1,F k)=gcd(F k,F k−1).Sincegcd(2,1)=1we have that gcd(F k+1,F k)=1for all k.Moreover,since F k is increasing,we have F k+1/F k =1for all k.When we reach the base case ofthe recursive calls to EXTENDED-EUCLID,we return(1,1,0).The following returns are given by(d,x,y)=(d ,y ,x −y ).We will show that in general, EXTENDED-EUCLID(F k+1,F k)returns(1,(−1)k+1F k−2,(−1)k F k−1).We have already shown d is correct,and handled the base case.Now suppose the claim holds for k−1.Then EXTENDED-EUCLID(F k+1,F k)returns(d ,y ,x −y ) where d =1,y =(−1)k−1F k−2,x =(−1)k F k−3,so the algorithm returns(1,(−1)k−1F k−2,(−1)k F k−3−(−1)k−1F k−2)=(1,(−1)k+1F k−2,(−1)k(F k−3+F k−2)=(1,(−1)k+1F k−2,(−1)k F k−1) as desired.Exercise31.2-7To show it is independent of the order of its arguments,we prove the fol-lowing swap property,for all a,b,c,gcd(a,gcd(b,c))=gcd(b,gcd(a,c)).By applying these swaps in some order,we can obtain an arbitrary ordering on the variables(the permutation group is generated by the set of adjacent transposi-tions).Let a i be the power of the i th prime in the prime factor decompositionof a,similarly define b i and c i.Then,we have that6gcd(a,gcd(b,c))=i p min(a i,min(b i,c i)) i=i p min(a i,b i,c i) i=i p min(b i,min(a i,c i)) i=gcd(b,gcd(a,c))Tofind the integers{x i}as described in the problem,we use a similar approach as for EXTENDED-EUCLID.Exercise31.2-8From the gcd interpretation given in equation(31.13),it is clear that lcm(a1,a2)=a1·a2 gcd(a1,a2).More generally,lcm(a1,...,a n)=a1···a ngcd(···(gcd(gcd(a1,a2),a3),...),a n).Wecan compute the denominator recursively using the two-argument gcd opera-tion.The algorithm is given below,and runs in O(n)time.Algorithm2LCM(a1,...,a n)x=a1g=a1for i=2to n dox=x·a i)g=gcd(g,a i)end forreturn x/gExercise31.2-9For two numbers to be relatively prime,we need that the set of primes that occur in both of them are disjoint.Multiplying two numbers results in a number whose set of primes is the union of the two numbers multiplied. So,if we let p(n)denote the set of primes that divide n.By testing that gcd(n1n2,n3n4)=gcd(n1n3,n2n4)=1.We get that(p(n1)∪p(n2))∩(p(n3)∪(n4))=(p(n1)∪p(n3))∩(p(n2)∪(n4))=∅.Looking at thefirst equation,it gets us that p(n1)∩p(n3)=p(n1)∩p(n4)=p(n2)∩p(n3)=p(n2)∩p(n4)=∅.The second tells,among other things,that p(n1)∩p(n2)=p(n3)∩p(n4)=∅.This tells us that the sets of primes of any two elements are disjoint,so all elements are relatively prime.A way to view this that generalizes more nicely is to consider the complete graph on n vertices.Then,we select a partition of the vertices into two parts. Then,each of these parts corresponds to the product of all the numbers cor-responding to the vertices it contains.We then know that the numbers that7any pair of vertices that are in different parts of the partition correspond to will be relatively prime,because we can distribute the intersection across the union of all the prime sets in each partition.Since partitioning into two parts is equivalent to selecting a cut,the problem reduces to selecting lg(k)cuts of K n so that every edge is cut by one of the cuts.To do this,first cut the vertex set in as close to half as possible.Then,for each part,we recursively try to cut in in close to half,since the parts are disjoint,we can arbitrarily combine cuts on each of them into a single cut of the original graph.Since the number of time you need to divide n by two to get1is lg(n) ,we have that that is the number of times we need to take gcd.Exercise31.3-1+4012300123112302230133012·5123411234224133314244321Then,we can see that these are equivalent under the mappingα(0)=1,α(1)=3,α(2)=4,α(3)=2.Exercise31.3-2The subgroups of Z9and{0},{0,3,6},and Z9itself.The subgroups of Z∗13 are{1},{1,3,9},{1,3,4,9,10,12},{1,5,8,12},{1,12}and Z∗13itself. Exercise31.3-3Since S was afinite group,every element had afinite order,so,if a∈S , there is some number of times that you can add it to itself so that you get the identity,since adding any two things in S gets us something in S ,we have that S has the identity element.Associativity is for free because is is a property of the binary operation,no the space that the operation draws it’s arguments stly,we can see that it contains the inverse of every element,because we can just add the element to itself a number of times equal to one less than its order.Then,adding the element to that gets us the identity.Exercise31.3-48The only prime divisor of p e is p.From the definition of the Euler phi function,we haveφ(p e)=p e1−1p=p e−1(p−1).Exercise31.3-5To see this fact,we need to show that the given function is a bijection.Since the two sets have equal size,we only need to show that the function is onto. To see that it is onto,suppose we want an element that maps to x.Since Z∗n is afinite Abelian group by theorem31.13,we can take inverses,in particu-lar,there exists an element a−1so that aa−1=1mod n.This means that f a(a−1x)=aa−1x mod n=(aa−1mod n)(x mod n)=x mod n.Since we canfind an element that maps to any element of the range and the sizes of domain and range are the same,the function is a bijection.Any bijection from a set to itself is a permutation by definition.Exercise31.4-1First,we run extended Euclid on35,50and get the result(5,−7,10).Then, our initial solution is−7∗10/5=−14=36.Since d=5,we have four other solutions,corresponding to adding multiples of50/5=10.So,we also have that our entire solution set is x={6,16,26,36,46}.Exercise31.4-2If ax≡ay mod n then a(x−y)≡0mod n.Since gcd(a,n)=1,n doesn’t divide a unless n=1,in which case the claim is trivial.By Corollary31.5, since n divides a(x−y),n divides x−y.Thus,x≡y mod n.To see that the condition gcd(a,n)is necessary,let a=3,n=6,x=6,and y=2.Note that gcd(a,n)=gcd(3,6)=3.Then3·6≡3·2mod6,but6=2mod6.Exercise31.4-3it will work.It just changes the initial value,and so changes the order in which solutions are output by the program.Since the program outputs all val-ues of x that are congruent to x0mod n/b,if we shift the answer by a multiple of n/b by this modification,we will not be changing the set of solutions that the procedure outputs.Exercise31.4-4The claim is clear if a≡0since we can just factor out an x.For a=0, let g(x)=g0+g1x+...+g t−1x t−1.In order for f(x)to equal(x−a)g(x) we must have g0=f0(−a)−1,g i=(f i−g i−1)(−a)−1for1≤i≤t−1and9g t −1=f t .Since p is prime,Z ∗p ={1,2,...,p −1}so every element,includ-ing −a ,has a multiplicative inverse.It is easy to satisfy each of these equa-tions as we go,until we reach the last two,at which point we need to satisfy both g t −1=(f t −1−g t −2)(−a )−1and g t −1=f t .More compactly,we need f t =(f t −1−g t −2)(−a )−1.We will show that this happens when a is a zero of f .First,we’ll proceed inductively to show that for 0≤k ≤t −1we have a k +1g k =− k i =0f i a i .For the base case we have ag 0=−f 0,which holds.Assume the claim holds for k −1.Then we havea k +1g k =a k +1(f k −g k −1)(−a )−1=−a k f k +a k g k −1=−a k f k −k −1 i =0f i a i =ki =0f i a iwhich completes the induction step.Now we show that we can satisfy the equation given above.It will suffice to show that −a t f t =a t −1(f t −1−g t −2).a t −1(f t −1−g t −2)=a t −1f t −1−a t −1g t −2=a t −1f t −1+t −2 i =0f i a i =t −1i =0f i a i =−a t f twhere the second equality is justified by our earlier claim and the last equality is justified because a is a zero of f .Thus,we can find such a g .It is clear that a polynomial of degree 1can have at most 1distinct zero modulo p since the equation x =−a has at most 1solution by Corollary 31.25.Now suppose the claim holds for t >1.Let f be a degree t +1polynomial.If f has no zeros then we’re done.Otherwise,let a be a zero of f .Write f (x )=(x −a )g (x ).Then by the induction hypothesis,since g is of degree t ,g has at most t distinct zeros modulo p .The zeros of f are a and the zeros of g ,so f has at most t +1distinct zeros modulo p .Exercise 31.5-110These equations can be viewed as a single equation in the ring Z +5×Z 11+,in particular (x 1,x 2)=(4,5).This means that x needs to be the element in Z 55+that corresponds to the element (4,5).To do this,we use the process de-scribed in the proof of Theorem 31.27.We have m 1=11,m 2=5,c 1=11(11−1mod 5)=11,c 2=5(5−1mod 11)=45.This means that the corresponding solution is x =11·4+45·5mod 55=44+225mod 55=269mod 55=49mod 55.So,all numbers of the form 49+55k are a solution.Exercise 31.5-2Since 9·8·7=504,we’ll be working mod 504.We also have m 1=56,m 2=63,and m 3=72.We compute c 1=56(5)=280,c 2=63(7)=441,and c 3=72(4)=288.Thus,a =280+2(441)+3(288)mod 504=10mod 504.Thus,the desired integers x are of the form x =10+504k for k ∈Z .Exercise 31.5-3Suppose that x ≡a −1mod n .Also,x i ≡x mod n i and a i ≡a mod n i .What we then want to show is that x i ≡a −1i mod n i .That is,we want that a i x i ≡1mod n i .To see this,we just use equation 31.30.To get that ax mod n corresponds to (a 1x 1mod n 1,...,a k x k mod n k ).This means that 1corresponds to (1mod n 1,...,1mod n k ).This is telling us exactly what we needed,in particular,that a i x i ≡1mod n i .Exercise 31.5-4Let f (x )=f 0+f 1x +...+f d x d .Using the correspondence of Theorem 31.27,f (x )≡0mod n if and only if d i =0f i j x i j ≡0mod n j for j =1to k .The product formula arises by constructing a zero of f via choosing x 1,x 2,...,x k such that f (x j )≡0mod n j for each j ,then letting x be the number associated to (x 1,...,x k ).Exercise 31.6-1elementorder 112103545556107108109510211The smallest primitive root is2,and has the following values for ind11,2(x)x ind11,2(x)1102138425469778396105Exercise31.6-2To perform modular exponentiation by examining bits from right to left, we’ll keep track of the value of a2i as we go.See below for an implementation:Algorithm3MODULAR-EXPONENTIATION-R-to-L(a,b,n)c=0d=1s=alet b k,b k−1,...,b0 be the binary representation of bfor i=0to k doif b i==1thend=s·d mod nc=2i+cend ifs=s·s mod nend forreturn dExercise31.6-3Since we knowφ(n),we know that aφ(n)≡1mod n by Euler’s theorem. This tells us that a−1=aφ(n)−1because aa−1=≡aaφ(n)−1≡aφ(n)≡1mod n. Since when we multiply this expression times a,we get the identity,it is the inverse of a.We can then compute nφ(n)efficiently,sinceφ(n)<n,so can be represented without using more bits than was used to represent n.Exercise31.7-1For the secret key’s value of e we compute the inverse of d=3modφ(n)= 280.To do this,wefirst computeφ(280)=φ(23)φ(7)φ(5)=4·6·4=96.Since12any number raised to this will be one mod280,we will raise it to one less than this.So,we compute395≡3(32)47≡3(9(92)23)≡3(9(81(812)11))≡3(9(81(121(1212)5)))≡3(9(81(121(81(812)2≡3·9·81·121·81·81≡3·9·121≡187mod280Now that we know our value of e,we compute the encryption of M=100 by computing100187mod319,which comes out to an encrypted message of122 Exercise31.7-2We know ed=1modφ(n).Since d<φ(n)and e=3,we have3d−1= k(p−1)(q−1)for k=1or2.We have k=1if3d−1<n and k=2if 3d−1>n.Once we’ve determined k,p+q=n−(3d−1)/k+1,so we can now solve for p+q in time polynomial inβ.Replacing q−1by(p+q)−p−1 in our earlier equation lets us solve for p in time polynomial inβsince we need only perform addition,multiplication,and division on numbers bounded by n. Exercise31.7-3P A(M1)P A(M2)≡M e1M e2≡(M1M2)e≡P A(M1M2)mod nSo,if the attacker can correctly decode1100of the encrypted messages,hedoes the following.If the message is one that he can decrypt,he is happy,de-crypts it and stops.If it is not one that he can decrypt,then,he picks a random element in Z m,say x encrypts it with the public key,and multiplies that by theencrypted text,he then has a1100chance to be able to decrypt the new message.He keeps doing this until he can decrypt it.The number of steps needed follows a geometric distribution with a expected value of100.Once he’s stumbled upon one that he could decrypt,he multiplies by the inverses of all the elements that he multiplied by along the way.This recovers thefinal answer,and also can be done efficiently,since for every x,x n−2is x−1by Lagrange’s theorem.13Exercise31.8-1Suppose that we can write n= ki=1p e ii,then,by the Chinese remainder the-orem,we have that Z n∼=Z p e11×···×Z p e11.Since we had that n was not aprime power,we know that k≥2.This means that we can take the elementsx=(p e11−1,1,...,1)and y=(1,p e22−1,1,...,1).Since multiplication in theproduct ring is just coordinate wise,we have that the squares of both of theseelements is the all ones element in the product ring,which corresponds to1inZ n.Also,since the correspondence from the Chinese remainder theorem was a bijection,since x and y are distinct in the product ring,they correspond todistinct elements in Z n.Thus,by taking the elements corresponding to x and yunder the Chinese remainder theorem bijection,we have that we have found twosquareroots of1that are not the identity in Z n.Since there is only one trivialnon-identity squareroot in Z n,one of the two must be non-trivial.It turns outthat both are non-trivial,but that’s more than the problem is asking. Exercise31.8-2Let c=gcd(···(gcd(gcd(φ(p e11),φ(p e22)),φ(p e33)),...),φ(p e r r)).Then we haveλ(n)=φ(e e11)···φ(p e r r)/c=φ(n)/c.Since the lcm is an integer,λ(n)|φ(n).Suppose p is prime and p2|n.Sinceφ(p2)=p2(1−1p )=p2−p=p(p−1),we have that p must divideλ(n).however,since p divides n,it cannot divide n−1,so we cannot haveλ(n)|n−1.Now,suppose that is the product of fewer than3primes,that is n=pq for some two distinct primes p<q.Since both p and q were primes,λ(n)= lcm(φ(p),φ(q))=lcm(p−1,q−1).So,mod q−1,λ(n)≡0,however,since n−1=pq−1=(q−1)(p)+p−1,we have that n−1≡p−1mod q−1. Sinceλ(n)has a factor of q−1that n−1does not,meaning thatλ(n)|n−1.Exercise31.8-3First,we prove the following lemma.For any integers a,b,n,gcd(a,n)·gcd(b,n)≥gcd(ab,n).Let{p i}be an enumeration of the primes,then,by Theorem31.8,there is exactly one set of powers of these primes so that a=i p a ii,b=ip b ii,and n=ip n ii.gcd(a,n)=ip min(a i,n i)igcd(b,n)=ip min(b i,n i)igcd(ab,n)=ip min(a i+b i,n i)i14We combine thefirst two equations to get:gcd(a,n)·gcd(b,n)=ip min(a i,n i)i·ip min(b i,n i)i=i p min(a i,n i)+min(b i,n i) i≥i p min(a i+b i,n i) i=gcd(ab,n)Since x is a non-trivial squareroot,we have that x2≡1mod n,but x=1 and x=n−1.Now,we consider the value of gcd(x2−1,n).By theorem31.9, this is equal to gcd(n,x2−1mod n)=gcd(n,1−1)=gcd(n,0)=n.So,we can then look at the factorization of x2−1=(x+1)(x−1)to get thatgcd(x+1,n)gcd(x−1,n)≥nHowever,we know that since x is a nontrivial squareroot,we know that 1<x<n−1so,neither of the factors on the right can be equal to n.This means that both of the factors on the right must be nontrivial.Exercise31.9-1The Pollard-Rho algorithm wouldfirst detect the factor of73when it con-siders the element84,when we have x12because we then notice that gcd(814−84,1387)=73.Exercise31.9-2Create an array A of length n.For each x i,if x i=j,store i in A[j].If j is thefirst position of A which must have its entry rewritten,set t to be the entry originally stored in that spot.Then count how many additional x i’s must be computed until x i=j again.This is the value of u.The running time isΘ(t+u).Exercise31.9-3Assuming that p e divides n,by the same analysis as sin the chapter,it will take timeΘ(p e/2).To see this,we look at what is happening to the sequence mod p n.15x i +1=x i +1mod p e =f n (x i )mod p e=((x 2−1)mod n )mod p e =(x 2−1)mod p e=(x i )2−1mod p e =f p e (x i )So,we again are having the birthday paradox going on,but,instead of hop-ing for a repeat from a set of size p ,we are looking at all the equivalence classes mod p e which has size p e ,so,we have that the expected number of steps be-fore gettinga repeat in that size set is just the squareroot of its size,which is Θ(√p e )=Θ(p e/2).Exercise 31.9-4Problem 31-1a.If a and b are both even,then we can write them as a =2(a/2)and b =2(b/2)where both factors in each are integers.This means that,by Corollary 31.4,gcd(a,b )=2gcd(a/2,b/2).b.If a is odd,and b is even,then we can write b =2(b/2),where b/2is an integer,so,since we know that 2does not divide a ,the factor of two that is in b cannot be part of the gcd of the two numbers.This means that we have gcd(a,b )=gcd(a,b/2).More formally,suppose that d =gcd(a,b ).Since d is a common divisor,it must divide a ,and so,it must not have any even factors.This means that it also divides a and b/2.This means that gcd(a,b )≤gcd(a,b/2).To see the reverse,suppose that d =gcd(a,b/2),then it is also a divisor of a and b ,since we can just double whatever we need to multiply it by to get b/2.Since we have inequalities both ways,we have equality.c.If a and b are both odd,then,first,in analoge to theorem 31.9,we show that gcd(a,b )=gcd(a −b,b ).Let d and d be the gcd’s on the left and right respectively.Then,we have that there exists n 1,n 2so that n 1a +n 2b =d ,but then,we can rewrite to get n 1(a −b )+(n 1+n 2)b =d .This getsus d ≥d .To see the reverse,let n 1,n 2so that n 1(a −b )+n 2b =d .We rewrite to get n 1a +(n 2−n 1)b =d ,so we have d ≥d .This meansthat gcd(a,b )=gcd(a −b,b )=gcd(b,a −b ).From there,we fall into the case of part b.This is because the first argument is odd,and the second is the difference of two odd numbers,hence is even.This means we can halve the second argument without changing the quantity.So,gcd(a,b )=gcd(b,(a −b )/2)=gcd((a −b )/2,b ).16。

前二章作业1.计算机的四个基本功能（Functions）是什么？2.在计算机的top-level structure view中，四个structural components 是什么？3.谁提出了store-program concept ?你能用汉语简单地描述这个存储程序的概念吗？4.CPU的英文全称是什么？汉语意义是什么？5.ALU的英文全称是什么？汉语意义是什么？6.V on Neumann 的IAS机的五大部件都是什么？7.在第一章中我们认识到的四个结构性部件（第2题）与V on Neumann的IAS机（第6题）中部件有本质差别吗？8.Fundamental Computer Elements 有哪几个？它们与计算机的四个基本功能的关系是什么？9.Moore’s Law在中文翻译为什么？它描述了什么事物的一般规律？10.本书的次标题和第二章第二节标题均为“Designing forPerformance”,Performance 主要指什么？Performance Balance的（balance）平衡要平衡什么？11.本书作者将他要研究的范围局限在“desktop, workstation , server“中，它们的中文名称是什么？各自的工作范围是什么？Chapter 3Homework1.PC means _________.A. personal computerB. programming controllerC. program counterD. portable computer2. PC holds _______________ .A. address of next instructionB. next instructionC. address of operandD. operand3. At the end of fetch cycle, MAR holds _____.A. address of instructionB. instructionC. address of operandD. operand4. Interrupt process steps are __________.A. suspending , resuming , branching & processingB. branching , suspending , processing & resumingC. suspending , branching , processing & resumingD. processing , branching , resuming & suspending5. A unsigned binary number is n bits, so it is can represent a value in the range between _________ .A. 0 to n-1B. 1 to nC. 0 to 2n-1D. 1 to 2n6.The length of the address code is 32 bits, so addressing range (or the range of address) is ________________.A. 4GB.from –2G to 2GC.4G-1D. from 1 to 4G7.There are three kinds of BUSes. Which is not belong to them?A. address busB. system busC. data busD. control busQuestions1.Translate the following terms (Note: function)PC, MAR, MBR, IR, AC, bus, system bus, data bus , address bus , control bus , handler*, opcode, Bus arbitrate* , multiplexed bus* , interrupt, ISR, Instruction cycle , fetch cycle , execute cycle(带“*”为选做题)2.Page90 problems3.1What general categories of functions are specified by computer instruction?3. Describe simply the operations of PC and IR in an instruction cycle.4.Suppose the length of word is n-bit, describe simply operand(操作数) format and instruction format.5. Describe simply the procedure of the interruption6. Describe simply the types and functions of the BUS.一：选择题1.The computer memory system refers to _________A.RAMB.ROMC.Main memoryD.Register , main memory, cache, external memory2.If the word of memory is 16 bits, which the following answer is right ?A.The address width is 16 bitsB.The address width is related with 16 bitsC.The address width is not related with 16 bitsD.The address width is not less than 16 bits3.The characteristics of internal memory compared to external memoryA.Big capacity, high speed, low costB.Big capacity, low speed, high costC.small capacity, high speed, high costD.small capacity, high speed, low cost4．On address mapping of cache, any block of main memory can be mapped toany line of cache, it is ___________ .A) Associative Mapping B) Direct MappingC) Set Associative Mapping D) Random Mapping5. Cache’s write-through polity means write operation to main memory _______.A)as well as to cacheB)only when the cache is replacedC)when the difference between cache and main memory is foundD)only when direct mapping is used6.Cache’s write-back polity means write operation to main memory ______________.a)as well as to cacheb)only when the relative cache is replacedc)when the difference between cache and main memory is foundd)only when using direct mapping7. On address mapping of cache, the data in any block of main memory can be mapped to fixed line of cache, it is _________________.associative mapping B) direct mappingC)set associative mapping D) random mapping8.On address mapping of cache, the data in any block of main memory can be mapped to fixed set any line(way) of cache, it is _________________.associative mapping B) direct mappingD)set associative mapping D) random mapping二：计算题(from page 126)Problem 4.1 , Problem 4.3 , Problem 4.4 , Problem 4.5 , , Problem 4.7, Problem 4.10第五章作业1.which type of memory is volatile?A.ROMB. E2PROMC. RAMD. flash memory2.which type of memory has 6-transistor structure?A. DRAMB. SRAMC. ROMD. EPROMing hamming code, its purpose is of one-bit error.A. detecting and correctingB. detectingC. correctingD. none of all4.Flash memory is .A. read-only memoryB. read-mostly memoryC. read-write memoryD. volatile5.Which answer about internal memory is not true?A. RAM can be accessed at any time, but data would be lost when power down..B. When accessing RAM, access time is non-relation with storage location.C. In internal memory, data can’t be modified.D. Each addressable location has a unique address.Page161 Problems: 5.4 5.5 5.6 5.7 5.8第六章作业一、选择题1. RAID levels_________make use of an independent access technique.A. 2B. 3C. 4D. all2. In RAID 4, to calculate the new parity, involves _________reads.A. oneB. twoC. threeD.four3. During a read/write operation, the head is ___________A. movingB. stationaryC. rotatingD. above all4. On a movable head system, the time it takes to position the head at the track is know as______.A. seek timeB. rotational delayC. access timeD. transfer time5. RAID makes use of stored______information that enable the recovery of data lost due to a disk failure.A. parityB. user dataC. OSD. anyone6. Recording and retrieval via _________called a headA. conductive coilB. aluminiumC. glassD. Magnetic field7.In Winchester disk track format, _________is a unique identifier or address used to locate a particular sector.A. SYNCHB. GapC. ID fieldD. Data field8. Data are transferred to and from the disk in ________.A. trackB. sectorC. gapD. cylinder9. In _________, each logical strip is mapped to two separate physical disk.A. RAID 1B. RAID 2C. RAID 3D. RAID 410. With _________, the bits of an error correcting code are stored in the corresponding bit position on multiple parity disk.A. RAID 1B. RAID 2C. RAID 3D. RAID 411. The write-once read-many CD, known as ________.A. CD-ROMB. CD-RC. CD-R/WD. DVD二、How are data written onto a magnetic disk?三、In the context of RAID, what is the distinction between parallel access and independent access?Homework in Chapter 71.“When the CPU issues a command to the I/O module, it must wait until the I/Ooperation is complete”. It is programmed I/O , the word “wait”means ___________________.a. the CPU stops and does nothingb. the CPU does something elsec. the CPU periodically reads & checks the status of I/O moduled. the CPU wait the Interrupt Request Signal2.See Figure 7.7. To save (PSW & PC) and remainder onto stack, why theoperations of restore them is reversed? Because the operations of stack are ________________.a. first in first outb. randomc. last in first outd. sequenceding stack to save PC and remainder, the reason is ____________________ .a.some information needed for resuming the current program at the point ofinterruptb.when interrupt occurs, the instruction is not executed over, so the instructionat the point of interrupt must be executed once againc.the stack must get some information for LIFOd.the start address of ISR must transfer by stack4.The signals of interrupt request and acknowledgement exchange between CPUand requesting I/O module. The reason of CPU’s acknowledgement is ________________a.to let the I/O module remove request signalb. to let CPU get the vectorfrom data busc.both a & bd. other aims5.In DMA , the DMA module takes over the operations of data transferring fromCPU, it means _________________________a.the DMA module can fetch and execute instructions like CPU doesb.the DMA module can control the bus to transfer data to or from memoryusing stealing cycle techniquec.the DMA module and CPU work together(co-operate) to transfer data into orfrom memoryd.when DMA module get ready, it issues interrupt request signal to CPU forgetting interrupt service6.Transfer data with I/O modules, 3 types of techniques can be used. Which one isnot belong them?a. Interrupt-driven I/Ob. programmed I/Oc. direct I/O accessd. DMA7.Think 2 types of different data transferring, to input a word from keyboard and tooutput a data block of some sectors to harddisk. The best choice is to use ___________.a. interrupt-driven I/O and DMAb. DMA and programmed I/O C. both interrupt-driven I/Os d. both DMAsparing with interrupt-driven I/O, DMA further raises the usage rate of CPUoperations, because __________a. it isn’t necessary for CPU to save & restore sceneb. it isn’t necessary for CPU to intervene the dada transferc. it isn’t necessary for CPU to read & check status repeatedlyd. both a and b9.Simply script the all actions when using Interrupt-driven I/O technique totransferring data with I/O module.(please insert the “vector “at step3 & step5)10.See Figure 7.7 & 7.8. Redraw figure 7.8, and mark the sequence numberaccording to Figure 7.7, to indicate the sequence of the information flowing.11. According to DMA technique, write all information of CPU sending to DMA module, and write at which time the DMA module issues interrupt request signal to CPU and why the INTR is issued ?.Chapter9 homework1.Suppose bit long of two’s complement is 5 bits, which arithmetic operation brings OVERFLOW?A. 5+8B. (-8)+(-8)C. 4-(-12)D.15-72.Overflow occurs sometime in ______arithmetic operation.A. addB. subtractC. add and subtractD. multiply3. In twos complement, two positive integers are added, when does overflow occurs?A. There is a carryB. Sign bit is 1C. There is a carry, and sign bit is 0D. Can’t determine4. An 8-bit twos complement 1001 0011 is changed to a 16-bit that equal to____.A.1000 0000 1001 0011B. 0000 0000 1001 0011C.1111 1111 1001 0011D.1111 1111 0110 1101 115. An 8-bit twos complement 0001 0011 is changed to a 16-bit that equal to____.A. 1000 0000 1001 0011B. 0000 0000 0001 0011C. 1111 1111 0001 0011D. 1111 1111 1110 11016.Booth’s algorithm is used for Twos complement ______.A. additionB. subtractionC. multiplicationD. division7. In floating-point arithmetic, addition can divide to 4 steps: ______.A. load first operand, add second operand, check overflow and store resultB. compare exponent, shift significand, add significands and normalizeC. fetch instruction, indirectly address operand, execute instruction and interruptD. process scheduling states: create, get ready, is running and is blocked8. In floating-point arithmetic, multiplication can divide to 4 steps: ______.A. load first operand, add second operand, check overflow and store resultB. fetch instruction, indirectly address operand, execute instruction and interruptC. process scheduling states: create, get ready, is running and is blockedD. check for zero, add exponents, multiply significands, normalize, and round.9.The main functions of ALU are?A. LogicB. ArithmeticC. Logic and arithmeticD. Only addition10. Which is true?A. Subtraction can not be finished by adder and complement circuits in ALUB. Carry and overflow are not sameC.In twos complement, the negation of an integer can be formed with thefollowing rules: bitwise not (excluding the sign bit), and add 1.D. In twos complement, addition is normal binary addition, but monitor sign bit foroverflowPage326：9.4, 9.5 and 9.7(其中9.4选作)To prove: in twos complement, sign-extension rule (converting between different bit length) and negation rule ( (-X)补= X补+ 1).Chapter 10 and Chapter 111: In instruction, the number of addresses is 0, the operand(s)’address is implied, which is(are) in_______.A. accumulatorB. program counterC. top of stackD. any register2: Which the following addressing mode can achieve the target of branch in program?A.Direct addressing modeB.Register addressing modeC.Base-register addressing modeD.Relative addressing mode （有问题）3: In index-register addressing mode , the address of operand is equal toA.The content of base-register plus displacementB.The content of index-register plus displacementC.The content of program counter plus displacementD.The content of AC plus displacement4: The address of operand is in the instruction, it is_________ ?A.Direct addressing modeB.Register indirect addressing modeC.Stack addressing modeD.Displacement addressing mode5: Which the following is not the area that the source and result operands can be stored in ?A.Main or virtual memoryB.CPU registerC.I/O deviceD.Instruction6: Compared with indirect addressing mode , the advantage of register indirect addressing mode isrge address spaceB.Multiple memory referenceC.Limit address spaceD.Less memory access7:With base-register ADDRESSING , the ______________ register can be used.A. BASEB. INDEXC. PCD. ANY8:The disadvantage of INDIRECT ADDRESSING is ____________.A. large addressing rangeB. no memory accessC. more memory accessD. large value range9:Which is not an advantage with REGISTER INDIRECT?A. just one times of operand’s accessB. large memory spaceC. large value rangeD. no memory reference10:The REGISTER ADDRESSING is very fast, but it has _________________.A. very less value rangeB. very less address spaceC. more memory accessD. very complex address’ calculating11:The disadvantage of IMMEDIATE ADDRESSING is ___________.A. limited address rangeB. more memory accessC. limit value rangeD. less memory access12:In instruction, the number of addresses is 2, one address does double duty both _______________.A. a result and the address of next instructionB.an operand and a resultC.an operand and the address of next instructionD.two closed operands13.In instruction, the number of addresses is 3, which are _______________.A. two operands and one resultB. two operands and an address of next instructionC. one operand, one result and an address of next instructionD. two operands and an address of next instruction14.The address is known as a type of data, because it is represented by __________.A. a number of floating pointB. a signed integerC. an unsigned integerD. a number of hexadecimal15.Which is not a feature of Pentium .A. complex and flex addressingB. abundant instruction setC. simple format and fixed instruction lengthD. strong support to high language16. Which is not a feature of Power PC .A. less and simple addressing modeB. basic and simple instruction setC. variable instruction length and complex formatD. strong support to high languageChapter 12 and Chapter 181. After the information flow of fetch subcycle, the content of MBR is_____________.A.oprandB.address of instructionC. instructionD. address of operand2. After the information flow of instruction subcycle, the content of MBR is_____________.A.oprandB.address of instructionC. instructionD. address of operand3. The worse factor that limits the performance of instruction pipeline is _________________.A.conditional branch delaying the operation of target addressB. the stage number of pipeline c an’t exceed 6C. two’s complement arithmetic too complexD. general purpose registers too few4.The most factor to affect instruction pipeline effectiveness is __________.A. The number of stagesB. the number of instructionC. the conditional branch instructionD. the number of pipelines5. RISC rejects ______.A. few, simple addressing modesB. a limited and simple instruction setC. few, simple instruction formatsD. a few number of general purpose registers6. RISC rejects ______.A.a large number of general-purpose registersB. indirect addressingC. a single instruction sizeD. a small number of addressing mode7. Which is NOT a characteristic of RISC processor.A. a highly optimized pipeline.B. Register to registeroperationsC. a large number of general-purpose registersD. a complexed instructionformat8.Control unit use some input signals to produce control signals that open the gatesof information paths and let the micro-operations implement. Which is NOT the input signals of control unit/A.clock and flagsB.instruction registerC.interrupt request signalD.memory read or write9.Control unit use some output signals to cause some operations. Which is notincluded in the output signals?A.signals that cause data movementB.signals that a ctivate specific functions(e.g. add/sub/…)C.flagsD.read or write or acknowledgement10. Symmetric Multi-Processor (SMP) system is tightly coupled by _______.A. high-speed data-link and distributed memoryB. shared RAIDs and high-speed data-linkC. distributed caches and shared memoryD. interconnect network and distributed memory11. The SMP means __________.A.Sharing Memory ProcessesB.Split Memory to PartsD.Stack and Memory Pointer D.Symmetric Multi-Processo r12.The “MESI” means states of ____________ .A.Modified, Exclusive, Stored and InclusiveB.Modified, Expected, Shared and InterruptedC.Modified, Exclusive, Shared and InvalidD.Moved, Exchanged, Shared and Invalid13.The protocol “MESI” is also called __________.A. write back policyB. write-update protocolC. write-invalidate protocolD. write through policyChapter 121.Which register is user –visible but is not directly operated in 8086 ?A. DSB. SPC. IPD. BP2.The indirect sub-cycle is occurred _____________ ?A. before fetch sub-cycleB. after execute sub-cycleC. after interrupt sub-cycleD. after fetch sub-cycle and before execute sub-cycle3.Within indirect sub-cycle , the thing the CPU must do is ______________?A. fetch operand or store resultB. fetch operand’s address from memoryC. fetch next instruction from memoryD. nothing4.In general, which register is used for relative addressing ---- the content inthis register plus the A supplied by instruction to make a target address in branch or loop instructions.A. SPB. IRC. BRD. PC5.The Memory Address Register connects to ____________ BUS .A. systemB. addressC. dataD. control6.The Memory Buffer Register links to ________ BUS.A. systemB. addressC. dataD. control7.After Indirect cycle , there is a ______________ cycle .A. FetchB. IndirectC. ExecuteD. Interrupt8.The Interrupt cycle is __________ ______ Execute cycle .A. always afterB. never afterC. sometime afterD. maybe before9.The correct cycle sequence is _________________ .A. Fetch , Indirect , Execute and InterruptB. Fetch , Execute , Indirect and InterruptC. Fetch , Indirect , Interrupt and ExecuteD. Indirect , Fetch , Execute and Interrup10.The aim of the indirect cycle is to get __________________.A. an operandB. an instructionC. an address of an instructionD. an address of an operand11.Which is not in the ALU ?A. shifterB. adderC. complementerD. accumulator12.The registers in the CPU is divided _____registers and ________registers .A. general purpose , user-visibleB. user-visible , control and statusC. data , addressD. general purpose , control and status13.The Base register is a(n) __________ register in 8086.A. general purposeB. dataC. addressD. control14.The Instruction Pointer is a(n) __________ register in 8086.A. general purposeB. dataC. addressD. control15.The Index register is a(n) __________ register in 8086.A. general purposeB. dataC. addressD. control16.The Stack Pointer is a(n) __________ register in 8086.A. general purposeB. dataC. addressD. control17.The Accumulator is a(n) __________ register in 8086.A. general purposeB. dataC. addressD. control18.The Programming Status W ord is a(n) __________ register .A. general purposeB. dataC. addressD. controlShow all the micro-operations and control signals for the following instruction:1. ADD AX, X; —The contents of AC adds the contents of location X, result is stored to AC.2. MOV AX, [X];—Operand pointed by the content of location X is moved to AX, that means ((X))->AX—[ ] means indirect addressing.3. ADD AX, [BX];—Operand pointed by the content of Register BX is added to AX, that means (AX)+((BX))->AX—[ ] means register indirect addressing.4. JZ NEXT1; —If (ZF)=0,then jump to (PC)+ NEXT1.5. CALL X; —Call x function, save return address on the top of stack.6. RETURN; —From top of stack return to PC.。

计算机网络原理习题讲解精编版MQS system office room 【MQS16H-TTMS2A-MQSS8Q8-MQSH16898】ChapterI1. Whatisthedifferencebetweenahostandanendsystem??2. Whatisaclientprogram?Whatisaserverprogram?Doesaserverprogramrequesta ndreceiveservicesfromaclientprogram?3. ,companyaccess,ormobileaccess.4. Dial-upmodems,HFC,,providearangeoftransmissionratesandcommentonwhetherthe transmissionrateissharedordedicated.5. .6. Whatadvantagedoesacircuit-switchednetworkhaveoverapacket-switchednetwork?WhatadvantagesdoesTDMhaveoverFDMinacircuit-switchednetwork?7. 2,000km 8102⨯prop d trans d trans d t =prop d trans d trans d prop d trans d trans d 8105.2⨯=s prop d trans d 6108⨯下列说法中,正确的是()。

A.在较小范围内布置的一定是局域网,币在较大范围内布置的一定是广域网B.城域网是连接广域网而覆盖园区的网络C.城域网是为淘汰局域网和广域网而提出的一种网络技术D.局域网是基于广播技术发展起来的网络,广域网是基于交换技术发展起来的向络 解答:D 。

通常而言,局域网的覆盖范围较小,而广域网的覆盖范围较大,但这并不绝对。

有时候在一个不大的范围内采用广域网,这取决于应用的需要和是否采用单一网络等多种因素。

About the T utorialScala is a modern multi-paradigm programming language designed to express common programming patterns in a concise, elegant, and type-safe way. Scala has been created by Martin Odersky and he released the first version in 2003.Scala smoothly integrates the features of object-oriented and functional languages. This tutorial explains the basics of Scala in a simple and reader-friendly way.AudienceThis tutorial has been prepared for beginners to help them understand the basics of Scala in simple and easy steps. After completing this tutorial, you will find yourself at a moderate level of expertise in using Scala from where you can take yourself to next levels. PrerequisitesScala Programming is based on Java, so if you are aware of Java syntax, then it's pretty easy to learn Scala. Further if you do not have expertise in Java but if you know any other programming language like C, C++ or Python then it will also help in grasping Scala concepts very quickly.Disclaimer & Copyright© Copyright 2015 by Tutorials Point (I) Pvt. Ltd.All the content and graphics published in this e-book are the property of Tutorials Point (I) Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republish any contents or a part of contents of this e-book in any manner without written consent of the publisher.We strive to update the contents of our website and tutorials as timely and as precisely as possible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt. Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of our website or its contents including this tutorial. If you discover any errors on our website or inthistutorial,******************************************.iT able of ContentsAbout this Tutorial (i)Audience (i)Prerequisites (i)Disclaimer & Copyright (i)Table of Contents .................................................................................................................................. i i 1.SCALA – OVERVIEW (1)Scala vs Java (2)Scala Web Frameworks (2)2.SCALA – ENVIRONMENT (3)Step 1: Verify your Java Installation (3)Step 2: Set your Java Environment (4)Step 3: Install Scala (4)3.SCALA – BASICS (7)First Scala Program (7)Script Mode (8)Basic Syntax (9)Scala Identifiers (9)Scala Keywords (10)Comments in Scala (11)Blank Lines and Whitespace (11)Newline Characters (12)Scala Packages (12)Apply Dynamic (12)ii4.SCALA – DATA (14)Scala Basic Literals (14)Escape Sequences (16)5.SCALA – VARIABLES (18)Variable Declaration (18)Variable Data Types (18)Variable Type Inference (19)Multiple assignments (19)Example Program (19)Variable Scope (20)6.SCALA – CLASSES & OBJECTS (22)Basic Class (22)Extending a class (24)Implicit Classes (26)Singleton Objects (28)7.SCALA – ACCESS MODIFIERS (30)Private Members (30)Protected Members (30)Public Members (31)Scope of Protection (32)8.SCALA – OPERATORS (34)Arithmetic Operators (34)Relational Operators (35)Logical Operators (37)Bitwise Operators (39)iiiOperators Precedence in Scala (46)9.SCALA – IF ELSE STATEMENT (48)if Statement (48)If-else Statement (49)If-else-if-else Statement (50)Nested if-else Statement (52)10.SCALA – LOOP STATEMENTS (54)While loop (55)do-while loop (57)for Loop (59)Loop Control Statements (66)Break Statement (66)Breaking Nested Loops (68)The infinite Loop (70)11.SCALA – FUNCTIONS (72)Function Declarations (72)Function Definitions (72)Calling Functions (73)Function Call-by-Name (74)Function with Variable Arguments (75)Function Default parameter values (76)Nested Functions (77)Partially Applied Functions (78)Function with Named arguments (80)Recursion Functions (81)ivAnonymous Functions (83)Currying Functions (84)12.SCALA – CLOSURES (86)13.SCALA – STRINGS (88)Creating a String (88)String Length (89)Concatenating Strings (89)Creating Format Strings (90)String Interpolation (91)The ‘f’ Interpolator (92)String Methods (94)14.SCALA – ARRAYS (98)Declaring Array Variables (98)Processing Arrays (99)Multi-Dimensional Arrays (100)Concatenate Arrays (102)Create Array with Range (103)Scala Array Methods (104)15.SCALA – COLLECTIONS (106)Scala Lists (106)Creating Uniform Lists (109)Tabulating a Function (110)Scala List Methods (111)Scala Sets (114)vFind max, min elements in set (117)Find Common Values Insets (118)Scala Map [K, V] (122)Concatenating Maps (124)Print Keys and Values from a Map (125)Check for a key in Map (126)Scala Map Methods (127)Scala Tuples (131)Iterate over the Tuple (132)Converting to String (133)Scala Options (134)Using getOrElse() Method (136)Using isEmpty() Method (137)Scala Option Methods (137)Scala Iterators (139)Find Min & Max values Element (140)Find the length of the Iterator (140)Scala Iterator Methods (141)16.SCALA – TRAITS (146)Value classes and Universal traits (148)When to Use Traits? (148)17.SCALA – PATTERN MATCHING (150)Matching using case Classes (151)18.SCALA – REGULAR EXPRESSIONNS (154)Forming Regular Expressions (156)vi19.SCALA – EXCEPTION HANDLING (161)Throwing Exceptions (161)Catching Exceptions (161)The finally Clause (162)20.SCALA – EXTRACTORS (164)Example (164)Pattern Matching with Extractors (165)21.SCALA – FILES I/O (167)Reading a Line from Command Line (167)Reading File Content (168)vii1.Scala, short for Scalable Language, is a hybrid functional programming language. It was created by Martin Odersky. Scala smoothly integrates the features of object-oriented and functional languages. Scala is compiled to run on the Java Virtual Machine. Many existing companies, who depend on Java for business critical applications, are turning to Scala to boost their development productivity, applications scalability and overall reliability.Here we have presented a few points that makes Scala the first choice of application developers.Scala is object-orientedScala is a pure object-oriented language in the sense that every value is an object. Types and behavior of objects are described by classes and traits which will be explained in subsequent chapters.Classes are extended by subclassing and a flexible Mixin-based composition mechanism as a clean replacement for multiple inheritance.Scala is functionalScala is also a functional language in the sense that every function is a value and every value is an object so ultimately every function is an object.Scala provides a lightweight syntax for defining anonymous functions, it supports higher-order functions, it allows functions to be nested, and supports currying functions. These concepts will be explained in subsequent chapters.Scala is statically typedScala, unlike some of the other statically typed languages (C, Pascal, Rust, etc.), does not expect you to provide redundant type information. You don't have to specify a type in most cases, and you certainly don't have to repeat it.Scala runs on the JVMScala is compiled into Java Byte Code which is executed by the Java Virtual Machine (JVM). This means that Scala and Java have a common runtime platform. You can easily move from Java to Scala.The Scala compiler compiles your Scala code into Java Byte Code, which can then be executed by the ‘scala’ command. The ‘s cala’ command is similar to the java command, in that it executes your compiled Scala code.Scala Scala can Execute Java CodeScala enables you to use all the classes of the Java SDK and also your own custom Java classes, or your favorite Java open source projects.Scala can do Concurrent & Synchronize processingScala allows you to express general programming patterns in an effective way. It reduces the number of lines and helps the programmer to code in a type-safe way. It allows you to write codes in an immutable manner, which makes it easy to apply concurrency and parallelism (Synchronize).Scala vs JavaScala has a set of features that completely differ from Java. Some of these are: ∙All types are objects∙Type inference∙Nested Functions∙Functions are objects∙Domain specific language (DSL) support∙Traits∙Closures∙Concurrency support inspired by ErlangScala Web FrameworksScala is being used everywhere and importantly in enterprise web applications. You can check a few of the most popular Scala web frameworks:∙The Lift Framework∙The Play framework∙The Bowler framework2Scala3Scala can be installed on any UNIX flavored or Windows based system. Before you start installing Scala on your machine, you must have Java 1.8 or greater installed on your computer.Follow the steps given below to install Scala.Step 1: V erify Y our Java InstallationFirst of all, you need to have Java Software Development Kit (SDK) installed on your system. To verify this, execute any of the following two commands depending on the platform you are working on.If the Java installation has been done properly, then it will display the current version and specification of your Java installation. A sample output is given in the following table. PlatformCommandSample OutputWindowsOpen Command Console and type:\>java –versionJava version "1.8.0_31" Java (TM) SE Run TimeEnvironment (build 1.8.0_31-b31) Java Hotspot (TM) 64-bit Server VM (build 25.31-b07, mixed mode)LinuxOpen Command terminal and type: $java –versionJava version "1.8.0_31"Open JDK Runtime Environment (rhel-2.8.10.4.el6_4-x86_64)Open JDK 64-Bit Server VM (build 25.31-b07, mixed mode)2.We assume that the readers of this tutorial have Java SDK version 1.8.0_31 installed on their system.In case you do not have Java SDK, download its current version from /technetwork/java/javase/downloads/index.html and install it.Step 2: Set Y our Java EnvironmentSet the environment variable JAVA_HOME to point to the base directory location where Java is installed on your machine. For example,Platform DescriptionWindows Set JAVA_HOME to C:\ProgramFiles\java\jdk1.7.0_60Linux Export JAVA_HOME=/usr/local/java-currentAppend the full path of Java compiler location to the System Path.Platform DescriptionWindows Append the String "C:\Program Files\Java\jdk1.7.0_60\bin" to the end of the system variable PATH.Linux Export PATH=$PATH:$JAVA_HOME/bin/Execute the command java -version from the command prompt as explained above.Step 3: Install ScalaYou can download Scala from /downloads. At the time of writing this tutorial, I downloaded ‘scala-2.11.5-installer.jar’. Make sure you have admin privilege to proceed. Now, execute the following command at the command prompt:Platform Command & Output Description4Windows\>java –jar scala-2.11.5-installer.jar\> This command will display an installation wizard, which will guide you to install Scala on your windows machine. During installation, it will ask for license agreement, simply accept it and further it will ask a path where Scala will be installed. I selected default given path “C:\Program Files\Scala”, you can select a suitable path as per your convenience.Linux Command:$java –jar scala-2.9.0.1-installer.jarOutput:Welcome to the installation of Scala2.9.0.1!The homepage is at: http://Scala-/press 1 to continue, 2 to quit, 3 toredisplay1 ................................................[ Starting to unpack ][ Processing package: Software PackageInstallation (1/1) ][ Unpacking finished ][ Console installation done ]During installation, it will ask forlicense agreement, to accept ittype 1 and it will ask a path whereScala will be installed. I entered/usr/local/share, you can select asuitable path as per yourconvenience.Finally, open a new command prompt and type Scala -version and press Enter. You should see the following:Platform Command Output5Windows \>scala -version Scala code runner version 2.11.5 -- Copyright 2002-2013, LAMP/EPFLLinux $scala -version Scala code runner version2.9.0.1 – Copyright 2002-2013, LAMP/EPFL6Scala7If you have a good understanding on Java, then it will be very easy for you to learn Scala. The biggest syntactic difference between Scala and Java is that the ‘;’ line end character is optional.When we consider a Scala program, it can be defined as a collection of objects that communicate via invoking each other’s methods. Let us now briefly look into what do class, object, methods and instant variables mean.∙Object - Objects have states and behaviors. An object is an instance of a class. Example: A dog has states - color, name, breed as well as behaviors - wagging, barking, and eating.∙Class - A class can be defined as a template/blueprint that describes the behaviors/states that object of its type support.∙Methods - A method is basically a behavior. A class can contain many methods. It is in methods where the logics are written, data is manipulated and all the actions are executed.∙Fields - Each object has its unique set of instant variables, which are called fields. An object's state is created by the values assigned to these fields.∙Closure - A closure is a function, whose return value depends on the value of one or more variables declared outside this function.∙Traits - A trait encapsulates method and field definitions, which can then be reused by mixing them into classes. Traits are used to define object types by specifying the signature of the supported methods.First Scala ProgramWe can execute a Scala program in two modes: one is interactive mode and another is script mode .Interactive ModeOpen the command prompt and use the following command to open Scala. \>ScalaIf Scala is installed in your system, the following output will be displayed:3.Welcome to Scala version 2.9.0.1Type in expressions to have them evaluated.Type: help for more information.Type the following text to the right of the Scala prompt and press the Enter key:Scala> println(“Hello, scala”);It will produce the following result:Hello, Scala!Script ModeUse the following instructions to write a Scala program in script mode. Open notepad and add the following code into it.object HelloWorld {/* This is my first java program.* This will print 'Hello World' as the output*/def main(args: Array[String]) {println("Hello, world!") // prints Hello World}}Save the file as: HelloWorld.scala.Open the command prompt window and go to the directory where the program file is saved. The ‘scalac’ command is used to compile the Scala program and it will generate a few class files in the current directory. One of them will be called HelloWorld.class. This is a bytecode which will run on Java Virtual Machine (JVM) using ‘scala’ command.Use the following command to compile and execute your Scala program.\>scalac HelloWorld.scala\>scala HelloWorldOutput:8Hello, World!Basic SyntaxThe following are the basic syntaxes and coding conventions in Scala programming.∙Case Sensitivity - Scala is case-sensitive, which means identifier Hello and hello would have different meaning in Scala.∙Class Names - For all class names, the first letter should be in Upper Case.If several words are used to form a name of the class, each inner word's first letter should be in Upper Case. Example: class MyFirstScalaClass.∙Method Names - All method names should start with a Lower Case letter.If multiple words are used to form the name of the method, then each inner word's first letter should be in Upper Case. Example: def myMethodName()∙Program File Name - Name of the program file should exactly match the object name. When saving the file you should save it using the object name (Remember Scala is case-sensitive) and append ‘.scala’ to the end of the name. (If the file name and the object name do not match your program will not compile).Example:Assume 'HelloWorld' is the object name. Then the file should be saved as 'HelloWorld.scala'.∙def main(args: Array[String]) - Scala program processing starts from the main() method which is a mandatory part of every Scala Program.Scala IdentifiersAll Scala components require names. Names used for objects, classes, variables and methods are called identifiers. A keyword cannot be used as an identifier and identifiers are case-sensitive. Scala supports four types of identifiers.Alphanumeric IdentifiersAn alphanumeric identifier starts with a letter or an underscore, which can be followed by further letters, digits, or underscores. The '$' character is a reserved keyword in Scala and should not be used in identifiers.Following are legal alphanumeric identifiers:age, salary, _value, __1_valueFollowing are illegal identifiers:9$salary, 123abc, -salaryOperator IdentifiersAn operator identifier consists of one or more operator characters. Operator characters are printable ASCII characters such as +, :, ?, ~ or #.Following are legal operator identifiers:+, ++, :::, <?>, :>,The Scala compiler will internally "mangle" operator identifiers to turn them into legal Java identifiers with embedded $ characters. For instance, the identifier :-> would be represented internally as $colon$minus$greater.Mixed IdentifiersA mixed identifier consists of an alphanumeric identifier, which is followed by an underscore and an operator identifier.Following are legal mixed identifiers:unary_+, myvar_=Here, unary_+ used as a method name defines a unary + operator and myvar_= used as method name defines an assignment operator (operator overloading).Literal IdentifiersA literal identifier is an arbitrary string enclosed in back ticks (` . . . `).Following are legal literal identifiers:`x` `<clinit>` `yield`Scala KeywordsThe following list shows the reserved words in Scala. These reserved words may not be used as constant or variable or any other identifier names.abstract case catch Class def do else extendsfalse final finally For10forSome if implicit importlazy match new Nullobject override package privateprotected return sealed super this throw trait Trytrue type val Varwhile with yield- : = =><- <: <% >:# @Comments in ScalaScala supports single-line and multi-line comments very similar to Java. Multi-line comments may be nested, but are required to be properly nested. All characters available inside any comment are ignored by Scala compiler.object HelloWorld {/* This is my first java program.* This will print 'Hello World' as the output* This is an example of multi-line comments.*/def main(args: Array[String]) {// Prints Hello World// This is also an example of single line comment.println ("Hello, world!")}}Blank Lines and WhitespaceA line containing only whitespace, possibly with a comment, is known as a blank line, and Scala totally ignores it. Tokens may be separated by whitespace characters and/or comments.11Newline CharactersScala is a line-oriented language where statements may be terminated by semicolons (;) or newlines. A semicolon at the end of a statement is usually optional. You can type one if you want but you don't have to if the statement appears by itself on a single line. On the other hand, a semicolon is required if you write multiple statements on a single line. Below syntax is the usage of multiple statements.val s = "hello"; println(s)Scala PackagesA package is a named module of code. For example, the Lift utility package is net.liftweb.util. The package declaration is the first non-comment line in the source file as follows:package com.liftcode.stuffScala packages can be imported so that they can be referenced in the current compilation scope. The following statement imports the contents of the scala.xml package:import scala.xml._You can import a single class and object, for example, HashMap from the scala.collection.mutable package:import scala.collection.mutable.HashMapYou can import more than one class or object from a single package, for example, TreeMap and TreeSet from the scala.collection.immutable package:import scala.collection.immutable.{TreeMap, TreeSet}Apply DynamicA marker trait that enables dynamic invocations. Instances x of this trait allow method invocations x.meth(args) for arbitrary method names meth and argument lists args as well as field accesses x.field for arbitrary field namesfield. This feature is introduced in Scala-2.10. If a call is not natively supported by x (i.e. if type checking fails), it is rewritten according to the following rules:foo.method("blah") ~~> foo.applyDynamic("method")("blah")12foo.method(x = "blah") ~~> foo.applyDynamicNamed("method")(("x", "blah"))foo.method(x = 1, 2) ~~> foo.applyDynamicNamed("method")(("x", 1), ("", 2))foo.field ~~> foo.selectDynamic("field")foo.varia = 10 ~~> foo.updateDynamic("varia")(10)foo.arr(10) = 13 ~~> foo.selectDynamic("arr").update(10, 13)foo.arr(10) ~~> foo.applyDynamic("arr")(10)13End of ebook previewIf you liked what you saw…Buy it from our store @ https://14。

Error MessagesF9001 Error internal function call.F9002 Error internal RTOS function callF9003 WatchdogF9004 Hardware trapF8000 Fatal hardware errorF8010 Autom. commutation: Max. motion range when moving back F8011 Commutation offset could not be determinedF8012 Autom. commutation: Max. motion rangeF8013 Automatic commutation: Current too lowF8014 Automatic commutation: OvercurrentF8015 Automatic commutation: TimeoutF8016 Automatic commutation: Iteration without resultF8017 Automatic commutation: Incorrect commutation adjustment F8018 Device overtemperature shutdownF8022 Enc. 1: Enc. signals incorr. (can be cleared in ph. 2) F8023 Error mechanical link of encoder or motor connectionF8025 Overvoltage in power sectionF8027 Safe torque off while drive enabledF8028 Overcurrent in power sectionF8030 Safe stop 1 while drive enabledF8042 Encoder 2 error: Signal amplitude incorrectF8057 Device overload shutdownF8060 Overcurrent in power sectionF8064 Interruption of motor phaseF8067 Synchronization PWM-Timer wrongF8069 +/-15Volt DC errorF8070 +24Volt DC errorF8076 Error in error angle loopF8078 Speed loop error.F8079 Velocity limit value exceededF8091 Power section defectiveF8100 Error when initializing the parameter handlingF8102 Error when initializing power sectionF8118 Invalid power section/firmware combinationF8120 Invalid control section/firmware combinationF8122 Control section defectiveF8129 Incorrect optional module firmwareF8130 Firmware of option 2 of safety technology defectiveF8133 Error when checking interrupting circuitsF8134 SBS: Fatal errorF8135 SMD: Velocity exceededF8140 Fatal CCD error.F8201 Safety command for basic initialization incorrectF8203 Safety technology configuration parameter invalidF8813 Connection error mains chokeF8830 Power section errorF8838 Overcurrent external braking resistorF7010 Safely-limited increment exceededF7011 Safely-monitored position, exceeded in pos. DirectionF7012 Safely-monitored position, exceeded in neg. DirectionF7013 Safely-limited speed exceededF7020 Safe maximum speed exceededF7021 Safely-limited position exceededF7030 Position window Safe stop 2 exceededF7031 Incorrect direction of motionF7040 Validation error parameterized - effective thresholdF7041 Actual position value validation errorF7042 Validation error of safe operation modeF7043 Error of output stage interlockF7050 Time for stopping process exceeded8.3.15 F7051 Safely-monitored deceleration exceeded (159)8.4 Travel Range Errors (F6xxx) (161)8.4.1 Behavior in the Case of Travel Range Errors (161)8.4.2 F6010 PLC Runtime Error (162)8.4.3 F6024 Maximum braking time exceeded (163)8.4.4 F6028 Position limit value exceeded (overflow) (164)8.4.5 F6029 Positive position limit exceeded (164)8.4.6 F6030 Negative position limit exceeded (165)8.4.7 F6034 Emergency-Stop (166)8.4.8 F6042 Both travel range limit switches activated (167)8.4.9 F6043 Positive travel range limit switch activated (167)8.4.10 F6044 Negative travel range limit switch activated (168)8.4.11 F6140 CCD slave error (emergency halt) (169)8.5 Interface Errors (F4xxx) (169)8.5.1 Behavior in the Case of Interface Errors (169)8.5.2 F4001 Sync telegram failure (170)8.5.3 F4002 RTD telegram failure (171)8.5.4 F4003 Invalid communication phase shutdown (172)8.5.5 F4004 Error during phase progression (172)8.5.6 F4005 Error during phase regression (173)8.5.7 F4006 Phase switching without ready signal (173)8.5.8 F4009 Bus failure (173)8.5.9 F4012 Incorrect I/O length (175)8.5.10 F4016 PLC double real-time channel failure (176)8.5.11 F4017 S-III: Incorrect sequence during phase switch (176)8.5.12 F4034 Emergency-Stop (177)8.5.13 F4140 CCD communication error (178)8.6 Non-Fatal Safety Technology Errors (F3xxx) (178)8.6.1 Behavior in the Case of Non-Fatal Safety Technology Errors (178)8.6.2 F3111 Refer. missing when selecting safety related end pos (179)8.6.3 F3112 Safe reference missing (179)8.6.4 F3115 Brake check time interval exceeded (181)Troubleshooting Guide | Rexroth IndraDrive Electric Drivesand ControlsI Bosch Rexroth AG VII/XXIITable of ContentsPage8.6.5 F3116 Nominal load torque of holding system exceeded (182)8.6.6 F3117 Actual position values validation error (182)8.6.7 F3122 SBS: System error (183)8.6.8 F3123 SBS: Brake check missing (184)8.6.9 F3130 Error when checking input signals (185)8.6.10 F3131 Error when checking acknowledgment signal (185)8.6.11 F3132 Error when checking diagnostic output signal (186)8.6.12 F3133 Error when checking interrupting circuits (187)8.6.13 F3134 Dynamization time interval incorrect (188)8.6.14 F3135 Dynamization pulse width incorrect (189)8.6.15 F3140 Safety parameters validation error (192)8.6.16 F3141 Selection validation error (192)8.6.17 F3142 Activation time of enabling control exceeded (193)8.6.18 F3143 Safety command for clearing errors incorrect (194)8.6.19 F3144 Incorrect safety configuration (195)8.6.20 F3145 Error when unlocking the safety door (196)8.6.21 F3146 System error channel 2 (197)8.6.22 F3147 System error channel 1 (198)8.6.23 F3150 Safety command for system start incorrect (199)8.6.24 F3151 Safety command for system halt incorrect (200)8.6.25 F3152 Incorrect backup of safety technology data (201)8.6.26 F3160 Communication error of safe communication (202)8.7 Non-Fatal Errors (F2xxx) (202)8.7.1 Behavior in the Case of Non-Fatal Errors (202)8.7.2 F2002 Encoder assignment not allowed for synchronization (203)8.7.3 F2003 Motion step skipped (203)8.7.4 F2004 Error in MotionProfile (204)8.7.5 F2005 Cam table invalid (205)8.7.6 F2006 MMC was removed (206)8.7.7 F2007 Switching to non-initialized operation mode (206)8.7.8 F2008 RL The motor type has changed (207)8.7.9 F2009 PL Load parameter default values (208)8.7.10 F2010 Error when initializing digital I/O (-> S-0-0423) (209)8.7.11 F2011 PLC - Error no. 1 (210)8.7.12 F2012 PLC - Error no. 2 (210)8.7.13 F2013 PLC - Error no. 3 (211)8.7.14 F2014 PLC - Error no. 4 (211)8.7.15 F2018 Device overtemperature shutdown (211)8.7.16 F2019 Motor overtemperature shutdown (212)8.7.17 F2021 Motor temperature monitor defective (213)8.7.18 F2022 Device temperature monitor defective (214)8.7.19 F2025 Drive not ready for control (214)8.7.20 F2026 Undervoltage in power section (215)8.7.21 F2027 Excessive oscillation in DC bus (216)8.7.22 F2028 Excessive deviation (216)8.7.23 F2031 Encoder 1 error: Signal amplitude incorrect (217)VIII/XXII Bosch Rexroth AG | Electric Drivesand ControlsRexroth IndraDrive | Troubleshooting GuideTable of ContentsPage8.7.24 F2032 Validation error during commutation fine adjustment (217)8.7.25 F2033 External power supply X10 error (218)8.7.26 F2036 Excessive position feedback difference (219)8.7.27 F2037 Excessive position command difference (220)8.7.28 F2039 Maximum acceleration exceeded (220)8.7.29 F2040 Device overtemperature 2 shutdown (221)8.7.30 F2042 Encoder 2: Encoder signals incorrect (222)8.7.31 F2043 Measuring encoder: Encoder signals incorrect (222)8.7.32 F2044 External power supply X15 error (223)8.7.33 F2048 Low battery voltage (224)8.7.34 F2050 Overflow of target position preset memory (225)8.7.35 F2051 No sequential block in target position preset memory (225)8.7.36 F2053 Incr. encoder emulator: Pulse frequency too high (226)8.7.37 F2054 Incr. encoder emulator: Hardware error (226)8.7.38 F2055 External power supply dig. I/O error (227)8.7.39 F2057 Target position out of travel range (227)8.7.40 F2058 Internal overflow by positioning input (228)8.7.41 F2059 Incorrect command value direction when positioning (229)8.7.42 F2063 Internal overflow master axis generator (230)8.7.43 F2064 Incorrect cmd value direction master axis generator (230)8.7.44 F2067 Synchronization to master communication incorrect (231)8.7.45 F2068 Brake error (231)8.7.46 F2069 Error when releasing the motor holding brake (232)8.7.47 F2074 Actual pos. value 1 outside absolute encoder window (232)8.7.48 F2075 Actual pos. value 2 outside absolute encoder window (233)8.7.49 F2076 Actual pos. value 3 outside absolute encoder window (234)8.7.50 F2077 Current measurement trim wrong (235)8.7.51 F2086 Error supply module (236)8.7.52 F2087 Module group communication error (236)8.7.53 F2100 Incorrect access to command value memory (237)8.7.54 F2101 It was impossible to address MMC (237)8.7.55 F2102 It was impossible to address I2C memory (238)8.7.56 F2103 It was impossible to address EnDat memory (238)8.7.57 F2104 Commutation offset invalid (239)8.7.58 F2105 It was impossible to address Hiperface memory (239)8.7.59 F2110 Error in non-cyclical data communic. of power section (240)8.7.60 F2120 MMC: Defective or missing, replace (240)8.7.61 F2121 MMC: Incorrect data or file, create correctly (241)8.7.62 F2122 MMC: Incorrect IBF file, correct it (241)8.7.63 F2123 Retain data backup impossible (242)8.7.64 F2124 MMC: Saving too slowly, replace (243)8.7.65 F2130 Error comfort control panel (243)8.7.66 F2140 CCD slave error (243)8.7.67 F2150 MLD motion function block error (244)8.7.68 F2174 Loss of motor encoder reference (244)8.7.69 F2175 Loss of optional encoder reference (245)Troubleshooting Guide | Rexroth IndraDrive Electric Drivesand Controls| Bosch Rexroth AG IX/XXIITable of ContentsPage8.7.70 F2176 Loss of measuring encoder reference (246)8.7.71 F2177 Modulo limitation error of motor encoder (246)8.7.72 F2178 Modulo limitation error of optional encoder (247)8.7.73 F2179 Modulo limitation error of measuring encoder (247)8.7.74 F2190 Incorrect Ethernet configuration (248)8.7.75 F2260 Command current limit shutoff (249)8.7.76 F2270 Analog input 1 or 2, wire break (249)8.7.77 F2802 PLL is not synchronized (250)8.7.78 F2814 Undervoltage in mains (250)8.7.79 F2815 Overvoltage in mains (251)8.7.80 F2816 Softstart fault power supply unit (251)8.7.81 F2817 Overvoltage in power section (251)8.7.82 F2818 Phase failure (252)8.7.83 F2819 Mains failure (253)8.7.84 F2820 Braking resistor overload (253)8.7.85 F2821 Error in control of braking resistor (254)8.7.86 F2825 Switch-on threshold braking resistor too low (255)8.7.87 F2833 Ground fault in motor line (255)8.7.88 F2834 Contactor control error (256)8.7.89 F2835 Mains contactor wiring error (256)8.7.90 F2836 DC bus balancing monitor error (257)8.7.91 F2837 Contactor monitoring error (257)8.7.92 F2840 Error supply shutdown (257)8.7.93 F2860 Overcurrent in mains-side power section (258)8.7.94 F2890 Invalid device code (259)8.7.95 F2891 Incorrect interrupt timing (259)8.7.96 F2892 Hardware variant not supported (259)8.8 SERCOS Error Codes / Error Messages of Serial Communication (259)9 Warnings (Exxxx) (263)9.1 Fatal Warnings (E8xxx) (263)9.1.1 Behavior in the Case of Fatal Warnings (263)9.1.2 E8025 Overvoltage in power section (263)9.1.3 E8026 Undervoltage in power section (264)9.1.4 E8027 Safe torque off while drive enabled (265)9.1.5 E8028 Overcurrent in power section (265)9.1.6 E8029 Positive position limit exceeded (266)9.1.7 E8030 Negative position limit exceeded (267)9.1.8 E8034 Emergency-Stop (268)9.1.9 E8040 Torque/force actual value limit active (268)9.1.10 E8041 Current limit active (269)9.1.11 E8042 Both travel range limit switches activated (269)9.1.12 E8043 Positive travel range limit switch activated (270)9.1.13 E8044 Negative travel range limit switch activated (271)9.1.14 E8055 Motor overload, current limit active (271)9.1.15 E8057 Device overload, current limit active (272)X/XXII Bosch Rexroth AG | Electric Drivesand ControlsRexroth IndraDrive | Troubleshooting GuideTable of ContentsPage9.1.16 E8058 Drive system not ready for operation (273)9.1.17 E8260 Torque/force command value limit active (273)9.1.18 E8802 PLL is not synchronized (274)9.1.19 E8814 Undervoltage in mains (275)9.1.20 E8815 Overvoltage in mains (275)9.1.21 E8818 Phase failure (276)9.1.22 E8819 Mains failure (276)9.2 Warnings of Category E4xxx (277)9.2.1 E4001 Double MST failure shutdown (277)9.2.2 E4002 Double MDT failure shutdown (278)9.2.3 E4005 No command value input via master communication (279)9.2.4 E4007 SERCOS III: Consumer connection failed (280)9.2.5 E4008 Invalid addressing command value data container A (280)9.2.6 E4009 Invalid addressing actual value data container A (281)9.2.7 E4010 Slave not scanned or address 0 (281)9.2.8 E4012 Maximum number of CCD slaves exceeded (282)9.2.9 E4013 Incorrect CCD addressing (282)9.2.10 E4014 Incorrect phase switch of CCD slaves (283)9.3 Possible Warnings When Operating Safety Technology (E3xxx) (283)9.3.1 Behavior in Case a Safety Technology Warning Occurs (283)9.3.2 E3100 Error when checking input signals (284)9.3.3 E3101 Error when checking acknowledgment signal (284)9.3.4 E3102 Actual position values validation error (285)9.3.5 E3103 Dynamization failed (285)9.3.6 E3104 Safety parameters validation error (286)9.3.7 E3105 Validation error of safe operation mode (286)9.3.8 E3106 System error safety technology (287)9.3.9 E3107 Safe reference missing (287)9.3.10 E3108 Safely-monitored deceleration exceeded (288)9.3.11 E3110 Time interval of forced dynamization exceeded (289)9.3.12 E3115 Prewarning, end of brake check time interval (289)9.3.13 E3116 Nominal load torque of holding system reached (290)9.4 Non-Fatal Warnings (E2xxx) (290)9.4.1 Behavior in Case a Non-Fatal Warning Occurs (290)9.4.2 E2010 Position control with encoder 2 not possible (291)9.4.3 E2011 PLC - Warning no. 1 (291)9.4.4 E2012 PLC - Warning no. 2 (291)9.4.5 E2013 PLC - Warning no. 3 (292)9.4.6 E2014 PLC - Warning no. 4 (292)9.4.7 E2021 Motor temperature outside of measuring range (292)9.4.8 E2026 Undervoltage in power section (293)9.4.9 E2040 Device overtemperature 2 prewarning (294)9.4.10 E2047 Interpolation velocity = 0 (294)9.4.11 E2048 Interpolation acceleration = 0 (295)9.4.12 E2049 Positioning velocity >= limit value (296)9.4.13 E2050 Device overtemp. Prewarning (297)Troubleshooting Guide | Rexroth IndraDrive Electric Drivesand Controls| Bosch Rexroth AG XI/XXIITable of ContentsPage9.4.14 E2051 Motor overtemp. prewarning (298)9.4.15 E2053 Target position out of travel range (298)9.4.16 E2054 Not homed (300)9.4.17 E2055 Feedrate override S-0-0108 = 0 (300)9.4.18 E2056 Torque limit = 0 (301)9.4.19 E2058 Selected positioning block has not been programmed (302)9.4.20 E2059 Velocity command value limit active (302)9.4.21 E2061 Device overload prewarning (303)9.4.22 E2063 Velocity command value > limit value (304)9.4.23 E2064 Target position out of num. range (304)9.4.24 E2069 Holding brake torque too low (305)9.4.25 E2070 Acceleration limit active (306)9.4.26 E2074 Encoder 1: Encoder signals disturbed (306)9.4.27 E2075 Encoder 2: Encoder signals disturbed (307)9.4.28 E2076 Measuring encoder: Encoder signals disturbed (308)9.4.29 E2077 Absolute encoder monitoring, motor encoder (encoder alarm) (308)9.4.30 E2078 Absolute encoder monitoring, opt. encoder (encoder alarm) (309)9.4.31 E2079 Absolute enc. monitoring, measuring encoder (encoder alarm) (309)9.4.32 E2086 Prewarning supply module overload (310)9.4.33 E2092 Internal synchronization defective (310)9.4.34 E2100 Positioning velocity of master axis generator too high (311)9.4.35 E2101 Acceleration of master axis generator is zero (312)9.4.36 E2140 CCD error at node (312)9.4.37 E2270 Analog input 1 or 2, wire break (312)9.4.38 E2802 HW control of braking resistor (313)9.4.39 E2810 Drive system not ready for operation (314)9.4.40 E2814 Undervoltage in mains (314)9.4.41 E2816 Undervoltage in power section (314)9.4.42 E2818 Phase failure (315)9.4.43 E2819 Mains failure (315)9.4.44 E2820 Braking resistor overload prewarning (316)9.4.45 E2829 Not ready for power on (316)。

2015 IM2C Problem Movie SchedulingTeam 2015004Team # 20150042 / 44SummaryArranging a movie’s shooting schedule can mean a lot of hard work. Different actors and actresses have their own schedules, various resources need to be booked, and special restrictions of some scenes must be considered. In order to offer a satisfactory solution, we have developed a model capable of finding possible schedules and selecting several better schedules based on our clients’ preferences. We have also provided solutions that help our clients adjust their plan if an accident happens, as well as helping them identify the most important constraints that would most greatly affect their schedule if varied.In the first part of our model, we search the possible shooting schedules according to the information that our clients provided, which may include the available time periods of each actor, specific sites and special resources. We sort out the various available dates by scenes, and using a 0-1 matrix to represent the availability of each scene on each of possible shooting dates. We then use the backtracking method, which is commonly used in solving constraint satisfaction problems and combinatorial search, to find arrangements that satisfy each scene’s availability dates. Moreover, in order to further shorten the running time of our program, we pre-arranged the order of scenes, so that the scenes with the strictest restrictions would be considered first, enabling the program using the backtracking method to find more results more quickly.In the second part of our model, we consider other special restrictions requested (for example, the required order of some scenes) and the general preference of our clients. We filter the solutions drawn from the previous part (which could be up to 10000 solutions), by first deleting the deficient solutions based on special restrictions, and then arraying the remaining solutions from the best to the worst. Our model can calculate the total shooting schedule length, the frequency of location changes, and required number of studios in a solution. And along with the average cost to rent a studio, the intended frequency of flexible day, the total budget, and traffic budget of our clients, we can assess the general appropriateness1and some characteristics of a schedule, based on which we array the solutions and provide 11 top schedules to our clients. The solutions include 5 overall best solutions, 2 solutions with least number of location changes, 2 solutions with least number of studios2, and 2 solutions with least number of shooting days.Extending our model, we provide ways to adjust an original schedule to various accidents. When our clients provide us with information of the original schedule they selected, accidents occurred and new restrictions, we can return a new schedule with feasible adjustments. These adjustments are achieved by running the program with the new data while leaving intact the scenes that have already happened or that are not expected to change. In this way, the computational complexity would be greatly reduced and the new schedule would involve as few changes as possible. Lastly, we can also evaluate the most important constraints for our clients by calculating the differences in average characteristic value of top solutions before and after a constraint is changed. Having access to such information, our clients would be able to pay more attention to those important constraints and prevent major delays of their original shooting schedule.1We use the characteristic value to evaluate the appropriateness of a solution. For further explanation, please see 2.2, where we explain in detail how we calculate the characteristic value of a solution.2 Different settings cannot be constructed or shooting simultaneously at the same studio, so more than one studio may be required.Content1. Problem interpretation (4)1.1 Problem restatement (4)1.2 Assumptions and Justifications (4)1.3 The goal of modeling (5)2 Model (5)2.1 Overview of the model (5)2.2 Definition of variables (5)2.3 Relations between variables (8)2.4 Algorithm of finding all possible schedules (9)2.5 Algorithm of finding the best schedule (10)2.6 Adjustment for accidents (11)3 Programming Approach (11)3.1 Overview of the program (11)3.2 Introduction of the program (12)3.2.1 Inputs (12)3.2.2 Algorithm of finding (12)3.2.3 Algorithm of filtering (12)3.2.4 Outputs (13)4. Case Analysis (13)4.1 Overview of the case (13)4.1.1 Roles and the available times of their actors (13)4.1.2 Scenes (14)4.1.3 Available time of sites (15)4.1.4 Preparation time of settings (15)4.1.5 Restriction of specific orders (15)4.1.6 Other constraints (16)4.1.7 Other settings (16)4.2 Case solving (16)4.2.1 The optimal schedule (16)4.2.2 Schedule analysis (17)4.3 Adjustment for accidents (17)4.3.1 Assumed accidents (17)4.3.2 Adjustment realization (17)4.3.3 Results (18)5 The way of finding the most important constraints (19)5.1 Overview of the algorithm (19)5.2 Description of the algorithm (19)6 Reviews and Prospect (20)7 Reference Material (21)8 Appendix (22)1. Problem interpretation1.1 Problem restatementAs one of the major types of popular entertainment, motion picture has become a fast-growing industry. The constant demand for new excellent films makes effective filmmaking an important job. Therefore, it is necessary for every producer to develop a good filming schedule within certain constraints, such as the availability dates of stars and specific resources. We hope to use mathematical models to come up with this optimal schedule.1.2 Assumptions and Justifications1) The filming schedule has a limited time span whose starting point and ending point are both reachable.2) The filming schedule must conform to the following restrictions, which are inflexible and cannot be violated:i.The availability dates of some stars.ii.The availability dates of specific sites.iii.The availability dates for specific resources.iv.The time required to construct and film on a list of sets.v.Some scenes cannot be shot until after certain computer generated content is defined and other physical items are constructed.vi.Some scenes cannot be shot until other scenes are finished. For example, if a set is finally destroyed, all other scenes related to this set are supposed to be shot beforeit happens.vii.Extra time is needed for redoing some shots if they turn out to be inadequate after editing and review.viii.Extra time is needed for making up some delay or changes.ix.During the filming process, the director might decide to add some new scenes, which will influence the schedule.3) The schedule breaks down time into days for further allocation.‐Filming schedules always choose “Day” as their unit, which is pretty reasonable.First, it is small enough, because most scenes require one or several days to be shot.Second, it is still flexible, because in every single day small delays can becompensated by working overtime, and night shoots can be compensated by morerests in the daytime.4) Several scenes cannot be shot at the same time.‐Every time a scene is shot, the director must be present.5) The construction of sets does not interfere with the filming process.‐Workers can build the sets themselves without being monitored by the director.6) If multiple schedules are available, the studio will consider the continuity of locations.‐ Since the crews do not wish to move frequently, a small number of changes infilming locations is preferred.7) Since we can rent several filming studios, it is possible to build different settings at the same time. However, renting more filming studios will increase the cost, so we hope that these constructions do not conflict with each other.8) Although the crew may not work every day, we should pay for them as long as the shoot is not finished. Therefore, the whole time span is not likely to be too long.9) To deal with problems of delays and reshoots, the filming crews usually have a “flexible day” for every two weeks. On this “flexible day”, they can shoot the scenes that were not completely finished before. Each day without a shooting plan can be seen as a flexible day.1.3 The goal of modelingAccording to the assumptions given above, the optimal schedule derived from our model is an arrangement that:‐ satisfies all the inflexible restrictions in 2nd assumption;‐ promises relatively less changes in locations;‐ has relatively less conflicts in construction of different settings;‐ has an appropriate time span;‐ has enough flexible day for problems of delays and reshoots.In this model, we attempt to find a schedule that can excel in all these criteria.2 Model2.1 Overview of the modelThe whole model consists of two parts: “finding” solutions and “filtering” solutions. For each specific situation, our model first figures out all possible schedules, and then picks up the best ones among them. The model can also adjust previous schedules to deal with new accidents, such as delays in some aspects or changes in the availability of some assets.2.2 Definition of variablesIn order to build a reasonable model, we first introduced some variables:max T : The maximum time length of filming schedule, which is the difference between the latestdate and the earliest date appearing in the input sheets. A movie cannot be finished if the span of shooting schedule is longer than max T .min T : The minimum time length of filming schedule, which is the actual shooting time. k A : The personal schedule of actor k , which is a 0-1 array within the spread of max T . A ‘0’ as the n th element means that the actor cannot work on the n th day. Similarly, ‘1’ means the actor can join shooting on that day.l B : The availability dates of site l . We can simply regard a site as an actor, because toaccomplish a shooting task, we need both the actors and the sites available at the same time. If one element is unavailable, the shooting cannot be accomplished. Thus we describel B in the same way as that of k A ; that is, a 0-1 array with the length of max T . Additionally, we define B as the number of sites.m C : The availability dates of setting m . Similar to sites, a setting can be treated just like an actor. We define C as the number of the settings.n D : The availability dates of special resource n , such as a helicopter or a tank, which is only available at certain time intervals. Since resources also can be treated as actors, we use k A to record n D to simplify the model. We define A as the total number of actors and specialresources. (The reason why we do not combinel B and m C with k A is that information about sites and settings are required for other calculations in the “filtering” process.)o N : A set that records the time required (a.k.a. time length) to film scene o and the elements (e.g. actors, special resources, and a site or a setting) involved. o N cannot be an empty set; it has to contain at least one actor and one site or setting. Generally, its time length cannot be changed, which already contains a little flexible time for preparation and transportation. Moreover, we consider a scene the smallest part of shooting, which means that a scene cannot be divided. When all scenes are finished, the shooting task is done. We defineo N as the time length of this scene,which is an element of the set. i Q : A sequence showing a specific arrangement of all o N s. i Q is a time plan for all scenes. o N t : The number of possible ways to arrange scene o , regardless of arrangements of all otherscenes.i x : The actual shooting time length of i Q .*k A : An “Invisible actor” that has the same character as a real actor. We can use this idea to fulfill the special requirements, such as a specific scene that can be shot in several particular time intervals. This variable depends on requirements of the clients.p E : A special restriction p that i Q must conform to. For example, the restriction that 1Nmust be shot before2N are accomplished. This variable depends on requirements of the clients. P : A value between 0 and 1 that measures the ability of a schedule to deal with delays and reshoots. We define that in every 1P days, one flexible day is used to compensate delays and reshoots. Small delays or quick reshoots, which need only a few hours, can be adjusted on the very day it occurs, so that the whole schedule will not be affected. If delays or reshoots cost a longer time, we can resort remaining scenes into a new schedule. So that only when delays and reshoots need one day or several days, the flexible day in the 1P days is needed. P is an average value, which satisfies 01P £<. This variable depends on requirements of the clients.i K : The number of changes in sites or settings (a.k.a. location changes) that occur in an arrangement i Q .0K : The least possible number of location changes.i L : The number of required filming studios.i y : The extra number of i Q ’s location changes. Since we want to avoid unnecessary location changes, the smaller i y is, the better i Q is.i z : The extra number of filming studios that are required. We say that the more filming studios are used, the more money is spent, and the less efficient the schedule is.budget M : Total budget of the movie, which is given by our client.totaltraffic M : Total traffic budget of the movie, which is also decided by our client.itrafficpertime M : The average cost of a location change, which is the money spent on travelling andtransportation.studio M : The average cost of one studio, including the construction cost and art design cost. It is decided by client. h : The budget per day. This variable builds a connection between time and money, so that we can find the equivalent of a certain amount of money in some measure of time. However, it is just an estimation variable, time is always invaluable.i q : Penalty coefficient of i y (illustrated below).a : Penalty coefficient of i z (illustrated below).2.3 Relations between variables According to the definitions of these variables, we can come up with some basic relationships:min =o T N å (2.3-1)min max i T x T ££ (2.3-2)0=1K B C +- (2.3-3)0i i y K K =- (2.3-4)when 0i L ¹,1i i z L =-; when 0i L =, 0i z = (2.3-5)=i totaltraffic trafficpertime i M M K (2.3-6) min budgetM T h = (2.3-7)We believe that a large number of changes in locations are “bad” for a shooting schedule; too many filming studios are “bad”, too. In order to describe the how bad they are, we can transform their financial cost into time of equal value. So we have=itrafficperday i M q h(2.3-8) =studio M a h (2.3-9)Moreover, when the constraints are too loose, most of possible solutions will be far from optimal. To prevent this condition, we add another limit:max min 21T T P êú£êúêú+ëû(2.3-10) This means that max T cannot be too long. max T should be longer than min T by a period of time no more than min 2PT , or there will be too much idle time. Since too much idle time causes the increase of possible solutions, if the case holds false to the formula, we know that there are too many i Q s.2.4 Algorithm of finding all possible schedulesFinding possible schedules is a process of trial and error, which is meant to include both successes and failures. However, in order to reduce the mass of calculation, we hope to obtain all solutions with the least number of failures. To achieve this, we can determine the relatively inflexible times first, and leave the flexible ones for permutations later.Since o N t , the number of possible ways to arrange scene o (regardless of all other scenes), is anindication of o N ’s flexibility in time, we can arrange all o N s by ascending order of o N t{}*****1231,,,......,,q q N N N N N -This arrangement enables us to settle these scenes in an efficient order.Then we use backtracking algorithm to find all of i Q .In fact, the finding process is like finding all**1q N N path -s in a directed graph:First, we choose one *o N . Then we pick oneof the available choices of *1o N +. If wecannot find a *1o N +, which means that thechosen *o N is unfeasible, we will go backto the last order and find another *o N . Wewill continual to repeat this procedure untilwe get a complete **1q N N path -. Everytime we obtain a path, we record it and go back to the last order.Even though the crotches of tree are numerous and unknown, we have promised the least number of crotches by arranging o N by o N t . After reducing a large amount of computations, the newlyderived *o N is suitable for finding i Q .2.5 Algorithm of finding the best scheduleAfter all possible schedules are found, we need to evaluate each of them to find the top solutions. First, we have to follow the restrictions in E . If i Q does not accord with p E , it should be eliminated from our consideration.Second, we need to assess how good i Q is. In an optimal situation, we can assume a numerical relationship among several variables:min min i i i i x T y z T P q a ---» (2.5-1)i x is the whole time span of i Q , while min T is the real shooting time, and i q and a are the time spent on transportations and constructions. Therefore, the left side of the equation stands for the actual flexible time ready to deal with delays and reshoots, which is expected to be min PT Based on formula (11), we introduce a new index ()i S Q :min min min ()()=ln i i i i i T P x T y z S Q T Pq a ----() (2.5-2) The function ()i S Q , a characteristic value, indicates the superiority of each i Q . The less ()i S Q is, the more orderly i Q is, and the better the schedule is.In the best solution whose free time is just appropriate, min min ()=0i i i i T P x T y z q a ----, and ()-i S Q ®¥.If free time is too little, and flexible days are just enough to cover the penalty time (time spent on transportations and constructions) but not enough to compensate for delays and reshoots, we will have min ()0i i i i x T y z q a ---=, and ()0i S Q =.If free time is too much, and the time for delays and reshoots are twice as much as needed, we will have min min ()2T i i i i x T y z P q a ---=, the characteristic value ()i S Q also equals to 0. Eventhough the two cases above are different, they are both considered as mediocre choices, and their()i S Q values are the same.2.6 Adjustment for accidentsIf the clients encounter an accident that cannot be solved by existing flexible days (for example, significant delays in one aspect or the availability of some asset changes) during the filming process, we can provide a model for them to rearrange the future plan. The rearrangement can be achieved through a similar program, so they could quickly obtain the new schedule after changing some basic information and running the program.This adjustment is based on information in several aspects:1) The change in constraints (if any). For example, if the delay is caused by change in availability of an actor, a site or a resource, the new available time must be known.2) The present achievements. Since some tasks are already finished, the schedule before the present day cannot change anymore.3) The future dates that are hard to change. Some appointments with actors and specific resources (such as a helicopter) cannot be cancelled or changed, so the related scenes have to stay at the same date.After these information are entered, the program will add new constraints {}****123,,,......,r A A A A and the unchangeable scenes {}''''123,,,......,r N N N N (unchangeable scenes will be considered as “Invisible actors”, and the detailed procedure is discussed in 2.2) and give solution based on the new circumstances. Therefore, if these information are known, the program can provide an optimal future schedule for the clients when an accident happens.3 Programming Approach3.1 Overview of the programBased on our model, we developed a computer program that is capable of generating possible schedules as well as determining the priority of each schedules according to their characteristic values and sorting them by the priority in descending order.3.2 Introduction of the program3.2.1 InputsOur program contains a function that can read an Excel file so that it is very convenient for clients to input data. The Excel has 6 sheets which contain the information of actors, places, sets, scenes and two kinds of restrictions.The input function named ‘Read’ works by transferring information in Excel into four variables (Data form: double) named Ifm_Actors, Ifm_Places, Ifm_Sets, Ifm_Scenes and Cmd_Time.3.2.2 Algorithm of finding3.2.2.1 Preliminary filteringFirst of all, the program will check whether a possible solution exists. If there’s obviously no possible solution3, it will display an error and terminates the program.3.2.2.2 Estimation and tipsUse the formula (10) to determine whether the restrictions are too loose so that the quantity of possible schedules might be too large. If the case holds false to the formula, the program would display a warning.3.2.2.3 Searching for possible schedulesThe program generates 0-1 matrixes Ifm_Actors, Ifm_Places, Ifm_Sets and Ifm_Scenes with 1 representing available days and 0 representing occupied days. In this way we can figure out the intersection of available time by multiplying the correspondent row.Then, by rearranging the 0-1 matrix in order of the method that was mentioned in 2.4, the computational complicity is significantly reduced.Finally, we use the backtracking method to search for all possible schedules within the 0-1 matrix. Solutions are saved in variable All_Solutions (data form: cell).During the searching, if the number of solutions is too large, the program simply stops searching when 1000 solutions are recorded.3.2.3 Algorithm of filteringAfter generating all solutions, our program will follow time restrictions to delete those solutions that don’t fit in. Then, the program determines the changing times of places and sets, and calculates the characteristic values with function (12) to judge whether a solution is practical enough. The solutions are rearranged according to their characteristic values.3 For example, if the schedules of two actors who cooperate in a specific scene do not have intersection, the scene obviously cannot be shot.3.2.4 OutputsFinally, the output function of the program creates an Excel file and writes 11 possible scheduleswith the top priority in four different criteria. They include 5 overall best schedules, 2 scheduleswith least number of location changes, 2 schedules with least number of studios, and 2 scheduleswith least number of shooting days. In each schedule, scenes are arranged chronologically.4. Case Analysis4.1 Overview of the caseFor most movies, the detailed information about the preparing process are not open to public,which makes it hard to find a realistic case to test our model. However, we gathered some basicfacts about film shooting from internet and libraries, and used them to create a mostly reliable caseto test our model.This movie tells the stories of a group of physicists. It contains 18 roles, 9 sites, 11 settings, and 29 scenes. The studio wants the whole filming to be finished within 60 days. They also give some constraints, which are all displayed as below.4.1.1 Roles and the available times of their actorsThe following chart displays all the roles included in the film and the available dates of theiractors:Role Available dates of actorRydberg 13-14 Thomson 26-2824-25,29-30 Rutherford 1-5,29-30 Chadwick 4-5,Planck 11-12, 16-17, 23, 29-30Bohr 1-3,7,9,26-28, 34-35, 51-54Landau 21 Fermi 41-50 Oppenheimer 22, 41-47, 51-52Feynman 44-4734-35 Schrödinger 18-20,34-35 Compton 24-25,De Broglie 34-35, 40-60Einstein 6, 8, 16, 17, 21, 34-40Heisenberg 7-9, 23, 31-36, 53-60Dirac 31-35,51-52 Pauli 10,34-35 Born 10,19-20,34-35 4.1.2 ScenesThe following chart displays all the scenes in the film, the locations of and roles in them, and thetime needed to shoot them. There are two types of locations, sites and settings, which will bespecifically discussed in following paragraphs.Scene Location Roles Time(day)Solvay Conference Brussels Einstein, Bohr, Planck, Dirac,Born, Pauli, Schrödinger,Compton, De Broglie, Heisenberg2Experiment 1 Lab 1 Rydberg, Bohr 2 Experiment 2 The University of Manchester Rutherford, Bohr 3 Experiment 3 The University of Cambridge Thomson, Chadwick 3 Story 1 The University of Manchester Rutherford, Chadwick 2 Story 2 The University of Cambridge Rutherford, Einstein 2 Story 3 Humboldt University of Berlin Planck, Einstein 2 Story 4 Auditorium 1 Landau 1 Story 5 The University of Chicago Fermi, Oppenheimer, Feynman 4 Story 6 The University of Cambridge Dirac, Heisenberg 2 Story 7 Humboldt University of Berlin Schrödinger 1 Story 8 House 1 Einstein, Heisenberg 1 Story 9 House 2 Planck, Heisenberg 1 Story 10 Auditorium 2 Einstein 1 Story 11 Meeting room 1 Einstein 1 Experiment 4 University of Copenhagen Dirac, Bohr, Oppenheimer 2 Experiment 5 Lab 2 Compton, Rutherford 2 Story 12 Auditorium 2 Heisenberg, Bohr 1 Story 13 University of Copenhagen Heisenberg, Bohr 2 Story 14 University of Göttingen Pauli, Born 1 Experiment 6 Lab 3 Planck 2 Story 15 Meeting room 2 Heisenberg, Bohr 1 Story 16 Princeton University Einstein 2 Story 17 House 1 Einstein 2 Story 18 Humboldt University of Berlin Schrödinger, Born 2 Story 19 House 3 Oppenheimer 1 Story 20 Lab 4 Oppenheimer, Fermi 2 Story 21 National Library Fermi 3 Story 22 University of Copenhagen Heisenberg 24.1.3 Available time of sitesFor some specific reasons, a few sites cannot be shot all the time. The following chart displays theavailable dates of each site:date Place Available University of Copenhagen 50-60Humboldt University of Berlin 15-20Brussels 1-60 The University of Manchester 1-7The University of Cambridge 25-33The University of Chicago 44-60University of Göttingen 1-57Princeton University 1-42National Library 48-604.1.4 Preparation time of settingsThe time of preparation for settings is a determinant of the number of filming studios. Thefollowing chart displays this preparation time:time(day) Set PreparationHouse 1 4House 2 3House 3 6Meeting room 1 0Meeting room 2 0Lab 1 0Lab 2 0Lab 3 0Lab 4 0Auditorium 1 0Auditorium 2 0We assume in this way because compared to filming in meeting rooms, labs and auditoriums, it isharder to film in a realistic house (For example, a high filming position cannot be reached).Therefore, we must build some “houses” in the filming studio, which requires several days toprepare.4.1.5 Restriction of specific ordersThe studio also requires some specific orders of scenes to be shot:“Story 20” must go after “Experiment 1”.“Story 13” must go after “Experiment 5”, and “Experiment 5” must go after “Experiment 2”.。