Vitani, Pablo

Paul Michael Béla Vitányi es un eminente científico holandés en el campo de la informática teórica , la teoría de los algoritmos y la complejidad computacional , profesor de la Universidad de Ámsterdam e investigador del Centro de Matemáticas e Informática . Vitani es holandés por madre y húngaro por padre.

Paul Vitani recibió un título de ingeniería en 1971 de la Universidad Tecnológica de Delft , en el mismo año ingresó a la escuela de posgrado en el Centro Matemático de Amsterdam, donde todavía trabaja (ahora este instituto de investigación se llama "Centro de Matemáticas e Informática") . Defendió su tesis doctoral sobre " Sistemas de Lindenmeier : estructura, lenguajes y funciones de crecimiento" [2] en 1978 en la Universidad Libre de Amsterdam y pronto se convirtió en el jefe del departamento recién creado, que trajo al mundo. nivel en el campo de la computación cuántica, algoritmos distribuidos, información de teoría algorítmica y cálculos adiabáticos reversibles. En 2003, recibió una transferencia al puesto de investigador honorario (CWI Fellow) [3] . En 2005 recibió la cátedra más alta (hoogleraar 1 [4] ) en la universidad más grande de los Países Bajos. En 2007 fue nombrado caballero de la Orden del León de los Países Bajos [5] . En 2011 fue elegido miembro de la Academia Europea de Ciencias [4] . Al igual que muchos científicos de su nivel, Paul Vitani realizó una gran cantidad de trabajo editorial en las principales revistas de su campo y, a menudo, fue invitado a conferencias y talleres para presentaciones plenarias [6] .

Contribución a la ciencia

Los sistemas de Lindenmeier, también llamados sistemas L, en los que Paul Vitani trabajó como estudiante de posgrado, son sistemas de reescritura que están relacionados con las gramáticas formales [7] y se diferencian principalmente en que en cada paso de inferencia la regla se aplica no a uno elegido (no -terminal), sino a todos los caracteres de la cadena al mismo tiempo. Inicialmente, los sistemas L fueron propuestos por el botánico Aristide Lindenmeier para modelar el desarrollo de organismos unicelulares y otras estructuras ramificadas. Vitani los consideró desde un punto de vista formal y aclaró muchos puntos respecto a las clases de lenguajes generados por los sistemas L, así como el uso de no terminales y homomorfismos . En particular, mostró que si en sistemas L deterministas (es decir, aquellos en los que el árbol de derivación no ramifica) consideramos una familia de extensiones (lenguajes generados por no terminales), entonces no contendrá completamente la clase de lenguajes regulares , pero su cierre por homomorfismo letra por letra equivalente a la clase de lenguajes recursivamente enumerables [8] . También demostró que tomar una extensión, que en realidad se reduce a una intersección teórica de conjuntos de un idioma con un conjunto de terminales (un alfabeto), es en muchos casos equivalente en la práctica a considerar cadenas invariantes de reescritura, es decir, demostró la conexión de la estabilización de la morfogénesis con la teoría de los lenguajes formales [9] .

