tailieunhanh - Lecture Discrete mathematics and its applications - Lecture 11

This chapter define the term average access time and describe how it is measured, explain why file compression is a factor in drive performance, define the term data transfer rote and describe how it is measured, explain two steps you can take to optimize the performance of your computer’s hard disk, identify four drive interface standards commonly used in PCs. | Advanced Counting Techniques Chapter 8 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Applications of Recurrence Relations Solving Linear Recurrence Relations Homogeneous Recurrence Relations Nonhomogeneous Recurrence Relations Divide-and-Conquer Algorithms and Recurrence Relations Generating Functions Inclusion-Exclusion Applications of Inclusion-Exclusion Applications of Recurrence Relations Section Section Summary Applications of Recurrence Relations Fibonacci Numbers The Tower of Hanoi Counting Problems Algorithms and Recurrence Relations (not currently included in overheads) Recurrence Relations (recalling definitions from Chapter 2) Definition: A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, , an-1, for all integers n with n ≥ n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. Rabbits and the Fiobonacci Numbers Example: A young pair of rabbits (one of each gender) is placed on an island. A pair of rabbits does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits on the island after n months, assuming that rabbits never die. This is the original problem considered by Leonardo Pisano (Fibonacci) in the thirteenth century. Rabbits and the Fiobonacci Numbers (cont.) Modeling the Population Growth of Rabbits on an Island Rabbits and the Fibonacci Numbers (cont.) Solution: Let fn be the the number of pairs of rabbits after n months. There are is f1 = 1 pairs of . | Advanced Counting Techniques Chapter 8 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Applications of Recurrence Relations Solving Linear Recurrence Relations Homogeneous Recurrence Relations Nonhomogeneous Recurrence Relations Divide-and-Conquer Algorithms and Recurrence Relations Generating Functions Inclusion-Exclusion Applications of Inclusion-Exclusion Applications of Recurrence Relations Section Section Summary Applications of Recurrence Relations Fibonacci Numbers The Tower of Hanoi Counting Problems Algorithms and Recurrence Relations (not currently included in overheads) Recurrence Relations (recalling definitions from Chapter 2) Definition: A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0, a1, , an-1, for all integers n .