СУДЬБЫ И СЕМИНАРЫ
О семинаре «Проблемы сокращения перебора» в ЛЭТИ в историко-научном контексте.
Аннотация
В работе рассматривается история семинара «Проблемы сокращения перебора» в ЛЭТИ, организованного Р.И. Фрейдзоном (1942-2018). Семинар начал свою работу в 1982 г., ставя в первую очередь своей целью развитие идей С.Ю. Маслова (1939-1982), и действовал до начала 1990-х годов. Историко-научный контекст, рассматриваемый в работе, включает связи этого семинара с другими семинарами – семинаром С.Ю. Маслова, семинаром по математической логике в ЛОМИ им. В.И. Стеклова, круг идей, рассматривавшихся на семинаре и основные результаты его дейстельности, выразившиеся в научных публикациях его участников. Рассматриваются также научно-педагогические аспекты деятельности семинара (его роль в формировании молодых ученых), организационная деятельность Р.И. Фрейдзона, и влияние его личности на творческую атмосферу, окружавшую семинар.Литература
S. V. Soloviev, “Seminar na poslednem etazhe” [Seminar on the Last Floor], Zvezda, no. 3, pp. 177–196, 2019 (in Russian).
D. A. Pospelov, G. E. Mints, and R. I. Freidson eds., “Problemy sokrashcheniya perebora” [Problems of Reducing Exhaustive Search], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987 (in Russian).
R. I. Freidson, “Algoritmika perebornykh zadach” [Algorithmics of exhaustive search], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, pp. 3–6, 1987 (in Russian).
V. Kreinovich and V. G. Mints eds., “Problems of Reducing the Exhaustive Search,” AMS Translations, ser. 2, vol. 178, 1997.
E. Ya. Dantsin and V. Ya. Kreinovich, “Veroyatnostnyi vyvod v sistemakh prognozirovaniya” [Probabilistic deduction in forecasting systems], Doklady Akademii Nauk SSSR, vol. 307, no. 1, 1989 (in Russian).
M. A. Vsemirnov et al., “Nikolai Aleksandrovich Shanin (nekrolog)” [Nikolay Aleksandrovich Shanin (obituary)], Uspekhi Mathematicheskikh Nauk, vol. 68, no. 4(412), pp. 173–176, 2013 (in Russian).
S. Yu. Maslov, “Iterativnye metody v perebornoi modeli, kak model’ intuitivnykh” [Iterative methods in intractable problems as a model of intuitive methods], in Abstracts of 9-th All-Union symposium on Cybernetics, Sukhumi, USSR, 1981, pp. 26–28 (in Russian).
S. Yu. Maslov, “Asimmetriya poznavatel’nykh mekhanizmov i ee sledstviya” [Asymmetry of cognitive mechanisms and its implications], Semiotics and Information Science, vol. 20, pp. 3–31, 1983 (in Russian).
S. Yu. Maslov, “Ischisleniya s monotonnymi vyvodami i ikh ekonomicheskaya interpretatsiya” [Calculi with monotone deductions and their economic interpretation], Zapiski Nauchnych Seminarov LOMI, vol. 88, pp. 90–105, 1979 (in Russian).
V. Ya. Kreinovich, “Semantika interaktivnogo metoda S. Yu. Maslova” [Semantics of interactive method of S. Yu. Maslov], Voprosy Kibernetiki, Moscow: Nauka, vol. 131, pp. 30–62, 1987 (in Russian).
M. I. Zakharevich, “Ergodicheskie svoistva iteratsionnogo metoda S. Yu. Maslova” [Ergodic properties of the iterative method of S. Yu. Maslov], Ibid., pp. 63–75, 1987.
I. V. Melichev, “Anomal’nye svoistva iteratsionnogo metoda S. Yu. Maslova” [Anomalous properties of the iterative method of S. Yu. Maslov], Ibid., pp. 76–86.
E. Ya. Dantsin, “Algoritmika zadachi vypolnimosti” [Algorithmics of the satisfiability problem], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 7–29 (in Russian).
S. M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, “DeepFool: A simple and accurate method to fool deep neural networks,” in Proc. of IEEE Conf. on computer vision and pattern recognition, Las Vegas, NV, 2016, pp. 2574–2582.
R. Williams, “Improving exhaustive search implies super polynomial lower bounds,” in Proc. of the 42nd Annu. ACM Symp. on Theory of Computing (STOC–2010), 2010, pp. 231–240; Journal version: SIAM J. Comput., vol. 42, no. 3, pp. 1218–1244, 2013; doi: 10.1137/10080703X
R. Williams, “Non-uniform ACC circuit lower bounds,” in Proc. of the 26th Annu. IEEE Conf. on Computational Complexity (CCC–2011), 2011, pp. 115–125; Journal version: JACM, vol. 61, no.1, pp. 2:1– 2:32, 2014; doi: 10.1145/2559903
R. Williams, “Algorithms for circuits and circuits for algorithms: Connecting the tractable and intractable,” in Proc. of the Int. Congr. of Mathematicians (ICM 2014), vol. 4, 2014, pp. 659–682.
G. V. Davydov and I. M. Davydova, “Dvoistvennye algoritmy v diskretnoi optimizatsii” [Dual algorithms in discrete optimization], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 90–117 (in Russian).
Yu. V. Matiyasevich, “Possible nontraditional methods of establishing the satisfiability of propositional formulas,” in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 87–89 (in Russian).
A. Ya. Dikovsky, “Modeli, metody i rezhimy sinteza skhem programm” [Models, methods and modes for the synthesis of program schemes], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 117–148 (in Russian).
N. K. Kossovskii, “Nizhnyaya granitsa skhemnoi slozhnosti pri sokrashchenii eksponentsial’nogo perebor” [Lower bounds of combinatorial complexity for exponential search reduction], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 167–179 (in Russian).
An. A. Muchnik, “Ob odnom klasse polinomial’nykh sistem uravnenii, vytekayushchikh iz formuly polnoi veroyatnosti, i vozmozhnosti ustraneniya perebora pri ikh resheniia” [On a class of polynomial systems of equations following from the formula for total probability and possibilities for elimination search in solving them], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 180–195 (in Russian).
M. I. Kanovich, “Effektivnye ischisleniya kak sredstvo sokrashcheniya perebora” [Effective calculi as a technique for search reduction], in Voprosy Kibernetiki, Moscow: Nauka, vol. 131, 1987, pp. 149–166 (in Russian).
B. A. Kushner, “The Teacher (To the centennial of A.A. Markov, Jr.),” in From the History of Cybernetics, Ya. Fet, ed., Novosibirsk: Geo Academic Publishers, 2006, pp. 189–262 (in Russian).
Материал публикуется под лицензией: