Фолькер Штрассен
Фолькер Штрассен | |
|---|---|
 Фолькер Штрассен читает лекцию о Премии Кнута на SODA 2009. | |
| Рожденный | 29 апреля 1936 г. |
| Национальность | немецкий |
| Альма-матер | Геттингенский университет |
| Известный | Уличный алгоритм |
| Научная карьера | |
| Поля | Математика |
| Учреждения | Университет Констанца |
| Докторантура | Конрад Джейкобс |
| Докторанты | Питер Бургиссер Иоахим фон цур Гатен |
Фолькер Штрассен (родился 29 апреля 1936) — немецкий математик , почётный профессор кафедры математики и статистики Констанцского университета . [1]
За важный вклад в анализ алгоритмов он получил множество наград, в том числе медаль Кантора . [2] медаль Конрада Цузе , [3] премия Пэрис Канеллакис за работу по рандомизированному тестированию на простоту , [4] Премия Кнута за «выдающийся и влиятельный вклад в разработку и анализ эффективных алгоритмов». [5]
Биография [ править ]
Штрассен родился 29 апреля 1936 года в Дюссельдорфе-Герресхайме . [2] Изучив музыку , философию, физику и математику в нескольких немецких университетах, [2] он получил докторскую степень. Степень бакалавра математики в 1962 году в Геттингенском университете под руководством Конрада Якобса . [6] Затем он занял должность на кафедре статистики одновременно Калифорнийского университета в Беркли, проходя аспирантуру в Университете Эрланген-Нюрнберг , куда с тех пор переехал Джейкобс. [2] В 1968 году Штрассен перешёл в Институт прикладной математики Цюрихского университета , где оставался в течение двадцати лет, прежде чем перешёл в Констанцский университет в 1988 году. [2] Он вышел на пенсию в 1998 году. [4]
Исследования [ править ]
Штрассен начал свои исследования как вероятностный специалист; его статья 1964 года «Принцип инвариантности закона повторного логарифма» определила функциональную форму закона повторного логарифма , показывая форму масштабной инвариантности в случайных блужданиях . Этот результат, ныне известный как принцип инвариантности Штрассена или закон повторного логарифма Штрассена , широко цитировался и привел к его презентации на Международном конгрессе математиков в 1966 году .
В 1969 году Штрассен переключил свои исследовательские усилия на анализ алгоритмов , написав статью об исключении Гаусса , представив алгоритм Штрассена , первый алгоритм для выполнения умножения матриц быстрее, чем O( n 3 ) с временной привязкой, которая могла бы возникнуть в результате использования простого алгоритма. В той же статье он также представил асимптотически быстрый алгоритм обращения матрицы , основанный на быстром алгоритме умножения матриц. Этот результат стал важным теоретическим прорывом, приведшим к большому количеству дополнительных исследований по быстрому умножению матриц, и, несмотря на более поздние теоретические улучшения, он остается практическим методом умножения плотных матриц среднего и большого размера. В 1971 году Штрассен совместно с Арнольдом Шенхаге опубликовал еще одну статью об асимптотически быстром целочисленном умножении, основанном на быстром преобразовании Фурье ; см. алгоритм Шенхаге – Штрассена . Штрассен также известен своей работой 1977 года с Робертом М. Соловеем над тестом на простоту Соловея-Штрассена , первым методом, показывающим, что проверка того, является ли число простым, может быть выполнена за рандомизированное полиномиальное время , и одним из первых результатов, показывающих степень рандомизированных алгоритмов в более общем плане.
Награды и почести [ править ]
В 1999 году Штрассен был награжден медалью Кантора . [2] а в 2003 году он стал со-лауреатом Премии Парижа Канеллакиса вместе с Робертом Соловеем , Гэри Миллером и Майклом Рабином за их работу по рандомизированному тестированию на простоту. [4] В 2008 году он был награжден премией Кнута за «выдающийся и влиятельный вклад в разработку и анализ эффективных алгоритмов». [5] В 2011 году он выиграл медаль Конрада Цузе Общества информатики . [3] [7] В 2012 году он стал членом Американского математического общества . [8]
Ссылки [ править ]
- ^ Математика и статистика FB. Архивировано 25 декабря 2008 г. в Wayback Machine , У. Констанц.
- ^ Jump up to: Перейти обратно: а б с д и ж Шёнхаге, А. (2000), «Медаль Кантора Фолькеру Штрассену» (PDF) , Годовой отчет Ассоциации немецких математиков , 102 (4) .
- ^ Jump up to: Перейти обратно: а б Винтер, Корнелия (28 сентября 2011 г.), «Медаль Конрада Цузе за информатику Фрицу-Рудольфу Гюнчу и Фолькеру Штрассену» , Служба научной информации (на немецком языке) .
- ^ Jump up to: Перейти обратно: а б с Премия профессору Фолькеру Штрассену, уникон 16.2004 , Univ. из Констанца.
- ^ Jump up to: Перейти обратно: а б Премия Кнута 2008 года присуждается Фолькеру Штрассену за его плодотворный и влиятельный вклад в разработку эффективных алгоритмов ACM SIGACT.
- ^ Фолькер Штрассен в проекте «Математическая генеалогия»
- ↑ Медаль Конрада Цузе . Архивировано 19 августа 2014 г. в Wayback Machine , Gesellschaft für Informatik (на немецком языке), получено 9 марта 2012 г.
- ^ Список членов Американского математического общества , получено 5 августа 2013 г.
Внешние ссылки [ править ]
- Домашняя страница Dr. Фолькер Штрассен
- Вайсштейн, Эрик В. «Формулы Штрассена» . Математический мир . Формулы для быстрого умножения и обращения матриц.
- О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Фолькер Штрассен» , Архив истории математики MacTutor , Университет Сент-Эндрюс
- 1936 рождений
- Живые люди
- Немецкие математики XX века
- Немецкие математики XXI века
- Теоретики-компьютерщики
- Линейные алгебраисты
- Выпускники Геттингенского университета
- Калифорнийский университет, факультет Беркли
- Академический состав Цюрихского университета
- Академический состав Констанцского университета
- Лауреаты премии Кнута
- Члены Американского математического общества