Kordamisküsimused

Kursus ITT0030: "Diskreetne matemaatika II"



  1. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega.
  2. Hulga võimsus. Kontiinumhüpotees.
  3. Järjendid. Permutatsioonid. Kombinatsioonid.
  4. Binoomi valem. Pascali kolmnurk.
  5. Liitmis- ja korrutamisreegel kombinatoorikas.
  6. Kordustega permutatsioonid. Multinoomkordajad.
  7. Elimineerimismeetod (juurde- ja mahaarvamise valem).
  8. Korratused ja subfaktoriaalid.
  9. Dirichlet‘ printsiip.
  10. Arvujadade genereerivad funktsioonid. Jadade ja genereerivate funktsioonide teisendamine.
  11. n objekti jaotamine k gruppi.
  12. Rekurrentsed võrrandid. Rekurrentsi lahendamine ad hoc meetodil ja iteratsioonimeetodil.
  13. Tasandi tükeldamine n sirgega ja n nurgaga.
  14. Lineaarsed rekurrentsed võrrandid.
  15. Rekurrentsete võrrandite lahendamine genereerivate funktsioonide meetodil.
  16. Fibonacci arvud. üldliikme valem ja rakendused.
  17. Lucas‘ arvud.
  18. Catalani arvud.
  19. Sündmused ja tõenäosus. Statistiline tõenäosus. Bernoulli suurte arvude seadus.
  20. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis.
  21. Täistõenäosuse valem. Bayesi reegel.
  22. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral).
  23. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel.
  24. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne.
  25. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud.
  26. Eukleidese algoritm.
  27. Lineaarsed diofantilised võrrandid.
  28. Täisarvude kongruentsid. Kongruentsi omadusi.
  29. Moodularitmeetika.
  30. Algarvulisuse Fermat‘ test. Miller-Rabini test.
  31. Graafid ja graafide omadused. Ahelad ja tsüklid graafis.
  32. Euleri graafid. Hamiltoni tsüklid.
  33. Puud. Puude omadused.
  34. Graafi vähima kaaluga aluspuud.
  35. Märgendatud puud. Puude esitamine arvuti mälus.
  36. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem.
  37. Märgendamata puude arv.
  38. Kooskõlad graafis. Berge’i teoreem.
  39. Kooskõlad kahealuselises graafis. Halli teoreem.
  40. Dijkstra lühima tee algoritm.
  41. Ford-Fulkersoni algoritm maksimaalse voo leidmiseks.
  42. Tasandiline graaf. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Eulri valemi rakendusi.
  43. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem (tõestuseta).
  44. Graafi tippude värvimise ülesanne. Brooksi teoreem.
  45. Tasandilise lihtgraafi värvimine 6 ja 5 värviga. Neljavärviprobleem ja kaartide värvimine.
  46. Welch-Powelli graafi värvimise algoritm.