Владимир Иосифович Левенштейн

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Владимир Иосифович Левенштейн

LevenshteinВИ.jpg
Дата рождения
20 мая 1935 года
Место рождения
Москва, СССР











Владимир Иосифович Левенштейнсоветский и российский математик, доктор физико-математических наук, ведущий научный сотрудник Института прикладной математики имени М.В. Келдыша, автор алгоритма оценки схожести строк[1].

Научная карьера[править]

Владимир Левенштейн родился 20 мая 1935 года.

В 1958 году окончил механико-математический факультет Московского государственного университета имени М.В. Ломоносова.

С тех пор работает в Институте прикладной математики имени М.В. Келдыша.

В 1965 году при изучении последовательностей ввёл понятие дистанции редактирования[2], названное «Расстояние Левенштейна».

Расстояние Левенштейна (также функция Левенштейна) в теории информатики и компьютерной лингвистики является мерой разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной последовательности в другую.

Пример:

Чтоб перевести слово «конь» в слово «кот» необходимо совершить одно удаление и одну замену, соответственно дистанция Левенштейна составляет 2:

  1. Конь
  2. Коть (Заменяем н на т)
  3. Кот (Удаляем ь)

Другой пример: имеется два слова, необходимо преобразовать одно слово в другое, используя только удаление, добавление и замену:

  1. Машка Миша — исходное состояние
  2. Мишка Миша — шаг 1 (замена)
  3. Миша Миша — шаг 2 (удаление)

Вывод: расстояние Левенштейна от строки Машка до строки Миша равно 2.

Практическим применением дистанции Левенштейна является определение похожести последовательностей символов, например, при проверке правописания или поиске дубликатов.

Программисты на PHP имеют функцию levenshtein, которая вычисляет дистанцию Левенштейна.

В 2006 году Левенштейн получил медаль Ричарда Хэмминга.

Исследования посвящены оптимизационным комбинаторым задачам кодирования и тестирования, универсальным границам для кодов и дизайнов и теория ортогональных многочленов, синхронизационным свойствам последовательностей, кодов и автоматов, а также изучению совершенных кодов, исправляющих одиночные ошибки различных типов.