Paul Vitani, junto con su colega Ming Li, hizo una contribución significativa a la teoría de la complejidad de Kolmogorov , incluida la escritura del libro "Introducción a la complejidad de Kolmogorov y sus aplicaciones" [10] (publicado en 1993, 1997, 2008). El concepto mismo de la complejidad de Kolmogorov existía mucho antes que él (propuesto de forma independiente por Solomonoff y Kolmogorov en la década de 1960) y se reduce a la afirmación de que existe cierta complejidad descriptiva abstracta de cualquier cadena igual a la longitud del programa mínimo que puede producir esta cadena. (por sencillez, podemos considerarlo un lenguaje de programación de máquina de Turing , aunque esto no es necesario: basta con fijar algún tipo de descripción universal o lenguaje de codificación). Tal complejidad de una cadena, y de hecho de cualquier otro objeto, representa la cantidad mínima absoluta, a menudo inalcanzable, de información que una cadena u objeto puede ocupar sin trucos especiales, como renunciar a la universalidad. La complejidad de Kolmogorov es una abstracción teórica conveniente, a menudo inútil en la práctica porque es demostrablemente incomputable . Paul Vitani fue uno de los primeros en encontrarle aplicaciones prácticas en la teoría de autómatas o el análisis de algoritmos. El libro fue precedido por su trabajo separado sobre colorear gráficos con precisión limitada, comparación algorítmica de cinta, cola y pila , revisión de la jerarquía de Chomsky , la conexión de los peores escenarios con promedios, etc. El principio de la descripción más corta fue formulado por Vitani, Lee y sus alumnos como una abstracción basada en el teorema de Bayes y la complejidad de Kolmogorov, se obtuvieron una serie de conclusiones de carácter práctico, por ejemplo, que la compresión de datos es la mejor estrategia para aproximarse a la longitud más corta de una descripción de datos o transmitirse. mensaje [11] . En la práctica, esto le permite reemplazar el concepto abstracto, complejo y no computable de complejidad descriptiva con su aproximación en la forma de la longitud de un mensaje comprimido por algún archivador disponible .

En teoría computacional, Paul Vitani introdujo el concepto de localidad de los cálculos y demostró que evitar los cálculos secuenciales de von Neumann no resuelve el problema general, porque el cálculo en sí tiene lugar en un lugar determinado y sus resultados deben transferirse a otro lugar para almacenarlos. o continuar los cómputos.- y esta comunicación ocupa tiempo y espacio, lo que debería reflejarse en modelos realistas de cómputo inconsistente [12] . La complejidad de Kolmogorov también fue útil para estimar la carga en redes de diferentes topologías a partir de diferentes algoritmos utilizando el llamado método de incompresibilidad [13] . El método es similar al principio de Dirichlet, mucho más simple, y se basa principalmente en el hecho de que hay muchos más gráficos con alta complejidad de Kolmogorov que gráficos con baja complejidad, por lo que los gráficos aleatorios serán complejos de Kolmogorov con una probabilidad cercana a la unidad [14] . En general, la información de cualquier objeto para Vitani se divide en dos partes: esencial (que establece la regularidad del objeto) y no esencial (adiciones estocásticas). Él llama a la cantidad relativa de información esencial una medida de sofisticación, y los objetos para los cuales es máximo absolutamente no estocástico [15] .

Los estudios de teoría, complejidad y compresión de la información llevaron inevitablemente a Paul Vitani a métricas que miden la distancia informativa entre objetos (cadenas, documentos, idiomas, imágenes, etc.): él y sus alumnos propusieron un método de análisis de conglomerados basado en la compresión de datos [16] ; propuso una distancia de información normalizada [17] y una distancia de compresión normalizada [18] como medidas de cuán difícil es transformar un objeto en otro; implementó la llamada medida de similitud de Google como una métrica semántica basada en el número de visitas en Google para un término, otro y su combinación [19] ; amplió el concepto de distancia de información de pares de palabras a listas finitas (en realidad abandonando las relaciones en favor de las hipergrafías ) [20] ; desarrolló una serie de métodos para derivar automáticamente el significado de palabras desconocidas en función de su similitud informativa con palabras conocidas [21] [22] . Algunos de los métodos de análisis de conglomerados propuestos por él son tan buenos que funcionan muchas veces más rápido que sus análogos; por ejemplo, el agrupamiento jerárquico que usa el algoritmo de escalada y la programación genética paralela requiere solo una matriz de distancia y construye un dendrograma de 60-80 objetos en unas pocas horas, mientras que los enfoques alternativos se limitan a 20-30 objetos o requieren varios años para los cálculos [23] . Los mismos métodos de análisis de conglomerados aplicados a la música pueden determinar el género con alta confiabilidad y clasificar las obras de los compositores [24] .

