В.И. Левенштейн: өмірі мен ғылыми еңбектері

Кіріспе

Ресейлік математик (1935–2017)

Владимир Иосифович Левенштейн (20 мамыр 1935 – 6 қыркүйек 2017) – ақпарат теориясы, қателерді түзету кодтары және комбинаторлық жобалау саласында зерттеулер жүргізген ресейлік және кеңестік ғалым. Басқа еңбектерімен қатар, ол 1965 жылы жасаған Левенштейн қашықтығы және Левенштейн алгоритмімен белгілі. 1958 жылы Мәскеу мемлекеттік университетінің математика және механика факультетін бітірген және содан бері Мәскеудегі Келдиш қолданбалы математика институтында жұмыс істеп келеді. Ол IEEE ақпарат теориясы қоғамының мүшесі болды. 2006 жылы «қателерді түзету кодтары теориясына және ақпарат теориясына, соның ішінде Левенштейн қашықтығына қосқан үлесі үшін» IEEE Ричард У. Хамминг медалімен марапатталды.

Өмір

Левенштейн 1958 жылы Мәскеу мемлекеттік университетін бітірді, онда механика-математика факультетінде оқыды. Бітірген соң М. В. Келдыш атындағы қолданбалы математика институтында жұмыс істеді.

Жарияланымдар