Труды[править]

  • В.И.Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011-1014.
  • В.И.Левенштейн, Применение матриц Адамара к одной задаче теории кодирования, Проблемы кибернетики, вып. 5, ГИФМЛ, Москва, 1961, 125-136.
  • В.И.Левенштейн, О некоторых свойствах кодовых систем, Докл. АН СССР, 140, 6, 1961, 1274-1277.
  • В.И.Левенштейн, Самонастраивающиеся автоматы для декодирования сообщений, Докл. АН СССР, 141, 6, 1961, 1320-1323.
  • В.И.Левенштейн, Об обращении конечных автоматов, Докл. АН СССР, 147, 6, 1962, 1300-1303.
  • В.И.Левенштейн, Об устойчивом доопределении конечных автоматов, Проблемы кибернетики, вып. 10, ГИФМЛ, Москва, 1963, 281-286.
  • В.И.Левенштейн, О некоторых своствах кодирования и самонастраивающихся автоматах для декодирования сообщений, Проблемы кибернетики, вып. 11, ГИФМЛ, Москва, 1964, 63-121.
  • В.И.Левенштейн, Декодирующие автоматы, инвариантные относительно начального состояния, Проблемы кибернетики, вып. 12, ГИФМЛ, Москва, 1964, 125-136.
  • В.И.Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, 163, 4, 1965, 845-848.
  • В.И.Левенштейн, Двоичные коды с исправлением выпадений и вставок символа 1, Пробл. перед. информ., 1, 1, 1965, 12-25.
  • В.И.Левенштейн, Об одном методе решения задачи синхронизации цепи автоматов за минимальное время, Пробл. перед. информ., 1, 4, 1965, 20-32.
  • В.И.Левенштейн, Двоичные коды, обеспечивающие синхронизацию и исправление ошибок, Тезисы кратких научных сообщений Международного конгресса математиков, Секция 13, Москва, 1966, 24.
  • В.И.Левенштейн, Асимптотически оптимальный двоичный код с исправлением выпадений одного или двух соседних символов, Проблемы кибернетики, вып. 19, Наука, Москва, 1967, 293-298.
  • В.И.Левенштейн, Об избыточности и замедлении разделимого кодирования натуральных чисел, Проблемы кибернетики, вып. 20, Наука, Москва, 1968, 173-179.
  • В.И.Левенштейн, О синхронизации двусторонних сетей автоматов, Пробл. перед. информ., 4, 4, 1968, 49-62.
  • В.И.Левенштейн, Оценки для кодов, обеспечивающих исправление ошибок и синхронизацию, Пробл. перед. информ., 5, 2, 1969, 3-13.
  • В.И.Левенштейн, О максимальном числе слов в кодах без перекрытий, Пробл. перед. информ., 6, 4, 1970, 88-90.
  • В.И.Левенштейн, Об одном методе построения квазилинейных кодов, обеспечивающих синхронизацию и исправление ошибок, Пробл. перед. информ., 7, 3, 1971, 30-40.
  • В.И.Левенштейн, О верхних оценках для кодов с фиксированным весом векторов, Пробл. перед. информ., 7, 4, 1971, 3-12.
  • В.И.Левенштейн, О минимальной избыточности двоичных кодов, исправляющих ошибки, Пробл. перед. информ., 10, 2, 1974, 26-42.
  • В.И.Левенштейн, Элементы теории кодирования, В кн. Дискретная математика и математические вопросы кибернетики, Наука, Москва, 1974, 207-305.
  • В.И.Левенштейн, О максимальной плотности заполнения n-мерного евклидова пространства равными шарами, Математические заметки, 18, 2, 1974, 301-311.
  • V.I. 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.
  • В.И.Левенштейн, О границах вероятности необнаружения ошибки, Пробл. перед. информ., 13, 1, 1977, 3-18.
  • Г.А. Кабатянский, В.И.Левенштейн, О границах для упаковок на сфере и в пространстве, Пробл. перед. информ., 14, 1, 1978, 3-25.
  • В.И.Левенштейн, О выборе многочленов для получения границ в задачах упаковки, VII Всесоюзная конференция по теории кодирования и передачи информации, ч. II, Москва - Вильнюс, 1978, 103-108.
  • В.И.Левенштейн, О границах для упаковок в n-мерном евклидовом пространстве, Докл. АН СССР, 245, 6, 1979, 1299-1303.
  • В.И.Левенштейн, Границы максимальной мощности кода с ограниченным модулем скалярного произведения, Докл. АН СССР, 263, 6, 1982, 1303-1308.
  • В.И.Левенштейн, Границы для упаковок метрических пространств и некоторые их приложения, Проблемы кибернетики, вып. 40, Наука, Москва, 1983, 43-110.
  • V.I. Levenshtein, Packing of polynomial metric spaces, Third International Workshop on Information Theory, Convolutional codes; multi-user communication, Sochi, 1987, 271-274.
  • В.И.Левенштейн, О прямолинейной границе для экспоненты вероятности необнаруженной ошибки, Пробл. перед. информ., 25, 1, 1989, 33-37.
  • V.I. Levenshtein, Perfect deletion-correcting codes as combinatorial designs, Proc. of the Second International Workshop: Algebraic and Combinatorial Coding Theory, Leningrad, USSR, 1990, 137-140.
  • В.И.Левенштейн, О совершенных кодах в метрике вставок и выпадений, Дискретная математика, 3, 1, 1991, 3-20.
  • V.I. Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Applicandae Mathematicae, vol.29 (1992), 1-82.
  • V.I. 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.
  • V.I. 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.
  • V.I. Levenshtein and A.J.H. Vinck, Perfect (d,k)-codes capable of correcting single peak-shifts, IEEE Trans. Inform. Theory, vol. 39, no. 2 (1993), 656-662.
  • V.I. Levenshtein, Packing and decomposition problems for polynomial association schemes, Europ. J. Combinatorics, vol. 14 (1993), 461-477.
  • T. Ericson and V.I. Levenshtein, Superimposed codes in the Hamming space, IEEE Trans. Inform. Theory, vol. 40, no. 6 (1994), 1882-1893.
  • G. Fasekas and V.I. 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, V.I. Levenshtein, and O.Ytrehus, Bounds on the minimum support weights, IEEE Trans. Inform. Theory, vol. 41, no. 2 (1995), 432-440.
  • V.I. Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory, vol. 41, no. 5 (1995), 1303-1321.
  • В.И.Левенштейн, Простое доказательство основных неравенств для фундаментальных параметров кодов в полиномиальных схемах отношений, Пробл. перед. информ., 31, 4, 1995, 37-50.
  • V.I. 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.
  • V.I. 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.
  • V.I. 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 V.I. Levenshtein, On the information function of an error-correcting code, IEEE Trans. Inform. Theory, vol. 43, no. 2 (1997), pp. 549-557.
  • В.И.Левенштейн, Восстановление обьектов по минимальному числу искаженных образцов, Доклады Российской Академии наук, 354, 5, 1997, 593-596.
  • P. Delsarte and V.I. Levenshtein, Association schemes and coding theory, IEEE Trans. Inform. Theory, vol. 44, no. 6 (1998), 2477-2504.
  • V.I. Levenshtein, Universal bounds for codes and designs, in Handbook of Coding Theory, V.S. Pless and W.C. Huffman, Eds., Amsterdam: Elsevier, vol. 1, 499-648, 1998.
  • V.I. Levenshtein, On designs in compact metric spaces and a universal bound on their size, Discrete Mathematics, vol. 192 (1998), 251-271.
  • V.I. Levenshtein, On the maximum T-wise independent systems of Boolean functions, Workshop on Coding and Cryptography, Paris, France, 1999, 367-370.
  • V.I. 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.
  • V.I. Levenshtein, New lower bounds on aperiodic crosscorrelation of binary codes, IEEE Trans. Inform. Theory, vol. 45, no. 1 (1999), 284-288.
  • В.И. Левенштейн, О дизайнах в непрерывных единичных кубах, Труды IV Международной конференции: Дискретные модели в теории управляющих систем, МГУ, МАКС Пресс, 2000, 62-64.
  • V.I. Levenshtein, Efficient reconstruction of sequences, IEEE Trans. Inform. Theory, vol. 47, no. 1 (2001), 2-22.
  • V.I. 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 V.I. Levenshtein, Asymptotical efficiency of two-stage testing, IEEE Trans. Inform. Theory, vol. 48, no. 7 (2002), 1741-1749.
  • T. Berger and V.I. Levenshtein, Application of cover-free codes and combinatorial designs to two-stage testing, Discrete Applied Mathematics.
  • T.Helleseth, T.Klove and V.I. Levenshtein, Hypercubic 4 and 5-designs from double-error-correcting BCH codes, Designs, Codes and Cryptography.
  • V.I. Levenshtein, A universal bound for a covering in regular posets and its application to pool testing, Discrete Mathematics.
  • T.Helleseth, T.Klove and V.I. Levenshtein, Error-correction capability of binary linear codes and the discrete simplex problem, IEEE Trans. Inform. Theory.
  • V.I. Levenshtein, Combinatorial problems motivated by comma-free codes, Discrete Mathematics.