En programación genética, Paul Vitani propuso un método basado en la mezcla rápida de cadenas de Markov que convergen con una probabilidad cercana a uno incluso en poblaciones pequeñas, mientras que los métodos alternativos sufren una evolución aleatoriamente divergente [25] . En cálculos reversibles  , demostró la posibilidad de simulación reversible de cálculos irreversibles en tiempo subexponencial y en costes de memoria subcuadráticos [26] . En teoría de juegos  , generalizó el problema de arruinar a un jugador a un mayor número de jugadores [27] . En geometría discreta  , resolvió el problema del triángulo de Heilbronn en el caso de una distribución aleatoria uniforme de puntos a lo largo de un círculo [28] [29] .

Paul Vitani está incluido en la lista de los científicos más productivos del catálogo DBLP como autor y coautor de casi 250 publicaciones científicas arbitradas [30] .

Aprendices

Bajo el liderazgo de Paula Vitani defendió [2] [31] :

• John Tromp, Aspectos de algoritmos y complejidad, 1993
• Jap-Henk Hupman, "Sincronización de comunicaciones y tolerancia a fallas", 1996
• Ronald Kramer, "Diseño modular de protocolos criptográficos seguros pero prácticos ", 1997
• Peter Grunwald, "Principio de descripción más corta y prueba bajo incertidumbre", 1998
• Barbara Terhal, "Algoritmos cuánticos y entrelazamiento cuántico ", 1999
• Ronald de Wolf, Computación cuántica y complejidad de la comunicación, 2001
• Wim van Dam, "Sobre la teoría cuántica de la computación", 2002
• Hein Roehrig, "Complejidad de consultas cuánticas y computación distribuida ", 2004
• Rudy Kilibrasi, "Inferencia estática por compresión de datos ", 2007
• Staven de Rooy, "Elección del modelo de descripción más breve: desafíos y complicaciones", 2008
• Wouter Kolen-Weikstra, “Combinación efectiva de estrategias. Soluciones de alta calidad basadas en consejos controvertidos”, 2011

Notas

