Ефим Диниц

Ефим Диниц
Ефим Диниц
Рожденный	Ефим Абрамович Диниц
Другие имена	Э. А. Динич
Заголовок	Почетный профессор
Академическое образование
Академические консультанты	Георгий Адельсон-Вельский ; Шимон Эвен
Академическая работа
Дисциплина	Ученый-компьютерщик
Школа или традиция	Московская школа полиномиальных алгоритмов
Учреждения	Московский Государственный Университет ; Технион ; Университет Бен-Гуриона
Известные работы	Алгоритм Динича ; Метод четырёх русских
Веб-сайт	https://www.cs.bgu.ac.il/~dinitz/

Yefim Dinitz ( Russian : Ефим Абрамович Диниц , ^{[ 2 ]} Иврит : יפים דיניץ ) — советский и израильский учёный-компьютерщик, связанный с Московской школой алгоритмов с полиномиальным временем. ^{[ 3 ]} Он изобрел алгоритм Динича для расчета максимального потока. ^{[ 4 ]} и он был одним из изобретателей алгоритма четырех русских для умножения булевых матриц или матриц по модулю 2 . ^{[ 5 ]}^{: 243, 250}

Образование и начало работы в группе Адельсона-Вельского

Диниц учился в магистратуре в группе Георгия Адельсона-Вельского в МГУ. ^{[ 4 ]}^{[ 6 ]}^{[ 3 ]} В 1969 году Адельсон-Вельский открыл семинар по алгоритмам, который его ученики и другие близкие к нему люди позже назовут «центром научной деятельности по полиномиальной алгоритмике в Москве». ^{[ 3 ]} По словам Диница, именно упражнение в «классе алгоритмов Адельсона-Вельского» привело к разработке алгоритма Диница в 1969 году. ^{[ 4 ]} Оглядываясь назад, Диниц и его одноклассники напишут, что конструкция алгоритма отражала атмосферу группы Адельсона-Вельски. ^{[ 3 ]} По словам Диница: ^{[ 4 ]}

Мы, ученики Адельсона-Вельского, впитали из его лекций всю парадигму советской вычислительной школы. Эта парадигма заключалась в стремлении разрабатывать экономичные алгоритмы, основанные на глубоком исследовании проблемы и использовании интеллектуального обслуживания структуры данных и анализа амортизированного времени выполнения в качестве необходимых компонентов. … Следовательно, неудивительно, что мой алгоритм сетевого потока, изобретенный в январе 1969 года, улучшил алгоритм Форда и Фулкерсона, используя и поддерживая многоуровневую структуру сетевых данных и применяя тонкий амортизированный анализ времени работы.

Диниц опубликовал алгоритм в 1970 году. ^{[ 7 ]}^{[ 8 ]}

В начале 1969 года Диниц также работал над задачей присваивания вместе со своим одноклассником Михаилом Кронродом, внося свой вклад в объем работ, в которых «всерьез начался поиск более быстрых алгоритмов присваивания». ^{[ 9 ]}^{[ 4 ]}^{[ 10 ]} Алгоритм Диница и Кронрода, опубликованный позже в том же году, мог решить проблему назначения для $n$ графов с $вершинами в O (n 3)$ шаги. ^{[ 9 ]}^{[ 11 ]}^{[ 12 ]}

Во время посещения семинара Адельсона-Вельского по алгоритмам Диниц и Кронрод познакомились с Владимиром Арлазаровым и Игорем Фараджевым — двумя молодыми математиками, работавшими в математической лаборатории ИТЭФ . ^{[ 13 ]}^{[ 14 ]}^{[ 6 ]} в 1968–1969 годах лабораторией руководил До политического инцидента и сестра Адельсона-Вельского академический брат и давний соратник Александр Кронрод . ^{[ 6 ]}^{[ 15 ]} В 1970 году Диниц, Михаил Кронрод, Арлазаров и Фараджев опубликовали алгоритм умножения булевых матриц , который прославил их как «Четыре русских» . ^{[ 16 ]}^{[ 17 ]}^{[ 18 ]}

Работа в Москве после группы Адельсона-Вельского

Адельсон-Вельский также подписал письмо 1968 года, которое привело к увольнению Александра Кронрода из ИТЭФ в 1969 году. В 1970 году механико-математический факультет окончила вся студенческая группа Адельсона-Вельского, и Адельсону-Вельскому запретили преподавать в МГУ. ^{[ 6 ]} Однако Диниц продолжал работать над алгоритмами потока. Он написал докторскую диссертацию МГУ. диссертацию по проблемам товарных потоков, которую он представил в 1972 году. ^{[ 19 ]}^{[ 20 ]} Он разработал идею масштабирования мощности независимо от Эдмондса и Карпа , которые только что представили ее на Западе, и использовал ее для изобретения одного из первых алгоритмов с полиномиальным временем для решения задачи потока с минимальной стоимостью . ^{[ 19 ]}^{[ 3 ]}^{[ 21 ]}