Источники[править]

  1. Левенштейн В.И. Персональная страница
  2. В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965. 163.4:845-848.
 
Владимир Иосифович Левенштейн относится к евреям-создателям компьютера и интернета
Предшественники

Ибрагим ЗаркалиИзраиль ШтафельЕвно ЯкобсонАвраам ШтернХаим СлонимскийГирш ИоффеАмеде МангеймКурт ХерцштаркЭмануэль ГольдбергСтанислав УламЭмиль ПостРальф Бенджамин

Компьютерные учёные

Джон НейманМакс НьюманТерри ВиноградГ. ЛукоффХэл АбельсонФил КацДжеф РаскинУриэль ФейгеАмос ФиатДавид ХарельНир ШавитС. ВольфрамЛи МинскийЭд ФейгенбаумЭндрю ВитербиМ. БлюмР. ФаноАдель ГолдбергР. ФинкельА. СпилбергД.С. СлотникХайн ГолдстайнАдель КацАза РаскинИда РоудсРичард КарпД. Коэн-ОрДжон КемениРэй КурцвейлЛ.А. ЛевинДжон МаккартиС. ПейпертАлан ПерлисЛоренс РабинерФрэнк РозенблаттД. ГерберДжефф УльманД. ВейценбаумДжуда ПерлБарбара ЛисковФред КоэнМайкл ЛаорД. ЭстринТельма ЭстринДебора ЭстринЭхуд ШапироЮваль ЭловициА.А. БрудноМайкл РабинЗ.Л. РабиновичВ.И. ЛевенштейнГ.Л. ЛившинБ.М. КаганБ.Я. КаганА.С. КронродА.А. ФельдбаумИ.В. БергИ.С. БрукА.Б. ЗалкиндГ.М. АдельсонА.Ф. ИоффеУ. КэхэнАмир ПнуэлиВольф ГоломбЛи ФельзенштейнС. МэйзорМули ИденОрен ПаташникРон ПинтерПитер ЭлиасЭрих БлохВ.Н. ВапникА.Я. ЧервоненкисИ.Ц. ГальперинГили РаананАрье ФайнгольдА. ФренкельЙорам МозесХагит АтияШломо МоранАви ВигдерсонДорит АароновУди МанберА. БродерЗеев СураскиДафна КоллерИлан ШпилингерЖан ИшбиаБоаз ЭйтанЮдит ЭстринДади ПерлмуттерЯэль ВиллаЭд КэхэнБ.Г. КацС. ОвшинскиМ.П. ГальперинН.Е. КобринскийА.Е. КобринскийИрвин ЯкобсМоше ЛихтманШломит ВайсЙорам ЯакобиЭндрю ТаненбаумДжошуа БлохДин ХачамовичАнна КарлинЕ.Л. РошалЯн РайхманИ.Я. АкушскийЕ.А. ЛиберманИтан ЦукерманВ.Л. АрлазаровЛ.С. БерштейнМарк АдлерВ.А. СойферКен СильверманМони НаорСинтия ДворкОмер РейнгольдБрэм КоэнОдед РегевР. ФейгинНоам НисанДани ДолевНати ЛинеалА.М. ГореликР. МореноБ. СильверН. ВудландИ. БерезинПол ЭйслерН. АбрамсонВ. БухгольцДжо КейтсД. СассманВ.С. ЧернявскийЛасло КозмаЛарри ТеслерДжек ШварцВ.И. ШтейнбергИдо КантерРассел КиршКлара Нейман