1. ↑ Paul Vitányi: Lindenmayer Systems: Structure, Languages, and Growth Functions, 1978.
2. ↑ 1 2 3 4 Paul Michael Bela Vitanyi Archivado el 22 de enero de 2015 en Wayback Machine en Mathematics Genealogy Project .
3. ↑ Paul Vitányi ha sido nombrado CWI Fellow . Archivado el 1 de diciembre de 2014 en Wayback Machine , ERCIM News No. 53 de abril de 2003.
4. ↑ 1 2 Academia de Europa: Vitanyi Paul Archivado el 22 de enero de 2015 en Wayback Machine .
5. ↑ Paul Vitányi ontvangt koninklijke onderscheiding Archivado el 22 de enero de 2015 en Wayback Machine .
6. ↑ Algunas conferencias distinguidas, conferencias magistrales, conferencias invitadas, tutoriales Archivado el 1 de diciembre de 2014 en Wayback Machine .
7. ↑ L-Systems - The Mathematical Beauty of Plants Archivado el 22 de enero de 2015 en Wayback Machine .
8. ↑ Paul M. B. Vitányi: Lenguajes deterministas de Lindenmayer, no terminales y homomorfismos . Informática Teórica 2(1): 49-71 (1976).
9. ↑ Paul M. B. Vitányi, Adrian Walker: Lenguajes de cuerdas estables de Lindenmayer Systems . Información y Control 37(2): 134-149 (1978).
10. ↑ Una introducción a la complejidad de Kolmogorov y sus aplicaciones (Textos en informática) Archivado el 29 de agosto de 2018 en Wayback Machine en Amazon .
11. ↑ Paul MB Vitányi, Ming Li: Inducción de longitud de descripción mínima, bayesianismo y complejidad de Kolmogorov . Transacciones IEEE sobre teoría de la información 46 (2): 446-464 (2000)
12. ↑ Paul M. B. Vitányi: Localidad, comunicación y longitud de interconexión en multicomputadoras . Computación SIAM J. 17(4): 659-672 (1988)
13. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: El método de incompresibilidad . SOFSEM 2000: 36-53
14. ↑ Harry Buhrman, Ming Li, John Tromp, Paul M. B. Vitányi: Gráficos aleatorios de Kolmogorov y el método de incompresibilidad . Computación SIAM J. 29(2): 590-599 (1999).
15. ↑ Paul M. B. Vitányi: Información significativa . Transacciones IEEE sobre teoría de la información 52 (10): 4617-4626 (2006)
16. ↑ Rudi Cilibrasi, Paul MB Vitányi: Agrupación por compresión . Archivado el 13 de octubre de 2008 en Wayback Machine . Transacciones IEEE sobre teoría de la información 51 (4): 1523–1545 (2005)
17. ↑ Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, Wojciech H. Zurek: Información a distancia . Transacciones IEEE sobre teoría de la información 44 (4): 1407-1423 (1998)
18. ↑ Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi: No aproximabilidad de la distancia de información normalizada . Revista de Ciencias de la Computación y Sistemas 77(4): 738-742 (2011)
19. ↑ Rudi Cilibrasi, Paul MB Vitányi: La distancia de similitud de Google . Trans. IEEE. Saber Ing. de datos 19(3): 370-383 (2007)
20. ↑ Paul M. B. Vitányi: Distancia de información en múltiplos . Transacciones IEEE sobre teoría de la información 57 (4): 2451–2456 (2011)
21. ↑ Rudi Cilibrasi, Paul MB Vitányi: Similitud de los objetos y el significado de las palabras Archivado el 11 de octubre de 2008 en Wayback Machine . TAMC 2006: 21-45
22. ↑ Rudi Cilibrasi, Paul MB Vitányi: Descubrimiento automático de significado con Google Archivado el 22 de enero de 2015 en Wayback Machine . Kolmogorov Complejidad y Aplicaciones 2006
23. ↑ Rudi Cilibrasi, Paul MB Vitányi: A New Quartet Tree Heuristic for Hierarchical Clustering Archivado el 22 de enero de 2015 en Wayback Machine . Teoría de los Algoritmos Evolutivos 2006
24. ↑ Rudi Cilibrasi, Paul M. B. Vitányi, Ronald de Wolf: Agrupación algorítmica de la música . WEDELMUSIC 2004: 110-117
25. ↑ Paul M. B. Vitányi: Una disciplina de programación evolutiva . Informática Teórica 241(1-2): 3-23 (2000)
26. ↑ Harry Buhrman, John Tromp, Paul M. B. Vitányi: Límites de tiempo y espacio para la simulación reversible . ICALP 2001: 1017-1027
27. ↑ Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe: Sobre un problema generalizado de ruina . ALEATORIO-APROX. 2001: 181-191
28. ↑ Tao Jiang, Ming Li, Paul M. B. Vitányi: El tamaño esperado de los triángulos de Heilbronn . Conferencia IEEE sobre Complejidad Computacional 1999: 105-113
29. ↑ Tao Jiang, Ming Li, Paul MB Vitányi: El área del caso promedio de los triángulos tipo Heilbronn . Estructuras aleatorias y algoritmos 20 (2): 206-219 (2002)
30. ↑ Autores DBLP más prolíficos Archivado el 13 de febrero de 2009. .
31. ↑ Doctorado anterior Estudiantes Archivado el 1 de diciembre de 2014 en Wayback Machine .

sitios temáticos	Google Académico genealogía matemática ORCIDO zbMATH Abierto Portal matemático de toda Rusia
En catálogos bibliográficos BIBSYS: 90290589 BNF : 124933863 ISNI : 0000 0001 1578 4969 J9U : 987007447082805171 LCCN : n81091576 NTA : 06767884X NUKAT : n95207712 SUDOC : 034146601 VIAF : 94523542 WorldCat VIAF : 94523542