Hispanopedia Wiki
Articulo de referencia

Yefim Dinitz

"},"website":{"wt":"https://www.cs.bgu.ac.il/~dinitz/"},"education":{"wt":""},"school_tradition":{"wt":"Moscow school of polynomial-time algorithms"},"academic_advisors":{"wt":"...

Hispanopedia WikiContenido en espanolLectura gratuita

Yefim Dinitz ( en ruso : Ефим Абрамович Диниц , [ 2 ] en hebreo : יפים דיניץ ) es un científico informático soviético e israelí asociado a la escuela de Moscú de algoritmos de tiempo polinomial. [ 3 ] Inventó el algoritmo de Dinic para calcular el flujo máximo, [ 4 ] y fue uno de los inventores del algoritmo de los Cuatro Rusos para multiplicar matrices booleanas o módulo 2. [ 5 ] : 243, 250

Formación y primeros trabajos en el grupo Adelson-Velsky.

Dinitz estudió una maestría en el grupo de Georgy Adelson-Velsky en la Universidad Estatal de Moscú. [ 4 ] [ 6 ] [ 3 ] En 1969, Adelson-Velsky inició un seminario sobre algoritmos, que sus estudiantes y otros cercanos a él describirían más tarde como "el centro de la actividad científica en algoritmia de tiempo polinomial en Moscú". [ 3 ] Fue un ejercicio en la "clase de algoritmos de Adel'son-Vel'sky", según Dinitz, lo que condujo al desarrollo del algoritmo de Dinic en 1969. [ 4 ] Mirando hacia atrás, Dinitz y sus compañeros de clase escribirían que el diseño del algoritmo reflejaba la atmósfera del grupo de Adelson-Velsky. [ 3 ] En palabras de Dinitz: [ 4 ]

Nosotros, los estudiantes de Adel'son-Vel'sky, asimilamos todo el paradigma de la escuela de computación soviética a partir de sus clases. Este paradigma consistía en el afán de desarrollar algoritmos económicos basados ​​en la investigación profunda de un problema y en el uso de un mantenimiento inteligente de la estructura de datos y un análisis amortizado del tiempo de ejecución como componentes necesarios. … Por lo tanto, no fue sorprendente que mi algoritmo de flujo de red, inventado en enero de 1969, mejorara el algoritmo de Ford y Fulkerson mediante el uso y mantenimiento de una estructura de datos de red por capas y el empleo de un análisis amortizado preciso del tiempo de ejecución.

Dinitz publicó el algoritmo en 1970. [ 7 ] [ 8 ]

A principios de 1969, Dinitz también trabajaba en el problema de asignación con su compañero de clase Mikhail Kronrod, contribuyendo al conjunto de trabajos en los que "comenzó en serio la búsqueda de algoritmos de asignación más rápidos". [ 9 ] [ 4 ] [ 10 ] El algoritmo que Dinitz y Kronrod publicaron más tarde ese año podía resolver el problema de asignación para grafos de n vértices en O ( n 3 ) pasos. [ 9 ] [ 11 ]

Durante su tiempo en el seminario de algoritmos de Adelson-Velsky, Dinitz y Kronrod se cruzaron con Vladimir Arlazarov e Igor Faradjev, dos jóvenes matemáticos que trabajaban en el Laboratorio Matemático del ITEP . [ 12 ] [ 6 ] El laboratorio fue dirigido, hasta un incidente político en 1968-1969, por el hermano académico y colaborador de larga data de Adelson-Velsky, Aleksandr Kronrod . [ 6 ] [ 13 ] En 1970, Dinitz, Mikhail Kronrod, Arlazarov y Faradjev publicaron el algoritmo de multiplicación de matrices booleanas que los haría famosos como los "Cuatro Rusos" . [ 14 ] [ 15 ]

Trabajo en Moscú tras el grupo Adelson-Velsky

Adelson-Velsky también firmó la carta de 1968 que llevó al despido de Aleksandr Kronrod del ITEP en 1969. En 1970, la Facultad de Mecánica y Matemáticas graduó a todo el grupo de estudiantes de Adelson-Velsky, y a este se le prohibió impartir clases en la Universidad Estatal de Moscú. [ 6 ] Sin embargo, Dinitz continuó trabajando en algoritmos de flujo. Escribió una tesis doctoral en la Universidad Estatal de Moscú sobre problemas de flujo de mercancías, que presentó en 1972. [ 16 ] [ 17 ] Desarrolló la idea de escalamiento de capacidad independientemente de Edmonds y Karp , quienes la acababan de introducir en Occidente, y la utilizó para inventar uno de los primeros algoritmos de tiempo polinomial para el problema de flujo de costo mínimo . [ 16 ] [ 3 ] [ 18 ]

