2-INF-113 Kombinatorická analýza (2)
| Odporúčaný ročník: | 1. |
| Semester: | zimný |
| Rozsah: | P4 |
| Hodnotenie: | 0/100 |
| Počet kreditov: | 6 |
| Vyučujúci: | prednáša doc. RNDr. Daniel Olejár PhD. |
| www stránka: |
Cieľ:
Zvládnutie metód konštrukcie asymptotických odhadov a využitie generujúcich funkcií.
Sylabus:
Význam odhadov. O-notácia. Narábanie s výrazmi obsahujúcimi O. Základné metódy konštrukcie asymptotických odhadov: vyňatie hlavnej časti, boot-strapping; odhady súm. Eulerova-McLaurinova sumačná formula. Príklady. Generujúce funkcie – obyčajné a exponenciálne. Kalkul generujúcich funkcií. Konvolúcie. Použitie generujúcich funkcií na enumerácie diskrétnych objektov. Riešenie rekurentných vzťahov pomocou GF. Analytická teória GF.
Literatúra:
Knuth D., Graham R., Patashnik O.: Concrete mathematics, Addison Wesley 1994
Wilf H., S.: Generatingfunctionology, Academic Press, 1994
Sedgewick R., Flajolet Ph.: An introduction to the Analysis of Algorithms, Addison Wesley, 1996