Кибернетики

Норберт ВинерХейнц фон ФёрстерМ.А. АйзерманН.А. БернштейнЭ.М. БраверманВ.И. ВаршавскийБен ГерцельЛ.И. ГутенмахерВ.К. ЛевинМ.Б. ЛейтманАвраам ЛемпельА.Я. ЛернерС.Б. ПогребинскийАртуро РозенблютГерберт СаймонБ.А. ТрахтенбротМ.Л. ЦетлинЯ.З. ЦыпкинБ.Л. ШмульянЮ.А. Шрейдер

Робототехника

Ружена БайчиХанс БарухЙохан БоренштейнИгорь ВернерКен ГолдбергДавид ЗаррукДин КейменИ.М. МакаровВиктор ШейнманСарит КраусХод ЛипсонЯн БернстайнГил ВайнбергДжефф ЛиберманДжером ЛемельсонВ.С. Гурфинкель

Криптографы

Лен АдлеманДэниел БернстейнАлекс БирюковИрвинг ГудСоломон КульбакАбрахам СинковУильям ФридманМартин ХеллманАди ШамирБрюс ШнайерДэн БонехЭли БихамШафи Гольдвассер

Интернет

Пол БэранВинт СерфРадья ПерлманБоб КанЛео КлейнрокДэнни КоэнРичард СтоллманАарон ШварцКарл МаламудД. ЛаньеДж. ЭпплбаумМ. ВербицкийДжош КопельманП. КирстейнИда ГольцДмитрий Хомак

Предприниматели

