Отакар Борувка (10 мая 1899 г. в Угерском Остроге - 22 июля 1995 г. в Брно ) был чешским математиком, наиболее известным сегодня своими работами в области теории графов . [1] [2]
Отакар Борувка | |
---|---|
Родившийся | |
Умер | 22 июля 1995 г. | (96 лет)
Национальность | Чешский |
Занятие | Математик |
Известен |
|
Образование и карьера
Борувка родился в Угерском Остроге , городе в Моравии (затем в Австро-Венгрии , позже в Чехословакии ; сегодня Чехия ), в семье директора школы. [2] В 1910 году он посещал гимназию в Угерске-Градиште . [1] В 1916 году, под влиянием продолжающейся Первой мировой войны , он перешел в военное училище (Realschule) в Границе , а затем поступил в Императорский и Королевский Военно-техническая академия в Мёдлинге под Веной . [1] [2]
Когда война закончилась, Борувка вернулся в Угерске-Градиште, закончил там учебу в 1918 году в гимназии и стал студентом Императорского чешского технического университета им. Франца Иосифа в Брно , сначала изучая гражданское строительство . [1] [2] В 1920 году в Брно открылся Масариковский университет , и Борувка тоже начала там учиться. [1] Он стал помощником Матиаса Лерха в Масарике в 1921 году, но Лерх умер в 1922 году; его должность в Масарике занял Эдуард Чех , которому также помогал Борувка, получив докторскую степень в 1923 году [3].
По предложению Чеха Борувка посетил Эли Картана в Париже с 1926 по 1927 год. [1] [2] Он получил абилитацию в Масариковом университете в 1927 году и (отклонив предложение Загребского университета ) стал там доцентом в 1928 году. . [1] [2] Он продолжал ездить за границу в течение конца 1920 - х и начале 1930 - х годов, в Картаном в Париже снова, а также Вильгельма Бляшке в Гамбурге . [1] [2] В 1934 году он получил звание доцента в Масарике, в 1940 году занял кафедру, а в 1946 году стал ординарным профессором. [1] [2]
В 1965 году он основал новый журнал Archivum Mathematicum , а в 1969 году стал одним из основателей Института математики Чехословацкой академии наук , разделив свое время между Институтом и своей профессурой в Масарике. [2]
Взносы
Проблема проектирования эффективных электрических распределительных сетей была предложена Борувке его другом Йиндржихом Сакселем, сотрудником Западно-Моравской энергетической компании, во время Первой мировой войны. В своей статье 1926 года O jistém problému minimálním (на английском языке об одной минимальной проблеме ), [4] Борувка решить эту проблему путем моделирования его математически как минимум связующего дерева проблемы, и описала первый известный алгоритм для нахождения минимального остовного дерева в виде метрического пространства (множество городов , чтобы быть подключен к сети, вместе с их расстояниями ). [1] Его метод, который теперь называется алгоритмом Борувки , работает, многократно добавляя связи между каждым поддеревом минимального остовного дерева, найденного на данный момент, и его ближайшим соседним поддеревом. [5] Один и тот же алгоритм неоднократно открывался заново. [6] [7] [8] Он больше подходит для распределенных и параллельных вычислений, чем многие другие алгоритмы минимального остовного дерева, может достигать линейной временной сложности на планарных графах и, в более общем плане, в семействах второстепенных -замкнутых графов, [9] и играет роль центральная роль в рандомизированном алгоритме линейного времени Karger, Klein & Tarjan (1995) . [10]
С 1924 по 1935 год Борувка в первую очередь интересовался дифференциальной геометрией . Его работа в этой области касалась аналитических соответствий между проективными плоскостями , нормальной кривизны многомерных поверхностей и формулы Френе для кривых в многомерных пространствах. [2]
Начиная с 1930-х годов интересы Борувки сместились в сторону абстрактной алгебры , в частности теории групп . Он также был одним из первых, кто изучил обобщение групп, названных им «группоидами», но теперь более часто называемых магмами . [2] Его учебник по группам и группоидам, первоначально опубликованный на чешском языке в 1944 году, претерпел несколько дополнений и переводов, включая английское издание в 1976 году. [1]
После войны Борувка снова переключился с алгебры на теорию дифференциальных уравнений . Он опубликовал несколько исследовательских работ по этой теме, а также монографию по дифференциальным уравнениям второго порядка, которую он опубликовал в 1971 г. [1]
Награды и почести
Борувка стал членом-корреспондентом Чехословацкой академии наук при ее создании в 1953 году и рядовым членом в 1965 году. В 1969 году Университет Коменского в Братиславе присвоил ему почетную докторскую степень, а в 1994 году он получил вторую почетную докторскую степень Масариковского университета в г. Брно . [1] [11]
Он также дал медали в Свободном университете Брюсселя , в Университете Льежа , Ягеллонский университет , Университета Коменского, Палацкого университета г. Оломоуц , Пуркине университета в Усти - над - Лабем , в Немецкой академии наук в Берлине , в Российской Академии Наук # Академии наук СССР и Чехословацкой Академии наук. [12]
Рекомендации
- ^ Б с д е е г ч я J к л м О'Коннор, Джон Дж ; Робертсон, Эдмунд Ф. , "Отакар Борувка" , архив истории математики MacTutor , Сент-Эндрюсский университет.
- ^ Б с д е е г ч я J K Трэшняк, Зденек; Шарманова, Петра; Pža, Bedřich (1996), Třešák, Zdeněk; Шарманова, Петра; Пужа, Бедржих (ред.), Отакар Борувка [резюме на английском языке] , Брно: Nadace Universitas Masarykiana v Brně, стр. 218–222.
- ^ Эта дата взята из MacTutor. Более поздняя дата, 1926 год, указана Отакаром Борувкой в проекте « Математическая генеалогия» . Однако, похоже, это относится скорее к его хабилитации, чем к его докторской степени.
- ^ Borvka, Otakar (1926), "O jistém problému minimálním", Práce Moravské přírodovědecké společnosti , 3 (3): 37–58
- ^ Нешетржил, Ярослав ; Милкова, Ева; Nešetřilová, Helena (2001), «Отакар Борувка по проблеме минимального остовного дерева: перевод обеих статей 1926 года, комментарии, история», Дискретная математика , 233 (1–3): 3–36, DOI : 10.1016 / S0012-365X ( 00) 00224-7 , ЛВП : 10338.dmlcz / 500413 , МР 1825599
- ^ Шоке, Гюстав (1938), «Этюд определенных маршрутов», Comptes Rendus de l'Académie des Sciences (на французском языке), 206 : 310–313
- ^ Флорек, Казимеж (1951), «Sur la liaison et la Division des points d'un ensemble fini», Colloquium Mathematicum (на французском языке), 2 : 282–285
- ^ Соллин, М. (1965), "Le tracé de canalisation", Программирование, игры и транспортные сети (на французском языке)
- ^ Эппштейн, Дэвид (1999), «Связывающие деревья и гаечные ключи», в Sack, J.-R. ; Уррутия, Дж. (Ред.), Справочник по вычислительной геометрии , Elsevier, стр. 425–461.; Мареш, Мартин (2004), "Два алгоритма линейного времени для MST на второстепенных классах замкнутых графов" (PDF) , Archivum Mathematicum , 40 (3): 315–320.
- ^ Каргер, Дэвид Р .; Klein, Philip N .; Тарьян, Роберт Е. (1995), «Рандомизированное алгоритм линейного времени , чтобы найти минимум связующих деревьев», Журнал Ассоциации вычислительной техники , 42 (2): 321-328, DOI : 10,1145 / 201019,201022 , MR 1409738
- ^ «Отакар Борувка» , Университет Масарика в Брно
- ^ Нойман, Франтишек (1979), «Восьмидесятилетие академика Отакара Борувки» , Чехословацкий математический журнал , 29 (2): 330–335, MR 0529522 , Zbl 0397.01006.
Внешние ссылки
- Борувка, Отакар , Чешская электронная математическая библиотека