Hispanopedia Wiki
Articulo de referencia

Anatol Slissenko

[[Mathematics]]"},"alma_mater":{"wt":"[[Saint Petersburg State University]]"},"work_institution":{"wt":"[[Steklov Mathematical Institute]] [[Saint Petersburg State University]] ...

Hispanopedia WikiContenido en espanolLectura gratuita

Anatol Slissenko (antigua transliteración: Slisenko ; en ruso: Анатоль Олесьевич Слисенко ), matemático e informático soviético, ruso y francés, nació el 15 de agosto de 1941 en Siberia, donde su padre [ 1 ] se desempeñó como comandante de un regimiento de topografía militar. En 1950, sus padres se mudaron a Leningrado.

Investigación

Fuente: [ 2 ]

En 1958, AO Slissenko ingresó en la Facultad de Matemáticas y Mecánica de la Universidad Estatal de Leningrado (actualmente San Petersburgo). [ 3 ] Allí comenzó su investigación [ 4 ] en matemáticas constructivas (análisis recursivo) [ 5 ] bajo la supervisión de Nikolai Shanin . Tras graduarse en 1963, se convirtió en investigador del Departamento de Leningrado del Instituto Matemático Steklov de la Academia de Ciencias de la URSS (actualmente con un nombre ligeramente diferente). [ 6 ] Defendió su tesis doctoral en matemáticas constructivas en 1967, bajo la dirección de Nikolai Shanin. En 1981 defendió su tesis doctoral en el Instituto Matemático Steklov de Moscú.

Entre 1963 y 1966 continuó su investigación en matemáticas constructivas y, al mismo tiempo, participó en el desarrollo e implementación del algoritmo de Shanin para la demostración automática de teoremas en lógica proposicional clásica. [ 7 ]

Posteriormente, comenzó gradualmente a investigar sobre algoritmos y complejidad computacional.

En el artículo [ 8 ] analiza cómo definir la complejidad "computacional" de un problema individual, un tema que influyó en sus artículos posteriores sobre convergencia entrópica.

En [ 9 ] dio una solución inesperada al problema del reconocimiento de palíndromos por máquinas de Turing de múltiples cabezas, a saber, demostró que una máquina de Turing de 6 cabezas con una cinta puede reconocer palíndromos en tiempo real; la expectativa generalizada era que era imposible. Su muy larga demostración fue posteriormente simplificada por Zvi Galil , quien utilizó algunos resultados nuevos que no se conocían cuando se escribió [ 9 ] (véase también [ 10 ]) .

Otro resultado importante de Slissenko fue un algoritmo en tiempo real que resolvió una gran variedad de problemas de coincidencia de cadenas (incluyendo la búsqueda de todas las periodicidades en una forma compacta). [ 11 ] El algoritmo puede formalizarse como LRAM (máquina de direcciones), una máquina de acceso aleatorio con registros cuya longitud está limitada por el logaritmo de la complejidad temporal, introducida en [ 12 ] y también descrita en. [ 13 ] [ 11 ] Este modelo permite el uso de varias operaciones, incluyendo la multiplicación, que sin esta limitación en la longitud pueden dar algoritmos irrealmente rápidos. Además de que LRAM tiene una jerarquía de complejidad temporal muy densa.

Durante 1981-1992, Slissenko fue jefe de un laboratorio en el Instituto de Informática y Automatización de San Petersburgo de la Academia Rusa de Ciencias . [ 14 ] Allí trabajó en aplicaciones, sin embargo, era una época de agonía para la Unión Soviética y no hubo publicaciones notables en este campo.

En [ 15 ] introdujo una clase de gramáticas de grafos (llamadas gramáticas de Slisenko (Slissenko) en [ 16 ] ) que generan grafos para los cuales la existencia de ciclos hamiltonianos puede decidirse en tiempo polinomial. Los grafos generados por estas gramáticas tienen un ancho de árbol acotado.

El artículo [ 17 ] fue el primero en el que introdujo una entropía para evaluar la calidad de los sistemas de inferencia.

