Shahada ya kwanza (mwanzo)Discrete MathematicsImepangwa
Recurrences and generating functions
Recurrence relations such as the Fibonacci recurrence, solving linear recurrences, ordinary generating functions and asymptotic notation.
math.discrete.recurrences-generating-functions
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 28 (hadi chini kabisa)
Utajifunza
- Solve linear recurrences with constant coefficients using characteristic polynomials.
- Use generating functions to solve recurrences and counting problems.
- Compare growth rates using O, Ω and Θ notation.
Fasili
- The ordinary generating function of a sequence (aₙ) is the formal power series Σ aₙxⁿ.
- f(n) = O(g(n)) means |f(n)| ≤ C|g(n)| for some constant C and all sufficiently large n.
Nadharia
- Binet's formula: with F₀ = 0 and F₁ = 1, Fₙ = (φⁿ − ψⁿ)/√5 where φ = (1 + √5)/2 and ψ = (1 − √5)/2.
- The Catalan numbers C(2n, n)/(n + 1) count, among many other things, balanced sequences of n pairs of brackets.
Mawazo potofu ya kawaida
- Thinking formal power series must converge to be useful.
- Reading big-O as an exact count rather than an upper bound up to a constant.
Inaelekea kwa
Ugunduzi wa hiari
- Algorithms, correctness and efficiency Recurrences describe the running time of recursive algorithms; mergesort satisfies T(n) = 2T(n/2) + O(n), so T(n) = O(n log n).
Usomaji zaidi
- Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics (1989)
- Herbert S. Wilf, generatingfunctionology (1990)