СУДЬБЫ И СЕМИНАРЫ

О семинаре «Проблемы сокращения перебора» в ЛЭТИ в историко-научном контексте.

  • Сергей Владимирович Соловьев 1 Тулузский исследовательский институт по информационным технологиям (IRIT), университет Тулузы-3, 118, Нарбоннская дорога, 31062, Тулуза, Франция
Ключевые слова: история науки, научная жизнь Ленинграда 1980-х, проблемы сокращения перебора, итерационный метод Маслова

Аннотация

В работе рассматривается история семинара «Проблемы сокращения перебора» в ЛЭТИ, организованного Р.И. Фрейдзоном (1942-2018). Семинар начал свою работу в 1982 г., ставя в первую очередь своей целью развитие идей С.Ю. Маслова (1939-1982), и действовал до начала 1990-х годов. Историко-научный контекст, рассматриваемый в работе, включает связи этого семинара с другими семинарами – семинаром С.Ю. Маслова, семинаром по математической логике в ЛОМИ им. В.И. Стеклова, круг идей, рассматривавшихся на семинаре и основные результаты его дейстельности, выразившиеся в научных публикациях его участников. Рассматриваются также научно-педагогические аспекты деятельности семинара (его роль в формировании молодых ученых), организационная деятельность Р.И. Фрейдзона, и влияние его личности на творческую атмосферу, окружавшую семинар.

Биография автора

Сергей Владимирович Соловьев, 1 Тулузский исследовательский институт по информационным технологиям (IRIT), университет Тулузы-3, 118, Нарбоннская дорога, 31062, Тулуза, Франция

кандидат физико-математических наук, профессор университета Тулузы-3, научно-инженерный факультет, отделение информатики, Тулузуский исследовательский институт по информационным технологиям (IRIT), Sergei.Soloviev@irit.fr

Литература

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).

Опубликован
2019-12-28
Как цитировать
Соловьев, С. В. (2019). СУДЬБЫ И СЕМИНАРЫ. Компьютерные инструменты в образовании, (4), 5-14. https://doi.org/10.32603/2071-2340-2019-4-5-14
Выпуск
Раздел
Алгоритмическая математика и математическое моделирование