В. И. Левенштейн, Применение матриц Адамара к задаче в теории кодирования, Проблемы кибернетики, том 5, ГИФМЛ, Москва, 1961, 125–136. В. И. Левенштейн, О стабильном расширении конечных автоматов, Проблемы кибернетики, том 10, ГИФМЛ, Москва, 1963, 281–286. В. И. Левенштейн, О некоторых системах кодирования и самонастраивающихся машинах для декодирования сообщений, Проблемы кибернетики, том 11, ГИФМЛ, Москва, 1964, 63–121. В. И. Левенштейн, Автоматы декодирования, инвариантные относительно начального состояния, Проблемы кибернетики, том 12, ГИФМЛ, Москва, 1964, 125–136. В. И. Левенштейн, Бинарные коды, обеспечивающие синхронизацию и коррекцию ошибок, Тезисы кратких научных докладов Международного конгресса математиков, Секция 13, Москва, 1966, 24. В. И. Левенштейн, Асимптотически оптимальный бинарный код с коррекцией появлений одного или двух соседних символов, Проблемы кибернетики, том 19, Наука, Москва, 1967, 293–298. В. И. Левенштейн, О избыточности и замедлении разделяемого кодирования натуральных чисел, Проблемы кибернетики, том 20, Наука, Москва, 1968, 173–179. В. И. Левенштейн, Элементы теории кодирования, В книге: Дискретная математика и математические вопросы кибернетики, Наука, Москва, 1974, 207–305. VI Левенштейн, Методы получения оценок в метрических задачах теории кодирования, Труды совместного семинара IEEE СССР по теории информации, 1975, Нью-Йорк, 1976, 126–143. В. И. Левенштейн, О выборе полиномов для получения границ в задачах упаковки, VII Всесоюзная конференция по теории кодирования и передачи информации, Часть II, Москва – Вильнюс, 1978, 103–108. В. И. Левенштейн, Границы для упаковки метрических пространств и некоторые их приложения, Проблемы кибернетики, том 40, Наука, Москва, 1983, 43–110. VI Левенштейн, Упаковка полиномиальных метрических пространств, Третий международный семинар по теории информации, Сверточные коды; многопользовательская связь, Сочи, 1987, 271–274. VI Левенштейн, Совершенные коды с удалением, корректирующие ошибки, как комбинаторные конструкции, Труды Второго международного семинара: Алгебраическая и комбинаторная теория кодирования, Ленинград, СССР, 1990, 137–140. VI Левенштейн, Конструкции как максимальные коды в полиномиальных метрических пространствах, Acta Applicandae Mathematicae, vol. 29 (1992), 1–82. VI Левенштейн, Границы для самодополнительных кодов и их приложения, Eurocode 92. CISM Courses and Lectures, vol. 339, Springer Verlag, Wien – New York, 1993, 159–171. VI Левенштейн, Границы для кодов как решения экстремальных задач для систем ортогональных полиномов, Прикладная алгебра, Алгебраические алгоритмы и коды, исправляющие ошибки, Лекции по компьютерным наукам, vol. 673, Springer Verlag, 1993, 25–42. T. Эрикссон и VI Левенштейн, Наложенные коды в пространстве Хэмминга, IEEE Trans. Inform. Theory, vol. 40, no. 6 (1994), 1882–1893. G. Фазекас и VI Левенштейн, О верхних границах расстояния между кодами и радиуса покрытия конструкций в полиномиальных метрических пространствах, J. Combin. Th. Ser. A, vol. 70, no. 2 (1995), 267–288. T. Хеллесет, T. Клове, VI Левенштейн и O. Итрехус, Границы для минимальных весов опор, IEEE Trans. Inform. Theory, vol. 41, no. 2 (1995), 432–440. VI Левенштейн, Полиномы Краутчука и универсальные границы для кодов и конструкций в пространствах Хэмминга, IEEE Trans. Inform. Theory, vol. 41, no. 5 (1995), 1303–1321. VI Левенштейн, Восстановление бинарных последовательностей по минимальному числу их подпоследовательностей или суперпоследовательностей заданной длины, Материалы Пятого междунар. семинара по алгебраической и комбинаторной теории кодирования, Созополь, Болгария, 1–7 июня 1996 г., 176–183. VI Левенштейн, Нижние границы для апериодической перекрестной корреляции бинарных кодов, Материалы Четвертого междунар. симпозиума IEEE по методам широкополосного спектра и их применению, Майнц, Германия, 22–25 сентября 1996 г., 657–661. VI Левенштейн, Разделенные ортогональные матрицы и максимальные независимые устойчивые системы функций, Designs, Codes and Cryptography, vol. 12, no. 2 (1997), 131–160. T. Хеллесет, T. Клове и VI Левенштейн, О информационной функции кода, исправляющего ошибки, IEEE Trans. Inform. Theory, vol. 43, no. 2 (1997), 549–557. P. Делсарте и VI Левенштейн, Схемы ассоциаций и теория кодирования, IEEE Trans. Inform. Theory, vol. 44, no. 6 (1998), 2477–2504. VI Левенштейн, Универсальные границы для кодов и конструкций, в Справочнике по теории кодирования, под ред. VS Pless и WC Huffman, Амстердам: Elsevier, vol. 1, 499–648, 1998. VI Левенштейн, О конструкциях в компактных метрических пространствах и универсальной границе для их размера, Discrete Mathematics, vol. 192 (1998), 251–271. VI Левенштейн, О максимальных T-независимых системах булевых функций, Семинар по кодированию и криптографии, Париж, Франция, 1999, 367–370. VI Левенштейн, Эквивалентность границ Делсарта для кодов и конструкций в симметричных схемах ассоциаций и некоторые их приложения, Discrete Mathematics, vol. 197/198 (1999), 515–536. VI Левенштейн, Новые нижние границы для апериодической перекрестной корреляции бинарных кодов, IEEE Trans. Inform. Theory, vol. 45, no. 1 (1999), 284–288. ИН. АН. Левенштейн, О конструкциях в непрерывных единичных кубах, Материалы IV Международной конференции: Дискретные модели в теории систем управления, Московский государственный университет, Изд-во МАКС Пресс, 2000, 62–64. VI Левенштейн, Эффективное восстановление последовательностей, IEEE Trans. Inform. Theory, vol. 47, no. 1 (2001), 2–22. VI Левенштейн, Эффективное восстановление последовательностей по их подпоследовательностям или суперпоследовательностям, Journal of Combin. Theory, Ser. A, vol. 93, no. 2 (2001), 310–332. T. Бергер и VI Левенштейн, Асимптотическая эффективность двухступенчатого тестирования, IEEE Trans. Inform. Theory, vol. 48, no. 7 (2002), 1741–1749. T. Бергер и VI Левенштейн, Применение кодов, свободных от покрытия, и комбинаторных конструкций к двухступенчатому тестированию, Discrete Applied Mathematics. T. Хеллесет, T. Клове и VI Левенштейн, Гиперкубические 4 и 5 конструкции из кодов БЧ, исправляющих две ошибки, Designs, Codes and Cryptography. VI Левенштейн, Универсальная граница для покрытия в регулярных частично упорядоченных множествах и ее применение к пульному тестированию, Discrete Mathematics. VI Левенштейн, Комбинаторные задачи, мотивированные кодами, свободными от запятых, Discrete Mathematics.

