tailieunhanh - Lecture Discrete structures: Chapter 9 - Amer Rasheed

This chapter includes contents: Uses a explicit linear ordering, insertions and removals are performed individually, there are no restrictions on objects inserted into (pushed onto) the queue that object is designated the back of the queue,. This topic discusses the concept of a stack: Description of an Abstract Stack, list applications, implementation, example applications, standard template library. | (CSC 102) Lecture 9 Discrete Structures Previous Lectures Summary Statements containing “∀ ” and “∃” Nested Quantifiers Relations Universal Instantiation statement Universal Modus Ponens Universal Modus Tollens Quantified form of Converse and Inverse error Elementary Number Theory Today's Lecture Divisors Prime Numbers Fundamental Theorem of Arithmetic Division Algorithm Greatest common divisors Least Common Multiple Relative Prime Divisors DEF: Let a, b and c be integers such that a = b·c Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol “|” denotes “divides” so the situation is summarized by b | a c | a. NOTE: Symbolically if a and b are integers and k is not equal to zero, an integer such Which of the following is true? 77 | 7 7 | 77 24 | 24 0 | 24 24 | 0 Solution 77 | 7: false bigger number can’t divide smaller positive number 7 | 77: true because 77 = 7 · 11 24 | 24: true because 24 = 24 · 1 0 | 24: false, 24 | 0: true, 0 is divisible by every number (0=24·0) Examples How many positive multiples of 15 are less than 100? Answer: Just list them 15, 30, 45, 60, 75, 90. Therefore the answer is 6. How many positive multiples of 15 are less than 1,000,000? Formula for Number of Multiples up to given N Cont Listing is too much of a hassle. Since 1 out of 15 numbers is a multiple of 15, if 1,000,000 were divisible by 15, answer would be exactly 1,000,000/15. However, since 1,000,000 isn’t divisible by 15, need to round down to the highest multiple of 15 less than 1,000,000, so answer is remainder of 1,000,000/15 In general: The number of d-multiples less than N is given as: {m Z+ | d |m and m N }. Divisor Theorems Theorem: Let a, b, and c be integers. Then a | b a| c a|(b + c ) a| b a| a| b b| c a| c. (Transitive Property) Examples 17|34 17|170 17|204. 17|34 17|340. 6|12 12|144 6|144. Proof of the Theorem In general, such statements are proved by starting . | (CSC 102) Lecture 9 Discrete Structures Previous Lectures Summary Statements containing “∀ ” and “∃” Nested Quantifiers Relations Universal Instantiation statement Universal Modus Ponens Universal Modus Tollens Quantified form of Converse and Inverse error Elementary Number Theory Today's Lecture Divisors Prime Numbers Fundamental Theorem of Arithmetic Division Algorithm Greatest common divisors Least Common Multiple Relative Prime Divisors DEF: Let a, b and c be integers such that a = b·c Then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol “|” denotes “divides” so the situation is summarized by b | a c | a. NOTE: Symbolically if a and b are integers and k is not equal to zero, an integer such Which of the following is true? 77 | 7 7 | 77 24 | 24 0 | 24 24 | 0 Solution 77 | 7: false bigger number can’t divide smaller positive number 7 | 77: true because 77 = 7 · 11 24 | 24: true because 24 = 24 · 1 0 | 24: .