Штрассен, Фолькер

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Фолькер Штрассен читает лекцию на вручении премии Кнута на Симпозиуме по Быстрым Алгоритмам в 2009 году

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

Биография[править | править исходный текст]

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

Вклад в науку[править | править исходный текст]

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

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

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

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

Награды[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. FB Mathematik and Statistik, U. Konstanz.
  2. 1 2 3 4 5 Schönhage, A. (2000), "«Cantor-Medaille für Volker Strassen»", Jahresbericht der Deutschen Mathematiker-Vereinigung Т. 102 (4), <http://dml.math.uni-bielefeld.de/JB_DMV/JB_DMV_102_4.pdf> .
  3. Штрассен, Фолькер (англ.) в проекте «Математическая генеалогия»
  4. 1 2 Preis für Prof. Volker Strassen, uni’kon 16.2004, Univ. of Konstanz.
  5. Volker Strassen: Gaussian Elimination is not Optimal. In: Numerische Mathemetik, Bd. 13 (1969), S. 354—356, ISSN 00298-599X
  6. Кибернетический сборник. Новая серия. Вып. 25. Сб. статей 1983 — 1985 гг.: Пер. с англ. — М.: Мир, 1988 — В.Б. Алекссев. Сложность умножения матриц. Обзор.
  7. The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms, ACM SIGACT.
  8. Winter, Cornelia (September 28, 2011), "«Konrad-Zuse-Medaille für Informatik an Fritz-Rudolf Güntsch und Volker Strassen»", Informationsdienst Wissenschaft, <http://www.idw-online.de/pages/de/news443079> .
  9. Konrad-Zuse-Medaille, Gesellschaft für Informatik (in German), retrieved 2012-03-09.

Ссылки[править | править исходный текст]