The Chair of Discrete Mathematics

V. V. Kochergin   ; N. P. Red'kin   ; S. B. Gashkov   ; A. V. Chashkin   ; R. M. Kolpakov   ; M. D. Kovalev   ; Yu. V. Tarannikov   ; O. S. Dudakova   ; Yu. A. Kombarov   ; M. V. Starostin   ; S. A. Korneev

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 6 (2024), pp. 38-49

Résumé

The paper about the Chair of Discrete Mathematics of the Faculty of Mechanics and Mathematics of Lomonosov Moscow State University discusses the issues of interpretation of the term “discrete mathematics”, the formation and rapid development of discrete mathematics in the modern sense, and also provides information about the history of the Chair. In addition, a brief overview of the main recent results obtained at the Chair of Discrete Mathematics in the field of the theory of circuit complexity and computational complexity, the theory of discrete functions and functional systems, combinatorics, graph theory, discrete geometry and other areas of discrete mathematics is presented.

Bibliographie

[1] Lupanov O.B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, M., 1963, 63–97

[2] Lupanov O.B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, 2-e izd., ispr., Izd-vo MGU, M., 2024

[3] Lupanov O.B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, Nauka, M., 1965, 31–110

[4] Kochergin V.V., “O rabotakh O.M. Kasim-Zade v oblasti teorii slozhnosti i teorii mnogoznachnykh logik”, Chebyshev. sb., 23:2 (2022), 121–150 | DOI | MR | Zbl

[5] Kochergin V.V., “Zadachi Bellmana, Knuta, Lupanova, Pippendzhera i ikh variatsii kak obobscheniya zadachi ob additivnykh tsepochkakh”, Matematicheskie voprosy kibernetiki, 20, FIZMATLIT, M., 2022, 119–256

[6] Kochergin V.V., “O nemonotonnoi slozhnosti bulevykh funktsii i funktsii $k$-znachnoi logiki”, Matematicheskie voprosy kibernetiki, 22, FIZMATLIT, M., 2024, 51–151

[7] Redkin N.P., “Ob asimptotikakh dlya slozhnosti bulevykh funktsii s malym chislom edinits”, Matem. zametki, 109:2 (2021), 257–263 | DOI | Zbl

[8] Redkin N.P., “Dokazatelstvo nizhnikh otsenok slozhnosti samokorrektiruyuschikhsya skhem metodom zameny bazisa”, Vestn. Mosk. un-ta. Matem. Mekhan., 2010, no. 3, 14–18 | Zbl

[9] Gashkov S.B., “O slozhnosti priblizhennoi realizatsii nepreryvnykh funktsii skhemami i formulami v polinomialnykh i nekotorykh drugikh bazisakh”, Matematicheskie voprosy kibernetiki, 5, Nauka, M., 1995, 144–207 | MR

[10] Gashkov S.B., “O slozhnosti priblizhennoi realizatsii funktsionalnykh kompaktov v nekotorykh prostranstvakh i o suschestvovanii funktsii s zadannoi po poryadku slozhnostyu”, Fund. i prikl. matem., 2:3 (1996), 675–774 | MR | Zbl

[11] Chashkin A.V., “Asimptoticheskie otsenki srednei slozhnosti bulevykh funktsii”, Matematicheskie voprosy kibernetiki, 20, FIZMATLIT, M., 2022, 257–306

[12] Chashkin A.V., “O slozhnosti realizatsii bulevykh funktsii formulami”, Diskretn. analiz i issled. oper. Cer. 1, 2005, no. 2, 56–72 | MR | Zbl

[13] Kolpakov R.M., “O diskretnykh preobrazovaniyakh veroyatnostnykh raspredelenii”, Matematicheskie voprosy kibernetiki, 19, FIZMATLIT, M., 2019, 5–20

[14] Kolpakov R., Kucherov G., “Periodic structures in words”, The 3rd Lothaire Volume Applied Combinatorics on Words, Cambridge University Press, 2005, 399–442 | MR

[15] Kovalev M.D., “Geometricheskaya teoriya sharnirnykh ustroistv”, Izv. RAN. Ser. matem., 58:1 (1994), 45–70 | Zbl

[16] Kovalev M.D., “Formuly dlya chisla sobstvennykh elektromagnitnykh mod v mnogosloinom planarnom volnovode”, Fiz. osnovy priborostr., 2011, no. 1, 100–111 | DOI

[17] Baksova I.P., Tarannikov Yu.V., “Ob odnoi konstruktsii bent-funktsii”, Obozrenie prikl. i prom. matem., 27:1 (2020), 64–66

[18] Potapov V.N., Taranenko A.A., Tarannikov Yu.V., “An asymptotic lower bound on the number of bent functions”, Des. Codes Cryptogr., 92:3 (2024), 639–651 | DOI | MR | Zbl

[19] Dudakova O.S., “O klassakh funktsii $k$-znachnoi logiki, monotonnykh otnositelno mnozhestv shiriny dva”, Vestn. Mosk. un-ta. Matem. Mekhan., 2008, no. 1, 31–37 | MR | Zbl

[20] Dudakova O.S., “O strukture reshetki klassov chastichnykh monotonnykh funktsii mnogoznachnoi logiki”, Prikl. matem. i inform., 59, MAKS Press, M., 2018, 16–24

[21] Kombarov Yu.A., “Slozhnost i stroenie skhem dlya lineinykh funktsii”, Fund. i prikl. matem., 20:6 (2015), 147–153

[22] Kombarov Yu.A., “Skhema glubiny dva s ogranichennym vkhodnym vetvleniem dlya funktsii golosovaniya”, Vestn. Mosk. un-ta. Matem. Mekhan., 2018, no. 5, 58–60 | Zbl

[23] Starostin M.V., “Neyavno predpolnye klassy i kriterii polnoty v trekhznachnoi logike”, Vestn. Mosk. un-ta. Matem. Mekhan., 2018, no. 2, 56–59 | Zbl

[24] Starostin M.V., “O klassakh samodvoistvennykh funktsii, neyavno predpolnykh v $P_k$”, Vestn. Mosk. un-ta. Matem. Mekhan., 2022, no. 3, 40–45 | Zbl

[25] Korneev S.A., “O slozhnosti realizatsii sistemy iz dvukh monomov skhemami kompozitsii”, Diskretn. matem., 32:2 (2020), 15–31 | DOI

[26] Korneev S.A., “Ob asimptoticheskom povedenii funktsii shennonovskogo tipa, kharakterizuyuschikh slozhnost vychisleniya sistem monomov”, Uch. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 162:3 (2020), 300–310 | MR