V. I. Levenshtein, Application of Hadamard matrices to a problem in coding theory, Problems of Cybernetics, vol. 5, GIFML, Moscow, 1961, 125–136. V. I. Levenshtein, On the stable extension of finite automata, Problems of Cybernetics, vol. 10, GIFML, Moscow, 1963, 281–286. V. I. Levenshtein, On some coding systems and self tuning machines for decoding messages, Problems of Cybernetics, vol. 11, GIFML, Moscow, 1964, 63–121. V. I. Levenshtein, Decoding automata invariant with respect to the initial state, Problems of Cybernetics, vol. 12, GIFML, Moscow, 1964, 125–136. V. I. Levenshtein, Binary codes providing synchronization and correction of errors, Abstracts of short scientific reports of the International Congress of Mathematicians, Section 13, Moscow, 1966, 24. V. I. Levenshtein, Asymptotically optimal binary code with correction of occurrences of one or two adjacent characters, Problems of Cybernetics, vol. 19, Science, Moscow, 1967, 293–298. V. I. Levenshtein, On the redundancy and deceleration of separable coding of natural numbers, Problems of Cybernetics, vol. 20, Nauka, Moscow, 1968, 173–179. V. I. Levenshtein, Elements of coding theory, In the book. Discrete mathematics and mathematical questions of cybernetics, Nauka, Moscow, 1974, 207–305. VI Levenshtein, Methods for obtaining bounds in metric problems of coding theory, Proc. of the 1975 IEEE USSR Joint Workshop on Information Theory, New York, 1976, 126–143. V. I. Levenshtein, On the choice of polynomials for obtaining boundaries in packaging problems, VII All Union Conference on the Theory of Coding and Information Transfer, Part II, Moscow Vilnius, 1978, 103–108. V. I. Levenshtein, Borders for packaging of metric spaces and some of their applications, Problems of cybernetics, vol. 40, Science, Moscow, 1983, 43–110. VI Levenshtein, Packing of polynomial metric spaces, Third International Workshop on Information Theory, Convolutional codes; multi user communication, Sochi, 1987, 271–274. VI Levenshtein, Perfect deletion correcting codes as combinatorial designs, Proc. of the Second International Workshop: Algebraic and Combinatorial Coding Theory, Leningrad, USSR, 1990, 137–140. VI Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Applicandae Mathematicae, vol. 29 (1992), 1 82. VI Levenshtein, Bounds for self complementary codes and their applications, in Eurocode 92. CISM Courses and Lectures, vol. 339. Springer Verlag, Wien New York, 1993, 159–171. VI Levenshtein, Bounds for codes as solutions of extremum problems for systems of orthogonal polynomials, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Lectures Notes in Computer Science, vol. 673, Springer Verlag, 1993, 25–42. T. Ericson and VI Levenshtein, Superimposed codes in the Hamming space, IEEE Trans. Inform. Theory, vol. 40, no. 6 (1994), 1882–1893. G. Fasekas and VI Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces, J. Combin. Th. Ser. A, vol. 70, no. 2 (1995), 267–288. T. Helleseth, T. Klove, VI Levenshtein, and O. Ytrehus, Bounds on the minimum support weights, IEEE Trans. Inform. Theory, vol. 41, no. 2 (1995), 432–440. VI Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory, vol. 41, no. 5 (1995), 1303–1321. VI Levenshtein, Reconstructing binary sequences by the minimum number of their subsequences or supersequences of a given length. Proceedings of Fifth Intern. Workshop on Algebr. and Combin. Coding Theory, Sozopol, Bulgaria, June 1–7, 1996, 176–183. VI Levenshtein, Lower bounds on crosscorrelation of codes. Proceedings of IEEE Fourth Intern. Symp on Spread Spectrum Techniques and Appl., Mainz, Germany, September 22–25, 1996, 657–661. VI Levenshtein, Split orthogonal arrays and maximum independent resilient systems of functions, Designs, Codes and Cryptography, vol. 12, no. 2 (1997), 131–160. T. Helleseth, T. Klove, and VI Levenshtein, On the information function of an error correcting code, IEEE Trans. Inform. Theory, vol. 43, no. 2 (1997), pp. 549–557. P. Delsarte and VI Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory, vol. 44, no. 6 (1998), 2477–2504. VI Levenshtein, Universal bounds for codes and designs, in Handbook of Coding Theory, VS Pless and WC Huffman, Eds., Amsterdam: Elsevier, vol. 1, 499–648, 1998. VI Levenshtein, On designs in compact metric spaces and a universal bound on their size, Discrete Mathematics, vol. 192 (1998), 251–271. VI Levenshtein, On the maximum T wise independent systems of Boolean functions, Workshop on Coding and Cryptography, Paris, France, 1999, 367–370. VI Levenshtein, Equivalence of Delsarte's bounds for codes and designs in symmetric association schemes and some applications, Discrete Mathematics, vol. 197/198 (1999), 515–536. VI Levenshtein, New lower bounds on aperiodic crosscorrelation of binary codes, IEEE Trans. Inform. Theory, vol. 45, no. 1 (1999), 284–288. IN AND. Levenshtein, On designs in continuous unit cubes, Proceedings of the IV International Conference: Discrete models in the theory of control systems, Moscow State University, MAKS Press, 2000, 62–64. VI Levenshtein, Efficient reconstruction of sequences, IEEE Trans. Inform. Theory, vol. 47, no. 1 (2001), 2 22. VI Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, Journal of Combin. Theory, Ser. A, vol. 93, no. 2 (2001), 310–332. T. Berger and VI Levenshtein, Asymptotical efficiency of two stage testing, IEEE Trans. Inform. Theory, vol. 48, no. 7 (2002), 1741–1749. T. Berger and VI Levenshtein, Application of cover free codes and combinatorial designs to two stage testing, Discrete Applied Mathematics. T. Helleseth, T. Klove and VI Levenshtein, Hypercubic 4 and 5 designs from double error correcting BCH codes, Designs, Codes and Cryptography. VI Levenshtein, A universal bound for a covering in regular posets and its application to pool testing, Discrete Mathematics. VI Levenshtein, Combinatorial problems motivated by comma free codes, Discrete Mathematics.