Штрассен, Фолькер — Википедия

Фолькер Штрассен
нем. Volker Strassen
Дата рождения 29 апреля 1936(1936-04-29)[1] (88 лет)
Место рождения
Страна
Род деятельности математик, преподаватель университета, специалист в области информатики
Научная сфера математик
Место работы
Альма-матер
Учёная степень докторская степень[вд][2]
Научный руководитель Конрад Джейкобс[вд][3]
Ученики Uday S. Gandbhir[вд][3]
Награды и премии
Сайт math.uni-konstanz.de/~st…
Логотип Викисклада Медиафайлы на Викискладе

Фо́лькер Штра́ссен (нем. Volker Strassen; род. 29 апреля 1936, Дюссельдорф, Германия) — немецкий математик, почетный профессор кафедры математики и статистики Констанцского университета.[4]

Штрассен родился 29 апреля 1936 года в дюссельдорфском районе Герресхайм.[5] Изучал музыку, философию, физику и математику в нескольких немецких университетах[5]. Докторскую степень по математике он получил в 1962 году в Гёттингенском университете под руководством Конрада Якобса.[6] Затем, занимая должность на кафедре статистики Калифорнийского университета в Беркли он подготовил свою хабилитацию для университета Эрлангена — Нюрнберга, куда переехал Якобс.[5] В 1968 году, Штрассен перешел в Институт Прикладной Математики Цюрихского университета, где проработал двадцать лет. В 1988 году он перешел в Констанцский университет.[5] В 1998 году ушел на пенсию.[7]

Вклад в науку

[править | править код]

Свои исследования Штрассен начал как вероятностник. В статье 1964 года «Принцип инвариантности для закона повторного логарифма» он дал функциональную форму закона повторного логарифма, демонстрирующую масштабную инвариантность случайного блуждания. Этот результат, известный сегодня как принцип инвариантности Штрассена или закон повторного логарифма Штрассена, обильно цитировался и был представлен в 1966 году на Международном конгрессе математиков.

В 1969, Штрассен сосредоточил свои усилия на анализе сложности алгоритмов и разработке быстрых алгоритмов. В статье о неоптимальности метода Гаусса[8] он доказал, что для перемножения двух матриц 2 X 2 над некоммутативным кольцом достаточно семи умножений и, используя рекурсию, предложил быстрый алгоритм Штрассена для умножения больших матриц. Это первый алгоритм, который позволяет перемножать большие матрицы за время меньше, чем O(n3). В той же статье он предложил асимптотически быстрый алгоритм обращения матрицы, основанный на алгоритме быстрого умножения матриц. Этот результат был важным теоретическим прорывом, повлёкшим многочисленные дальнейшие исследования проблемы быстрого умножения матриц. Несмотря на последующие улучшения алгоритм Штрассена остаётся практическим методом умножения больших плотных матриц. Поставленная Штрассеном проблема быстрого умножения матриц[9] по сей день (2015 год) не решена ни в теоретическом, ни в практическом плане.

В 1971 году Штрассен совместно с Арнольдом Шёнхаге предложил метод асимптотически быстрого умножения больших целых чисел, основанный на быстром преобразовании Фурье.

В 1977 году он вместе с Робертом Соловеем предложил тест Соловея — Штрассена для определения простоты числа. Это был первый полиномиальный вероятностный алгоритм с ограниченной односторонней ошибкой для определения простоты числа — класс сложности RP. И один из первых результатов, привлекший внимание к возможностям вероятностных алгоритмов.

Был одним из основных создателей теории алгебраической сложности, в которой ему принадлежат многие классические теоремы[10].

В 1999 году Штрассен был награждён медалью Кантора,[5]. В 2003 году Фолькер Штрассен, Роберт Соловей, Гари Миллер и Михаэль Рабин получили премию Париса Канеллакиса за вклад в разработку вероятностного тестирования простоты чисел.[7] В 2008 году он получил премию Кнута за «выдающийся вклад в разработку и анализ эффективных алгоритмов.»[11] В 2011 году он получил медаль Конрада Цузе от Немецкого общества информатики.[12][13]

Примечания

[править | править код]
  1. Архив по истории математики Мактьютор — 1994.
  2. 1 2 Deutsche Nationalbibliothek Record #1027737773 // Gemeinsame Normdatei (нем.) — 2012—2016.
  3. 1 2 Mathematics Genealogy Project (англ.) — 1997.
  4. FB Mathematik and Statistik Архивировано 25 декабря 2008 года., U. Konstanz.
  5. 1 2 3 4 5 Schönhage, A. (2000), "Cantor-Medaille für Volker Strassen" (PDF), Jahresbericht der Deutschen Mathematiker-Vereinigung, 102 (4), Архивировано из оригинала (PDF) 28 сентября 2011, Дата обращения: 11 февраля 2013.
  6. Штрассен, Фолькер (англ.) в проекте «Математическая генеалогия»
  7. 1 2 Preis für Prof. Volker Strassen, uni’kon 16.2004, Univ. of Konstanz.
  8. Strassen V. Gaussian Elimination is not Optimal (англ.) // Numerische Mathematik / F. BrezziSpringer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354—356. — ISSN 0029-599X; 0945-3245doi:10.1007/BF02165411
  9. Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983—1985 гг.: Пер. с англ. — М.: Мир, 1988 — В. Б. Алекссев. Сложность умножения матриц. Обзор.
  10. Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — С. 3. — 32 с. — ISBN 978-5-4439-1032-1.
  11. The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms Архивная копия от 14 мая 2016 на Wayback Machine, ACM SIGACT.
  12. Winter, Cornelia (September 28, 2011), "Konrad-Zuse-Medaille für Informatik an Fritz-Rudolf Güntsch und Volker Strassen", Informationsdienst Wissenschaft (нем.), Архивировано из оригинала 6 июня 2014, Дата обращения: 11 февраля 2013.
  13. Konrad-Zuse-Medaille Архивировано 19 августа 2014 года., Gesellschaft für Informatik (in German), retrieved 2012-03-09.