Dinitz también se mantuvo en contacto con su compañero de clase Aleksandr Karzanov, publicando con él un artículo sobre el problema del flujo de costo mínimo en 1974. [ 6 ] [ 4 ] [ 10 ] [ 16 ] En 1975, Dinitz y Karzanov se unieron a Adelson-Velsky para publicar un libro sobre algoritmos de flujo de red, que "describía muchos resultados importantes... que fueron descubiertos independientemente más tarde (y en algunos casos mucho más tarde) en Occidente". [ 16 ] [ 10 ] [ 4 ]

Publicidad en Occidente

En 1974, Shimon Even y su estudiante de posgrado Alon Itai, del Technion, se interesaron por el algoritmo de flujo máximo de Dinitz, así como por un algoritmo de flujo de red que Karzanov había publicado casi al mismo tiempo. [ 4 ] La descripción del algoritmo de Dinitz era muy concisa, debido a las limitaciones de espacio de la revista, pero Even e Itai lograron descifrar la mayor parte, gracias en parte a la explicación explícita de Karzanov de un concepto implícito en el artículo de Dinitz. [ 4 ] Tras completar la última parte con una nueva técnica propia, Even e Itai obtuvieron una versión funcional del algoritmo de Dinitz, que Even dio a conocer en charlas en numerosas universidades occidentales. [ 4 ]

El nombre de Dinitz se transcribió como "EA Dinic" en la traducción al inglés de su artículo, por lo que la versión de Even e Itai de su algoritmo se conoció como el algoritmo de Dinic en Occidente, y su nombre se transcribió incorrectamente como [dinik] en lugar de [dinits] en ese contexto. [ 4 ]

Posteriormente trabajó en el Technion y en la Universidad Ben-Gurion.

En la década de 1990, Even finalmente tuvo la oportunidad de aprender la versión original del algoritmo de Dinitz del propio Dinitz. [ 4 ] En 1992, Dinitz publicó un artículo sobre la red mariposa con Even y otros dos científicos informáticos del Technion, indicando su afiliación como Universidad Ben-Gurion. Según se informa, Dinitz recordaría más tarde que Even luchó con éxito para que lo contrataran como profesor asociado en el Technion. [ 19 ] Indicó su afiliación como Technion en un artículo publicado en 1994, y asesoró a un estudiante de doctorado del Technion en 1997. [ 20 ] [ 21 ] Dinitz se unió al departamento de ciencias de la computación de la Universidad Ben-Gurion en 1998, y el departamento celebró una fiesta de jubilación en su honor en 2019. [ 22 ]

Debido a sus publicaciones con Shlomo Moran y Shmuel Zaks a finales de la década de 1990 y en la década de 2000, Dinitz tiene un número de Erdős de dos. [ 23 ] [ 24 ]

