Статья 1969 года «Gaussian Elimination is Not Optimal» представила метод умножения матриц, который нарушил существующие ограничения скорости, доказав, что операции с большими матрицами могут выполняться значительно быстрее, чем при традиционной кубической временной сложности. Это открытие утвердило Фолькера Штрассена как ключевую фигуру в развитии теоретической информатики и проектирования алгоритмов.
Раннее образование и академический путь
Фолькер Штрассен родился в 1936 году в Дюссельдорф-Герресхайме, Германия, и получил широкое академическое образование, охватывающее философию, физику, музыку и математику. Он завершил докторскую диссертацию в Геттингенском университете в 1962 году под руководством Конрада Якобса. Его ранняя карьера привела его в Калифорнийский университет в Беркли, где он работал на факультетах математики и статистики, дослужившись до доцента. В 1968 году он перешел в Цюрихский университет, чтобы возглавить семинар по прикладной математике, где проработал два десятилетия, прежде чем перейти в Констанцский университет в 1988 году, где оставался до выхода на пенсию в 1998 году.
Фундаментальный вклад в теорию вероятностей
До перехода к вычислительной сложности Штрассен добился значительных успехов в теории вероятностей. Его работа 1964 года «An Invariance Principle for the Law of the Iterated Logarithm» принесла ему выступление на Международном конгрессе математиков 1966 года в Москве. К 1965 году он вывел необходимые и достаточные условия для вероятностных мер и мартингалов. Его совместная работа 1973 года с Хубером по минимаксным тестам и лемме Неймана-Пирсона послужила краеугольным камнем для последующих разработок в области робастной статистики.
Прогресс в алгоритмической эффективности
Влияние Штрассена на проектирование алгоритмов включает разработку в 1971 году алгоритма Шёнхаге-Штрассена для умножения целых чисел, который десятилетиями оставался самым быстрым известным методом. В 1977 году он совместно с Робертом М. Соловеем создал тест на простоту Соловея-Штрассена, ознаменовав сдвиг в сторону рандомизированной проверки за полиномиальное время. Его сотрудничество с Вальтером Бауром в 1983 году предоставило метод ограничения сложности рациональных функций, что еще больше расширило его предыдущие исследования алгебраической сложности, представленные на Международном конгрессе математиков 1974 года в Ванкувере.
Двадцать вопросов, восемь минут на часах и процентиль, измеренный по всем, кто его проходил. Без регистрации.
Пройти тест IQ →Профессиональное признание
На протяжении своей карьеры Штрассен был принят в несколько учреждений, включая Немецкую академию наук Леопольдина, Геттингенскую академию наук и гуманитарных наук в Нижней Саксонии и Гейдельбергскую академию наук и гуманитарных наук. Он также является членом Американского математического общества. Среди его наград — медаль Кантора 1999 года, премия Пэриса Канеллакиса 2003 года, премия Кнута 2008 года и медаль Конрада Цузе 2011 года.
Краткие факты
- Рождение: 1936, Дюссельдорф - Гражданство: Германия - Докторская степень: Геттингенский университет, 1962 - Значимый алгоритм: Алгоритм Штрассена для умножения матриц - Премия Кнута: 2008 - Медаль Кантора: 1999 - Медаль Конрада Цузе: 2011 - Академическое место: Констанцский университет
Вопросы читателей
### В чем значимость алгоритма Штрассена?
Он доказал, что умножение больших матриц может выполняться быстрее, чем при традиционной временной границе O(n³).
### Какие основные награды получил Фолькер Штрассен?
Среди его наград — медаль Кантора, премия Кнута, премия Пэриса Канеллакиса и медаль Конрада Цузе.