Диниц также поддерживал связь со своим одноклассником Александром Карзановым, опубликовав вместе с ним статью по проблеме потока с минимальными затратами в 1974 году. ^{[ 6 ]}^{[ 4 ]}^{[ 10 ]}^{[ 19 ]}^{[ 22 ]} В 1975 году Диниц и Карзанов присоединились к Адельсону-Вельскому в публикации книги об алгоритмах сетевых потоков, в которой «описываются [d] многие важные результаты… которые были независимо открыты позже (а в некоторых случаях намного позже) на Западе». ^{[ 19 ]}^{[ 23 ]}^{[ 10 ]}^{[ 4 ]}

Реклама на Западе

В 1974 году Шимон Эвен и его аспирант Алон Итай из Техниона заинтересовались алгоритмом максимального потока Диница, а также алгоритмом сетевого потока, который Карзанов опубликовал примерно в то же время. ^{[ 4 ]} Описание алгоритма, данное Диницем, было очень сжатым из-за ограничений по страницам журнала, но Эвену и Итаи удалось расшифровать большую его часть, отчасти благодаря явному объяснению Карзановым концепции, которая подразумевалась в статье Диница. ^{[ 4 ]} Заполнив последний пробел собственной новой техникой, Эвен и Итай получили рабочую версию алгоритма Диница, которую Эвен обнародовал на переговорах во многих западных университетах. ^{[ 4 ]}

Имя Диница было транслитерировано как «EA Dinic» в английском переводе его статьи, поэтому версия его алгоритма Эвена и Итая стала известна как алгоритм Диница на Западе , а его имя было «неправильно отображено как [dinik] вместо [dinits] "в этом контексте. ^{[ 4 ]}

Позже работа в Технионе и Университете Бен-Гуриона.

В 1990-е годы Эвен наконец получил возможность изучить оригинальную версию алгоритма Диница у самого Диница. ^{[ 4 ]} В 1992 году Диниц вместе с Эвеном и двумя другими учеными-компьютерщиками Техниона опубликовал статью о сети «бабочка» , указав, что он является Университетом Бен-Гуриона. Сообщается, что позже Диниц вспоминал, что Эвен успешно боролся за то, чтобы его наняли доцентом в Технионе. ^{[ 24 ]} Он указал свою принадлежность к Техниону в статье, опубликованной в 1994 году, и консультировал доктора философии Техниона. студентка 1997 года. ^{[ 25 ]}^{[ 26 ]} Диниц поступил на факультет компьютерных наук Университета Бен-Гуриона в 1998 году, а в 2019 году факультет организовал для него празднование выхода на пенсию. ^{[ 27 ]}

Благодаря его публикациям с Шломо Мораном и Шмуэлем Заксом в конце 1990-х и в 2000-х годах, Диниц имеет число Эрдеша, равное двум. ^{[ 28 ]}^{[ 29 ]}

Ссылки