Desde 1993 hasta 2009 fue profesor en la Universidad Paris-East Créteil [ 18 ] (UPEC: Université Paris-Est-Créteil; el nombre anterior era Universidad Paris-12), Facultad de Ciencias y Tecnología, Departamento de Informática. Trabajó en la complejidad de los procesos de decisión de Markov, [ 19 ] en algoritmos para construir caminos más cortos en medio de obstáculos semialgebraicos y de otro tipo, y en la verificación de sistemas temporizados.

El artículo [ 20 ] describe un algoritmo de tiempo polinomial para construir un camino más corto que toca líneas rectas oblicuas en un espacio tridimensional que resuelve un problema abierto conocido.

En [ 21 ] se desarrolló un algoritmo de verificación de modelos para una lógica bastante potente con un operador de probabilidad; fue un primer resultado para este tipo de lógicas.

Se investigaron varios temas de verificación para modelos temporizados. En [ 22 ] se introdujo una lógica potente para la especificación de sistemas de tiempo real estricto, denominada FOTL (First Order Timed Logic), y se presentaron clases decidibles. En [ 23 ] se investigaron clases decidibles más generales.

La convergencia entrópica de algoritmos se introdujo en [ 24 ] y se aplicó a la evaluación de bases de conocimiento. [ 25 ]

En [ 26 ] notó que se puede reformular ligeramente el problema P≠NP de tal manera que siga siendo prácticamente interesante, pero su independencia de la aritmética implica que P≠NP.

Slissenko fue ponente invitado en numerosas conferencias, en particular en el Congreso Internacional de Matemáticos de 1983, celebrado en Varsovia, Polonia. [ 27 ]

Colaboró ​​con Nikolai Shanin , S. Maslov, G. Mints y V. Orevkov [ 28 ] en la demostración automática de teoremas, con D. Beauquier, Dima Grigoriev , D. Burago , A. Rabinovich [ 29 ] y otros en diversos temas relacionados con la algoritmia. [ 30 ] [ 31 ]

Actividad docente y organizativa

AOSlissenko fue profesor a tiempo parcial en el Instituto Politécnico de Leningrado [ 32 ] entre 1981 y 1987, y entre 1988 y 1992 fue profesor a tiempo parcial en la Facultad de Matemáticas y Mecánica de la Universidad Estatal de Leningrado [ 3 ], donde dirigió el Departamento de Informática, cuya creación impulsó (los equipos de estudiantes del departamento fueron campeones mundiales del Concurso Internacional Universitario de Programación de la ACM en cuatro ocasiones). Entre 1993 y 2009 fue catedrático en la Universidad París-Este de Créteil [ 18 ] , en la Facultad de Ciencias y Tecnología, Departamento de Informática. Desde 2009 es profesor emérito en dicha universidad.

También fue director (y, en cierto modo, fundador) del Laboratorio de Complejidad y Lógica Algorítmica (LACL) desde 1997 hasta 2007. En todos estos cargos contribuyó a modernizar el plan de estudios y la investigación.

En 1967, Slissenko organizó junto con Grigori Tseitin (1936–2022) y Robert I. Friedson (1942–2018) el Seminario de Leningrado sobre Complejidad Computacional [ 26 ] , que inicialmente tuvo sus reuniones en la Universidad Estatal de Leningrado y luego en el Departamento de Leningrado del Instituto Matemático Steklov (en ese momento Slissenko se convirtió en su director formal). El seminario desempeñó un papel importante en el desarrollo de este campo en la Unión Soviética. El seminario funcionó hasta 1992, fecha en la que, tras el colapso de la Unión Soviética (y de su sistema de investigación), la mayor parte de sus participantes abandonaron el país y encontraron trabajo en Estados Unidos, Francia y el Reino Unido.

Se puede encontrar información histórica sobre la informática soviética en [ 26 ] [ 33 ] y algunas observaciones están en [ 34 ] .

