Paskaitų kurso programa

TYRIMŲ OBJEKTAI

1. Binarieji medžiai. Katalano skaičiai.
2. Vidutinis kelio ilgis greitojo rūšiavimo algoritme.
3. Aibės skaidiniai poaibiais. Belo skaičiai.
4. Natūraliojo skaičiaus adityvieji skaidiniai.
5. Simetrinė grupė. Keitinių ciklinė struktūra ir jungtinių elementų klasės.
6. Polinomai virš baigtinio kūno. Pirminių polinomų kiekis.
7. Baigtinių aibių atvaizdžiai ir funkciniai digrafai.
8. Skaidumo sandaugos. Generuojančių funkcijų sąryšiai.
9. Ansamblio sąvoka. Jo eksponentinė generuojanti funkcija.
10. Atrankos. Jų generuojančios funkcijos.
11. Kartotinės atrankos. Jų generuojančios funkcijos.

1. Struktūros vektoriaus skirstinys ir sąlyginės tikimybės.
2. "Kinų restorano" problema.
3. Atsitiktinio keitinio ciklų struktūros vektorius.
4. Ciklo kiekio asimptotinis skirstinys. Gončarovo teorema.
5. Atsitiktinių keitinių generavimas.
6. Felerio poravimas. Ciklų kiekio išraiškos Bernulio dydžiais.
7. Atstumo pagal tikimybinių matų variaciją įvertis.
8. Sąlyginių tikimybių įverčiai per besąlygines tikimybes.
9. Didžiųjų skaičių dėsnis adityviosioms simetrinės grupės funkcijoms.
10. Centrinė ribinė teorema.
11. Kartotinės atrankos struktūros vektoriaus asimptotinis skirstinys.
12. Komponenčių kiekio momentų konvergavimas.
13. Atrankų tikimybiniai uždaviniai.

KNYGOS

1. P.J.Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge Univ. Press, 1994.
2. N. L. Johnson & S. Kotz, Urn Models and Their Applications, John Wiley, New York, 1977.
3. V.F.Kolčin, Atsitiktiniai atvaizdžiai, Nauka, Maskva, 1984 (rusų k.).
4. V.N.Sačkov, Įvadas į kombinatorinius diskrečios matematikos metodus, Nauka, Maskva, 1982 (rusų k.).
5. V.\ N.\ Sachkov, Probabilistic Methods in Discrete Mathematics, Cambridge University Press, 1995.
6. V.\ N.\ Sachkov, Probabilistic Methods in the Combinatorial Analysis, Cambridge University Press, 1997.
7. H.S.Wilf, Generatingfunctionology, Academic Press, San Diego, 2nd edition, 1994.

STRAIPSNIAI

1. R. Arratia and S. Tavare, Independent process approximations for random combinatorial structures, Advances in Math., 104 (1994), 1, 90--154.
2. P. Flajolet, A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3(1990), 2, 216--240.
3. P. Flajolet, A. Odlyzko, Random mapping statistics, Lecture Notes in Computer Science. Advances in Cryptology - EUROCRYPT'89 (J.-J.Quisquater, J.Vandewalle, Eds), 434(1990), 329--354.
4. H.-K.Hwang, Theoremes limites pour les structures combinatoires et les fonctions arithmetiques, These, Ecole Plolytechnique, Paris, 1994.
5. E.Manstavičius, Adityviosios ir multiplikatyviosios atsitiktinių keitinių funkcijos, Lietuvos matem. rink., 36(1996), 4, 501--510 (rusų k.).
6. E.Manstavičius, Atsitiktinių keitinių kartotinio logaritmo dėsnis, Lietuvos matem. rink., 38(1998), 2, 205--220 (rusų k.).
7. A.M.Odlyzko, Asymptotic enumeration methods, In: Handbook of Combinatorics (R.L.Graham et al Eds), vol II, Elsevier, Amsterdam, 1995, 1063--1229.
8. D.Stark, Total variation asymptotics for independent process approximations of logarithmic multisets and selections, Random Structures and Algorithms, 11(1997), 1, 51--80.
9. D.Stark, Explicit limits of total variation distance of random logarithmic assemblies by related Poisson process, Combinatorics, Probab. and Computing , 6(1997), 87--105.
10. J.S.Vitter, Ph.Flajolet, Average-case analysis of algorithms and data structures, In: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed),Elsevier, Amsterdam, 1990, 433--524.

Pradinis puslapis | Main page