^ «Ефим Диниц» . Университета Бен-Гуриона Исследовательский портал . Проверено 23 декабря 2023 г.
^ Диниц Ефим Абрамович [Dinitz Yefim Abramovich]. ИСТИНА ISTINA . Retrieved 23 December 2023 .
^ Перейти обратно: ^а ^б ^с ^д ^и Arlazarov, V. L.; Dinitz, E. A.; Ilyashenko, Yu. S. ; Karzanov, A. V.; Karpenko, S. M.; Kirillov, A. A. ; Konstantinov, N. N. ; Kronrod, M. A.; Kuznetsov, O. P.; Okun', L. B. ; Pevzner, P. A. ; Semenov, A. L. ; Faradzhev, I. A.; Cherkasskii, B. V.; Khovanskii, A. G. (2014). "Georgy Maksimovich Adelson-Velsky (obituary)". Russian Mathematical Surveys . 69 (4): 743–751. Bibcode : 2014RuMaS..69..743A . doi : 10.1070/RM2014v069n04ABEH004909 . S2CID 123048550 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Диниц, Ефим (2006). «Алгоритм Диница: оригинальная версия и версия Эвена» . В Гольдрейхе, Одед ; Розенберг, Арнольд Л .; Селман, Алан Л. (ред.). Теоретическая информатика: Очерки памяти Шимона Эвена . Конспекты лекций по информатике. Том. 3895. Спрингер. стр. 218–240. дои : 10.1007/11685654_10 . ISBN 978-3-540-32880-3 .
^ Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974). Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. ISBN 978-0-201-00029-0 . ОСЛК 1147299 .
^ Перейти обратно: ^а ^б ^с ^д ^и Donskoy, Mikhail . История «Каиссы» [History of "Kaissa"]. Виртуальный Компьютерный Музей [Russian Virtual Computer Museum] . Retrieved 25 December 2023 .
^ «Алгоритм решения задачи максимального потока в сети с оценкой мощности» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.
^ Э. А. Динич (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности» (PDF) . Доклады Академии наук СССР . 11 : 1277–1280.
^ Перейти обратно: ^а ^б Дуан, Ран; Петти, Сет (1 января 2014 г.). «Приближение линейного времени для согласования максимального веса» (PDF) . Журнал АКМ . 61 : 1–23. дои : 10.1145/2529989 . S2CID 207208641 .
^ Перейти обратно: ^а ^б ^с Shalyto, А. А. (12 April 2022). Сто лет со дня рождения Георгия Максимовича Адельсона-Вельского [A hundred years since the day of birth of Georgy Adelson-Velsky]. Виртуальный Компьютерный Музей [;Russian Virtual Computer Museum] . Retrieved 25 December 2023 .
^ «Алгоритм решения задачи о назначениях» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.
^ Диниц, Ю.А. ; Кронрод, Массачусетс (1969). «Алгоритм решения задачи о назначениях». Доклады Академии наук СССР . 189 (1): 23–25.
^ Фараджев, Игорь (1–7 июля 2018 г.). «Симметрия против регулярности». Как это началось и к чему привело . Симметрия против регулярности: первые 50 лет после стабилизации Вейсфейлера-Лемана . Пльзень. Разговорные слайды.
^ Фараджев И.А. (2020). Симметрия и регулярность. Как это начиналось и к чему привело [Симметрия и регулярность. Как это началось и к чему привело. ИТиВС [JITCS] (4): 71–77. дои : 10.14357/20718632200406 . S2CID 241168270 .
^ Лэндис, EM ; Яглом, И.М. (2002). Гаучи, Уолтер (ред.). «Вспоминая А. С. Кронрода» . Математика. Интеллигент . 24 (1). Перевод Брудно, Альт: 22–30. дои : 10.1007/BF03025307 . S2CID 119452130 . Архивировано из оригинала 21 июля 2006 г.
^ Чан, Тимоти М. (2015). «Ускорение алгоритма четырех русских еще примерно на один логарифмический коэффициент». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2015 г. Общество промышленной и прикладной математики . стр. 212–217. дои : 10.1137/1.9781611973730.16 . ISBN 978-1-61197-374-7 .
^ «Об экономичном построении транзитивного замыкания ориентированного графа» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.
^ Arlazarov, V. L. ; Dinitz, Y. A. ; Kronrod, M. A.; Faradžev, I. A. (1970). Об экономном построении транзитивного замыкания ориентированного графа «Об экономичном построении транзитивного замыкания ориентированного графа». Доклады Академии наук СССР . 194 (11). Первоначально опубликовано как: Арлазаров, В. Л. ; Диниц, Э. А. ; Кронрод, М. А.; Фараджев, И. А. (1970). Об экономном построении транзитивного замыкания ориентированного графа . Доклады Академии Наук СССР . 134 (3).
^ Перейти обратно: ^а ^б ^с ^д Goldberg, Andrew V.; Gusfield, Dan (June 1991). "Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov)" . SIAM Review . 33 (2): 306–314. doi : 10.1137/1033075 . Book review.
^ Диниц, E. A. (1972). Экономные Алгоритмы Решения Задач Транспортного Типа [ Эффективные алгоритмы решения транспортных задач ] (кандидатская диссертация) (на русском языке).
^ Диниц, E. A. (1973). Метод Поразрядного Сокращения Неязок и Транспортные Задачи [Метод масштабирования и транспортных задач]. Фридман А.А. (ред.). Исследования по Дискретной Математике [ Исследования по дискретной математике ]. Москва: Наука .
^ Диниц, E. A. ; Карзанов, А. В. (1974). "Об Экспоненциалъной Сложсности Алгоритмов Решения Общей и Транспортной Задач Линейного Програмироеания" [On Exponential Complexity of Algorithms for the General and Transportation Linear Programming Problems]. Труды XIX Конференций Молодых Ученых ИАТ . Moscow.
^ Адельсон-Вельский, Г . М. ; Диниц, EA ; Карзанов, А. В. (1975). Потоковые алгоритмы [ Алгоритмы сетевых потоков ]. Москва: Наука .
^ Гольдрейх, Одед (ноябрь 2003 г.). Ефим Диниц выступает на вечеринке Шимона Эвена . Стенограмма речи Диница на вечеринке по случаю выхода на пенсию Шимона Эвена .
^ Диниц, Ефим ; Вайнштейн, Алек (23 мая 1994 г.). «Каркас связности подмножества вершин в графе и его постепенное обслуживание» . Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений . АКМ . дои : 10.1145/195058.195442 . ISBN 978-0-89791-663-9 .
^ «Кандидатские и магистерские диссертации» . Технион . Проверено 27 декабря 2023 г.
^ Поздравляем профессора Яфима Диница с выходом на пенсию . Университет Бен-Гуриона . 14 января 2020 года. Архивировано из оригинала 15 августа 2021 года.
^ Гроссман, Джерри (7 августа 2020 г.). «Эрдос2» . 2020.
^ «Диниц, Ефим» . zbMATH Открыть .

Внешние ссылки

«Ефим Диниц» . Цифровая библиотека ACM .

[dinitz_profile_ben-gurion-1] «Ефим Диниц» . Университета Бен-Гуриона Исследовательский портал . Проверено 23 декабря 2023 г.

[dinitz_profile_istina-2] Диниц Ефим Абрамович [Dinitz Yefim Abramovich]. ИСТИНА ISTINA . Retrieved 23 December 2023 .

[adelson-velsky_obit-3] Перейти обратно: ^а ^б ^с ^д ^и Arlazarov, V. L.; Dinitz, E. A.; Ilyashenko, Yu. S. ; Karzanov, A. V.; Karpenko, S. M.; Kirillov, A. A. ; Konstantinov, N. N. ; Kronrod, M. A.; Kuznetsov, O. P.; Okun', L. B. ; Pevzner, P. A. ; Semenov, A. L. ; Faradzhev, I. A.; Cherkasskii, B. V.; Khovanskii, A. G. (2014). "Georgy Maksimovich Adelson-Velsky (obituary)". Russian Mathematical Surveys . 69 (4): 743–751. Bibcode : 2014RuMaS..69..743A . doi : 10.1070/RM2014v069n04ABEH004909 . S2CID 123048550 .

[even's_version-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Диниц, Ефим (2006). «Алгоритм Диница: оригинальная версия и версия Эвена» . В Гольдрейхе, Одед ; Розенберг, Арнольд Л .; Селман, Алан Л. (ред.). Теоретическая информатика: Очерки памяти Шимона Эвена . Конспекты лекций по информатике. Том. 3895. Спрингер. стр. 218–240. дои : 10.1007/11685654_10 . ISBN 978-3-540-32880-3 .

[alg_design_&_analysis-5] Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974). Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. ISBN 978-0-201-00029-0 . ОСЛК 1147299 .

[history_of_kaissa-6] Перейти обратно: ^а ^б ^с ^д ^и Donskoy, Mikhail . История «Каиссы» [History of "Kaissa"]. Виртуальный Компьютерный Музей [Russian Virtual Computer Museum] . Retrieved 25 December 2023 .

[max_flow_profile_mathnet-7] «Алгоритм решения задачи максимального потока в сети с оценкой мощности» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.

[max_flow-8] Э. А. Динич (1970). «Алгоритм решения задачи максимального потока в сети с оценкой мощности» (PDF) . Доклады Академии наук СССР . 11 : 1277–1280.

[lin_appx_max_wt-9] Перейти обратно: ^а ^б Дуан, Ран; Петти, Сет (1 января 2014 г.). «Приближение линейного времени для согласования максимального веса» (PDF) . Журнал АКМ . 61 : 1–23. дои : 10.1145/2529989 . S2CID 207208641 .

[adelson-velsky_centennial-10] Перейти обратно: ^а ^б ^с Shalyto, А. А. (12 April 2022). Сто лет со дня рождения Георгия Максимовича Адельсона-Вельского [A hundred years since the day of birth of Georgy Adelson-Velsky]. Виртуальный Компьютерный Музей [;Russian Virtual Computer Museum] . Retrieved 25 December 2023 .

[assign_prob_profile_mathnet-11] «Алгоритм решения задачи о назначениях» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.

[assign_prob-12] Диниц, Ю.А. ; Кронрод, Массачусетс (1969). «Алгоритм решения задачи о назначениях». Доклады Академии наук СССР . 189 (1): 23–25.

[symmetry_vs_regularity_slides-13] Фараджев, Игорь (1–7 июля 2018 г.). «Симметрия против регулярности». Как это началось и к чему привело . Симметрия против регулярности: первые 50 лет после стабилизации Вейсфейлера-Лемана . Пльзень. Разговорные слайды.

[symmetry_vs_regularity_paper-14] Фараджев И.А. (2020). Симметрия и регулярность. Как это начиналось и к чему привело [Симметрия и регулярность. Как это началось и к чему привело. ИТиВС [JITCS] (4): 71–77. дои : 10.14357/20718632200406 . S2CID 241168270 .

[a_s_kronrod_memorial-15] Лэндис, EM ; Яглом, И.М. (2002). Гаучи, Уолтер (ред.). «Вспоминая А. С. Кронрода» . Математика. Интеллигент . 24 (1). Перевод Брудно, Альт: 22–30. дои : 10.1007/BF03025307 . S2CID 119452130 . Архивировано из оригинала 21 июля 2006 г.

[one_more_log_factor-16] Чан, Тимоти М. (2015). «Ускорение алгоритма четырех русских еще примерно на один логарифмический коэффициент». Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2015 г. Общество промышленной и прикладной математики . стр. 212–217. дои : 10.1137/1.9781611973730.16 . ISBN 978-1-61197-374-7 .

[econ_construct_profile_mathnet-17] «Об экономичном построении транзитивного замыкания ориентированного графа» . Мат-Нет.Ру . Проверено 24 декабря 2023 г.

[econ_construct-18] Arlazarov, V. L. ; Dinitz, Y. A. ; Kronrod, M. A.; Faradžev, I. A. (1970). Об экономном построении транзитивного замыкания ориентированного графа «Об экономичном построении транзитивного замыкания ориентированного графа». Доклады Академии наук СССР . 194 (11). Первоначально опубликовано как: Арлазаров, В. Л. ; Диниц, Э. А. ; Кронрод, М. А.; Фараджев, И. А. (1970). Об экономном построении транзитивного замыкания ориентированного графа . Доклады Академии Наук СССР . 134 (3).

[flow_algs_rev-19] Перейти обратно: ^а ^б ^с ^д Goldberg, Andrew V.; Gusfield, Dan (June 1991). "Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov)" . SIAM Review . 33 (2): 306–314. doi : 10.1137/1033075 . Book review.

[efficient_transport-20] Диниц, E. A. (1972). Экономные Алгоритмы Решения Задач Транспортного Типа [ Эффективные алгоритмы решения транспортных задач ] (кандидатская диссертация) (на русском языке).

[scaling_transport-21] Диниц, E. A. (1973). Метод Поразрядного Сокращения Неязок и Транспортные Задачи [Метод масштабирования и транспортных задач]. Фридман А.А. (ред.). Исследования по Дискретной Математике [ Исследования по дискретной математике ]. Москва: Наука .

[exp_transport-22] Диниц, E. A. ; Карзанов, А. В. (1974). "Об Экспоненциалъной Сложсности Алгоритмов Решения Общей и Транспортной Задач Линейного Програмироеания" [On Exponential Complexity of Algorithms for the General and Transportation Linear Programming Problems]. Труды XIX Конференций Молодых Ученых ИАТ . Moscow.

[flow_algs-23] Адельсон-Вельский, Г . М. ; Диниц, EA ; Карзанов, А. В. (1975). Потоковые алгоритмы [ Алгоритмы сетевых потоков ]. Москва: Наука .

[even's_party-24] Гольдрейх, Одед (ноябрь 2003 г.). Ефим Диниц выступает на вечеринке Шимона Эвена . Стенограмма речи Диница на вечеринке по случаю выхода на пенсию Шимона Эвена .

[connect_carcass-25] Диниц, Ефим ; Вайнштейн, Алек (23 мая 1994 г.). «Каркас связности подмножества вершин в графе и его постепенное обслуживание» . Материалы двадцать шестого ежегодного симпозиума ACM по теории вычислений . АКМ . дои : 10.1145/195058.195442 . ISBN 978-0-89791-663-9 .

[dinitz_theses-26] «Кандидатские и магистерские диссертации» . Технион . Проверено 27 декабря 2023 г.

[dinitz_retirement-27] Поздравляем профессора Яфима Диница с выходом на пенсию . Университет Бен-Гуриона . 14 января 2020 года. Архивировано из оригинала 15 августа 2021 года.

[erdos2-28] Гроссман, Джерри (7 августа 2020 г.). «Эрдос2» . 2020.

[dinitz_profile_zbmath-29] «Диниц, Ефим» . zbMATH Открыть .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]