Referencias

  1. ↑ Oles' Vasilyevitch Slissenko. En : EIDolgov, SVSergeyev. Topógrafos militares del Ejército Rojo. Servicio Topográfico de las Fuerzas Armadas de la Federación Rusa. Moscú, 2005, páginas 487-489 (en ruso). http://militera.org/books/pdf/enc/dolgov_sergeev01.pdf
  2. ^ Beauquier, D.; Grigoriev, D.; Matiyasevich, Yu. (2003). "Biografía de AO Slissenko". Informática Teórica . 303 : 3-5 .
  3. 1 2 "Facultad de Matemáticas y Mecánica de la Universidad Estatal de San Petersburgo" . math.spbu.ru .
  4. ↑ A. Slisenko (Slissenko). Sobre algunos problemas algorítmicos, relativos a las operaciones aritméticas en dúplex. Soviet Mathematical Doklady, 152(2), 1963. Original ruso en: Doklady Akademii Nauk SSSR, 152(2):292–295, 1963.
  5. ↑ Bridges, Douglas; Palmgren, Erik; Ishihara, Hajime (12 de marzo de 2022). Zalta, Edward N.; Nodelman, Uri (eds.). La Enciclopedia de Filosofía de Stanford . Laboratorio de Investigación en Metafísica, Universidad de Stanford – vía Enciclopedia de Filosofía de Stanford.
  6. ↑ " Historia del Instituto | Departamento de San Petersburgo del Instituto Matemático Steklov de la Academia Rusa de Ciencias" . www.pdmi.ras.ru.
  7. ↑ N. Shanin, G. Davydov, S. Maslov, G. Mints, V. Orevkov y A. Slissenko (Slissenko). Un algoritmo para la búsqueda automática de una deducción lógica natural en un cálculo proposicional. En J. Siekmann y G. Wrightson, editores, *The Automation of Reasoning I: Classical Papers on Computational Logic 1957–1966*, páginas 424–483. Springer-Verlag, 1983 (el original ruso fue publicado por Nauka, Leningrado, 1965, 39 págs.).
  8. ↑ A. Slisenko. Enfoque finito del problema de optimizar algoritmos de demostración de teoremas. J. of Soviet Mathematics, 10(4):597–603, 1978. Original ruso en: Zapiski Nauchnykh Seminarov LOMI, 49:123-130, 1975.
  9. 1 2 A. Slisenko . Reconocimiento de un predicado de simetría por máquinas de Turing multicabezales con entrada. Proc. Steklov Inst. of Mathematics, 129:25–208, 1976. Original ruso en:Trudy Matematicheskogo Instituta Akademii Nauk SSSR, 129:30–202, 1973.
  10. ↑ A. Slisenko. Una prueba simplificada de la reconocibilidad en tiempo real de palíndromos en máquinas de Turing. J. of Soviet Mathematics, 15(1):68–77, 1981. Original ruso en: Zapiski Nauchnykh Seminarov LOMI, 68:123–139, 1977.
  11. 1 2 A. Slissenko. Detección de periodicidades y coincidencia de cadenas en tiempo real. J. of Soviet Mathematics, 22(3):1316–1386, 1983. Original ruso en: Zapiski Nauchnykh SeminarovnLOMI, 105:62–173, 1981.
  12. ↑ A. Slissenko. Modelos de computación basados ​​en la organización de direcciones de almacenamiento. En Actas del Simposio Soviético sobre IA y Automatización de la Investigación Matemática, Kiev, páginas 94-96. Instituto de Cibernética, Kiev, 1978 (en ruso).
  13. ↑ A. Slissenko. Problemas de complejidad de la teoría de la computación. Russian Mathematical Surveys, 36(6):23–125, 1981. Original en ruso en: Uspekhi Matem. Nauk, 36(2):21–103, 1981.
  14. ↑ «Principal - SPIIRAS» . www.spiiras.nw.ru .
  15. ↑ Slisenko, A. (1982). "Gramáticas libres de contexto como herramienta para describir subclases de tiempo polinomial de problemas difíciles". Information Processing Letters . 14 (2): 52– 56. doi : 10.1016/0020-0190(82)90086-2 .
  16. ↑ A. Habel, Reemplazo de hiperaristas: gramáticas y lenguajes, en: Lecture Notes in Computer Science, Vol. 643, Springer, Berlín, 1992
  17. ↑ Slissenko, A. (1991). "Sobre medidas de calidad de la información de los sistemas de procesamiento del conocimiento". Information Sciences . 57–58 : 389–402 . doi : 10.1016/0020-0255(91)90089-D .
  18. 1 2 "UPEC" . UPEC .
  19. ↑ Burago, D.; de Rougemont, M.; Slissenko, A. (1996). "Sobre la complejidad de los procesos de decisión de Markov parcialmente observados" . Theoret. Comput. Sci . 157 (1): 161– 183. doi : 10.1016/0304-3975(95)00158-1 .
  20. ↑ Burago, D.; Grigoriev, D.; Slissenko, A. (2004). "Aproximación del camino más corto para el problema de las líneas oblicuas en tiempo doblemente logarítmico en 1/epsilon". Theoretical Computer Science . 315 ( 2– 3): 371– 404.
  21. ↑ Beauquier, D.; Rabinovich, A.; Slissenko, A. (2006). "Una lógica de probabilidad con verificación de modelos decidible". Journal of Logic and Computation . 16 (4): 461– 487.
  22. ↑ Beauquier, D.; Slissenko, A. (2002). "Una lógica de primer orden para la especificación de algoritmos temporizados: propiedades básicas y una clase decidible". Annals of Pure and Applied Logic . 113 ( 1– 3): 13– 52.
  23. ↑ Beauquier, D.; Slissenko, A. (2006). "Clases decidibles basadas en periodicidad en una lógica temporizada de primer orden". Annals of Pure and Applied Logic . 139 ( 1– 3): 43– 73.
  24. ↑ A. Slissenko. Sobre la convergencia entrópica de algoritmos. En A. Blass, P. Cgielski, N. Dershowitz, M. Droste y B. Finkbeiner (eds.), Campos de la lógica y la computación III. Lecture Notes in Computer Science, vol. 12180, páginas 291-304. Springer, Cham, 2020.
  25. ↑ A. Slissenko. Relacionando información y conocimiento. En K. Meer, A. Rabinovich, E. Ravve y A. Villaveces (eds.), Teoría de modelos, informática y polinomios de grafos, Trends in Mathematics, páginas 515–523. Birkhäuser Cham, 2025. ISBN 978-3-031-86318-9 (tapa dura), ISBN 978-3-031-86319-6 (libro electrónico).
  26. 1 2 3 A. Slissenko. San Petersburgo/Leningrado (1961-1998): De la lógica a la complejidad y más allá, en: "Personas e ideas en la informática teórica", Springer Verlag, páginas 274-313, 1998. ISBN 981-4021-13-X
  27. ↑ A. Slissenko. Consideraciones lingüísticas en el diseño de algoritmos eficaces. En Actas del Congreso Internacional de Matemáticos, 16-24 de agosto de 1983, Waszawa, páginas 347-357. ICM, Waszawa, 1984.
  28. ↑ " Vladimir Orevkov | Departamento de San Petersburgo del Instituto Matemático Steklov de la Academia Rusa de Ciencias" . www.pdmi.ras.ru.
  29. ↑ «Prof. Alejandro Rabinovich» . Universidad de Tel Aviv .
  30. ↑ "anatol_pub.html" . www.lacl.fr .
  31. ↑ "Personaliza: Слисенко Анатоль Олесьевич" . www.mathnet.ru .
  32. ↑ "Universidad Politécnica Pedro el Grande de San Petersburgo" . 13 de febrero de 2025 – vía Wikipedia.
  33. ↑ A. Slissenko. Una visión de los últimos años de investigación en informática teórica en la antigua Unión Soviética. RAIRO, Technique et science informatique, 12(1):9–28, 1993.
  34. ↑ A. Slissenko. Hacia el análisis de la estructura de la información de los cálculos. The IFCoLog Journal of Logic and its Applications, 4(4):1457–1476, 2017. Publicado también en el volumen 70 de la serie Studies in Logic, páginas 277-299, College Publications.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Anatol_Slissenko&oldid=1337612599 "