1. Rekurence a základní metody řešení rekurencí: substituční metoda, iterační metoda 2. Redukce rekurencí na algebraické rovnice: homogenní lineární rekurence, charakteristický polynom, charakteristické kořeny 3. Speciální funkce: funkce dolní a horní celé části, logaritmy, binomické koeficienty, binomická věta 4. Asymptotika: asymptotická hierarchie, O-, Theta- a Omega-notace, relace mezi asymptotickými notacemi, manipulace s O-notací, asymptotika a rekurence: analýza algoritmů rozděl a panuj 5. Euklidův algoritmus a prvočísla: Euklidův algoritmus: největší společný dělitel, nejmenší společný násobek, rozšířený Euklidův algoritmus, analýza Euklidova algoritmu; prvočísla: Základní věta aritmetiky, Eratosthenovo síto, Eulerova funkce phi, Prvočíselná věta 6. Kongruence: zbytkové třídy modulo n, řešení lineárních kongruencí, Čínská věta o zbytcích, modulární umocňování, Malá Fermatova věta, Eulerova věta 7. Diskrétní logaritmy: primitivní kořeny, diskrétní logaritmus 8. Základní pojmy z teorie grafů: orientovaný a neorientovaný graf, vrcholy, hrany, incidence, stupně, reprezentace grafů: seznamy sousedů, matice sousednosti, matice incidence 9. Další vlastnosti grafů: sledy, tahy, cesty, cykly, souvislé komponenty, silně souvislé komponenty, vrcholová souvislost, hranová souvislost, isomorfismus, regularita, vrcholově symetrický graf, hranově symetrický graf, podgrafy, úplné grafy, bipartitní grafy, stromy, kostry grafu, rovinné grafy, Kuratowského věta, průměr grafu, multigrafy, hypergrafy 10. Párování a barvení v grafech: párování, perfektní párování, Hallova věta, Talleova věta, hranové barvení, Vizingova věta, vrcholové barvení, chromatické číslo 11. Cestování grafem: eulerovský tah, eulerovský graf, hamiltonovská cesta, hamiltonovský graf, prohledávání do šířky, prohledávání do hloubky, minimální kostra, Kruskalův algoritmus, Primův algoritmus, problém obchodního cestujícího 12. Stromy: strom, les, kořenový strom, hloubka stromu, uspořádaný strom, binární strom, reprezentace binárních stromů 13. Základy teorie složitosti: některé třídy složitosti: rozhodovací problém, třída P, třída NP; polynomiální redukce: NP-těžký problém, NP-úplný problém; výpočetně obtížné problémy teorie grafů
|
-
Demel, J. Grafy a jejich aplikace. 2019.
-
Graham, R. L., Knuth, D. E., Patashnik, O. Concrete Mathematics. Addison - Wesley Publishing Company, 1994.
-
Gruska, J. Foundations of Computing. International Thomson Computer Press, 1997.
-
Knuth, D. E. Umění programování, 1. díl, Základní algoritmy. Computer Press, a.s., Brno, 2008.
-
Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky. Karolinum, Praha, 2010.
-
Meyer, A., Chlipala, A. 6.042J Mathematics for Computer Science. Massachusetts Institute of Technology: MIT OpenCourseWare, 2015.
-
Rigo, M. Advanced Graph Theory and Combinatorics. ISTE Ltd and John Wiley & Sons, Inc., 2016.
|