Referencias

  1. ↑ "Yefim Dinitz" . Portal de investigación de la Universidad Ben-Gurion . Consultado el 23 de diciembre de 2023 .
  2. ↑Диниц Ефим Абрамович[ Dinitz Yefim Abramovich ] . ИСТИНА ISTINA . Consultado el 23 de diciembre de 2023 .
  3. 1 2 3 4 5 Arlázarov, VL; Dinitz, EA; Ilyashenko, Yu. S. ; Karzanov, AV; Karpenko, SM; Kirillov, AA ; Konstantinov, NN ; Kronrod, MA; Kuznetsov, OP; Bueno, LB ; Pevzner, PA ; Semenov, AL ; Faradzhev, IA; Cherkasskii, BV; Khovanskii, AG (2014). "Georgy Maksimovich Adelson-Velsky (obituario)". Encuestas matemáticas rusas . 69 (4): 743– 751. Bibcode : 2014RuMaS..69..743A . doi : 10.1070/RM2014v069n04ABEH004909 . S2CID 123048550 . 
  4. 1 2 3 4 5 6 7 8 9 10 11 12 Dinitz, Yefim (2006). "El algoritmo de Dinitz: la versión original y la versión de Even" . En Goldreich, Oded ; Rosenberg, Arnold L .; Selman, Alan L. (eds.). Informática teórica: ensayos en memoria de Shimon Even . Lecture Notes in Computer Science. Vol. 3895. Springer. pp. 218–240 . doi : 10.1007/11685654_10 . ISBN   978-3-540-32880-3.
  5. ↑ Aho, Alfred V.; Hopcroft , John E .; Ullman, Jeffrey D. (1974). El diseño y análisis de algoritmos informáticos . Addison-Wesley. ISBN 978-0-201-00029-0OCLC 1147299​​ 
  6. 1 2 3 4 5 Donskoy, Mikhail .Historia «Каиссы»[ Historia de "Kaissa" ] . Виртуальный Компьютерный Музей [Museo Ruso de Computación Virtual] . Consultado el 25 de diciembre de 2023 .
  7. ↑ "Un algoritmo para la solución del problema del flujo máximo en una red con estimación de potencia" . Math-Net.Ru . Consultado el 24 de diciembre de 2023 .
  8. ↑ EA Dinic (1970). "Algoritmo para la solución de un problema de flujo máximo en una red con estimación de potencia" (PDF) . Doklady Akademii Nauk SSSR . 11 : 1277–1280 .
  9. 1 2 Duan, Ran; Pettie, Seth (1 de enero de 2014). "Aproximación en tiempo lineal para la coincidencia de peso máximo" (PDF) . Journal of the ACM . 61 : 1–23 . doi : 10.1145/2529989 . S2CID 207208641 . 
  10. ^ Shalyto , А. A. (12 de abril de 2022).Сто лет со дня рождения Георгия Максимовича Адельсона-Вельского[ Cien años desde el día del nacimiento de Georgy Adelson-Velsky ] . Виртуальный Компьютерный Музей [;Museo Ruso de Computadoras Virtuales] . Consultado el 25 de diciembre de 2023 .
  11. ↑ Dinitz, YA ; Kronrod, MA (1969). "Un algoritmo para resolver el problema de asignación". Doklady Akademii Nauk SSSR . 189 (1): 23–25 .
  12. ↑ Faradjev, IA (2020).Simetría y regulación. Как это начиналось к чему привело[ Simetría y regularidad. Cómo empezó y a qué condujo ] . Información sobre tecnologías y sistemas de información (4): 71– 77. doi : 10.14357/20718632200406 . S2CID 241168270 . 
  13. ↑ Landis, EM ; Yaglom, IM (2002). Gautschi, Walter (ed.). "Recordando a AS Kronrod" . Math . Intelligencer . 24 (1). Traducido por Brudno, Viola: 22–30 . doi : 10.1007/BF03025307 . S2CID 119452130. Archivado del original el 21 de julio de 2006. 
  14. ↑ Chan, Timothy M. (2015). "Acelerando el algoritmo de los cuatro rusos en aproximadamente un factor logarítmico más". Actas del Simposio Anual ACM-SIAM de 2015 sobre Algoritmos Discretos (SODA) . Sociedad de Matemáticas Industriales y Aplicadas . págs. 212–217 . doi : 10.1137/1.9781611973730.16 . ISBN  978-1-61197-374-7.
  15. ↑ "Sobre la construcción económica del cierre transitivo de un grafo orientado" . Math-Net.Ru . Consultado el 24 de diciembre de 2023 .
  16. ^ Goldberg , Andrew V .; Gusfield, Dan (junio de 1991). "Потоковые Алгоритмы (Algoritmos de flujo) (GM Adel'son-Vel'ski, EA Dinits y AV Karzanov)" . Revisión SIAM . 33 (2): 306– 314. doi : 10.1137/1033075 .Reseña del libro.
  17. ↑ Dinist, EA (1972).Экономные Алгоритмы Решения Задач Транспортного Типа[ Algoritmos eficientes para resolver problemas de transporte ] (tesis doctoral) (en ruso).
  18. ↑ Dinist, EA (1973). Método de transporte de mercancías Неязок y Транспортные Задачи[ El método de escalamiento y problemas de transporte ] . En Fridman, AA (ed.).Исследования по Дискретной Математике[ Estudios en Matemáticas Discretas ] . Moscú: Наука [ Ciencia ].
  19. ↑ Goldreich, Oded (noviembre de 2003). Charla de Yefim Dinitz en la fiesta de Shimon Even .Transcripción del discurso de Dinitz en la fiesta de jubilación de Shimon Even .
  20. ↑ Dinitz, Yefim ; Vainshtein, Alek (23 de mayo de 1994). «El esqueleto de conectividad de un subconjunto de vértices en un grafo y su mantenimiento incremental» . Actas del vigésimo sexto simposio anual de la ACM sobre Teoría de la Computación . ACM . doi : 10.1145/195058.195442 . ISBN 978-0-89791-663-9.
  21. ↑ "Tesis de doctorado y maestría" . Technion . Archivado del original el 27 de diciembre de 2023. Consultado el 27 de diciembre de 2023 .
  22. ↑ברכות לפרופ' יפים דיניץ על פרישתו לגמלאותUniversidad Ben-Gurion . 14 de enero de 2020. Archivado del original el 15 de agosto de 2021.
  23. ↑ Grossman, Jerry (7 de agosto de 2020). "Erdos2" . 2020.
  24. ↑ «Dinitz, Yefim» . zbMATH Abierto .