Сергей БринЛарри ПейджСтив БалмерСьюзен ВожицкиШерил СэндбергМарк ЦукербергЭдуардо СаверинДастин МосковицТрэвис Каланик Сафра КацЛарри ЭллисонВ.М. МирилашвилиЭнди ГутмансАмнон ШашуаОрен ЭциониФилипп КанЯн КумМакс ЛевчинРид ХоффманКен ЛевинБен ХоровицЮджин КлейнерАртур ЛевинсонЛирон ШапираУэнделл БраунЭнди ГроувРонен ШилоЭлдад МатитяуАврам МиллерМарк ПинкусБоб РозеншейнЭнди РубинДжон РубинштейнМайкл РубинЛиор РонТомер КаганЛеон БагритЭд ЗандерМарк БениоффМайкл ДеллО.П. ФирерКен ГольдманДэвид ХиндавиАлон КоэнКамилло ОливеттиГилад РабиновичЭрик ЛефкофскиСэнди ЛернерАарон ЛевиеЭдвин ЛэндДани ЛевинТальмон МаркоИгорь МагазинникЮ.Б. МильнерАлан ШугарМайкл МорхеймКрейг НьюмаркРут ПоратБрайан РобертсГенри СамуэлиДжоэл СпольскиАлан ТрефлерД. РозенштайнДэн РозенцвейгЭнн ВожицкиДжефф ВейнерЛев ЛевиевТедди СагиОрна БерриБ. ГордонДжек ТрэмелКира РадинскиДэн БриклинИ.В. СегаловичА.Б. НосикФеликс ЗандманБени АлагемД. ХоффманРальф БаерЭд ФредкинЭрик БенамуМаксин ФассбергДейв ГолдбергГил ШведРоберт АльтманДжефф СколлСтив ШирлиЛ.Б. БогуславскийЯкоб ГолдманМайкл КоганЭнди ХерцфельдНир ЗукМарн ЛевинКоби АлександерБоаз МишолиЭндрю МэйсонЛ.И. ВайнбергЗоар ЗисапельАарон АаронЯнив ГартиУри ЛевинНил ДракманИцик КиршенбаумДжейсон РубинДов МоранЙосси МатиасДжек ФридманЙоэль МаарекМитч КапорД. СтопплменДжордан МекнерДжастин ФранкельДжонатан АбрамсД. ХомакШон РэдДов ФроманЕ.И. БунинаСтив ПерлманБратья БухманыМендель РозенблюмЖерар ФилипсСэм АльтманЭнди ДжессиРэнди Цукерберг

Компании США

AlphabetGoogleDellPackard BellQuixeyFacebookWhatsAppPalo Alto NetworksYouTube

Израильские компании

Elbit SystemsEx Libris GroupCeragon NetworksComsec ConsultingCheck PointElronEZchip SemiconductorAnobitAlvarionAudioCodesBATMChip PC TechnologiesCybereasonM-SystemsWaze MobileMellanoxMirabilisNice SystemsAlgoSecAmdocsComverseQumranetInfinidatCimatronRadwareLucid LogixEmblaze MobileCyberArkSikluPlariumInuitiveAllot CommunicationsMetalinkKramer ElectronicsGettWix.comVishay IntertechnologyYamarRadwinRADDataRAD GroupAITECRamon ChipsSightfulGilat Satellite NetworksRoboteam

Иностранные компании в Израиле

Intel в ИзраилеMicrosoft в ИзраилеApple в ИзраилеIBM в ИзраилеMotorola в ИзраилеHewlett-Packard в ИзраилеGoogle IsraelAT&T в ИзраилеCisco в ИзраилеeBay в ИзраилеAmazon в ИзраилеPalo Alto в ИзраилеDell в ИзраилеToshiba в ИзраилеSamsung в ИзраилеAlibaba в ИзраилеElectronic Arts в ИзраилеFacebook в ИзраилеAlcatel в ИзраилеEMC в ИзраилеARM в ИзраилеNvidia в ИзраилеYahoo в ИзраилеSalesforce в ИзраилеProofpoint в ИзраилеКасперский в ИзраилеЯндекс в Израиле

Израильские технологии

Израильская кремниевая долинаКибервойны ИзраиляВирусы и антивирусыДНК-компьютерWEIZACDiskOnKey/USB-флеш-накопительУчастие Израиля в создании Firewalli8088Kinect«Микромышь»EPROMRPDA-57Changhong H2SolarinAny.doProcess SimulateTecnomatixClarizenBabylonICQJuniorKali LinuxCeedoooVooMobliMoovitMeerkatViberWiPeerWazeYoSkylakeKaby Lake RefreshEnLigth256GrippityGoogle DuplexTDMoIPPentium MDebaterCentrinoModu TPentium DKaby LakeSandy BridgeTap SystemsIce LakeNervana NNP-1Робототехника Израиляизраильский автономный навигатор для пехотинцевСлайдтроникаБоевые роботы ИзраиляWeizQC