Uwe Schöning (nacido el 28 de diciembre de 1955) es un informático alemán , conocido por sus investigaciones en la teoría de la complejidad computacional .
Educación y carrera
Schöning obtuvo su Ph.D. de la Universidad de Stuttgart en 1981, bajo la supervisión de Wolfram Schwabhäuser. [1] Es profesor en el Instituto de Informática Teórica de la Universidad de Ulm . [2]
Contribuciones
Schöning introdujo las jerarquías bajas y altas a la teoría de la complejidad estructural en 1983. Como Schöning mostró más tarde en un artículo de 1988, estas jerarquías juegan un papel importante en la complejidad del problema del isomorfismo gráfico , que Schöning desarrolló en una monografía de 1993 con Köbler y Toran. .
En un artículo de 1999 de FOCS , Schöning mostró que WalkSAT , un algoritmo aleatorio previamente analizado por Papadimitriou para determinar la satisfacibilidad 2 , tenía una buena complejidad de tiempo esperado (aunque aún exponencial) cuando se aplicaba a los peores casos de satisfacibilidad 3 y otras restricciones NP-completas problemas de satisfacción . En ese momento, este era el tiempo garantizado más rápido para 3SAT; La investigación posterior se ha basado en esta idea para desarrollar algoritmos aún más rápidos.
Schöning también es el inventor de los lenguajes de programación pedagógica LOOP , GOTO y WHILE, que describió en su libro de texto Theoretische Informatik - kurz gefasst .
Publicaciones Seleccionadas
Schöning es autor o editor de muchos libros de informática, incluidos
- Complejidad y estructura (Springer, Lecture Notes in Computer Science 211, 1985). [3]
- Logik für Informatiker (en alemán, Reihe Informatik, 1987; 5a ed., Springer, 2000). Traducido al inglés como Logic for Computer Scientists (Birkhäuser, 1989). [4] [5]
- Theoretische Informatik - kurz gefasst (en alemán, BI-Wiss.-Verlag, 1992; 5a ed., Spektrum, 2008)
- El problema del isomorfismo gráfico: su complejidad estructural (con J. Köbler y J. Toran, Birkhäuser, 1993). [6]
- Perlen der Theoretischen Informatik (en alemán, Bibl. Institut Wissenschaftsverlag, 1995). Revisado y traducido al inglés como gemas de la informática teórica (con RJ Pruim, Springer, 1998). [7] [8] [9]
- Algoritmos - kurz gefasst (en alemán, Spektrum, 1997).
- Algorithmik (en alemán, Spektrum, 2001).
- Ideen der Informatik (en alemán, Oldenbourg, 2002, 2ª ed. 2005).
- Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden (Lehmanns, 2010).
- Kryptologie-Kompendium (Lehmanns, 2012).
- Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen (con J. Toran, en alemán, Lehmanns, 2012). Traducido al inglés como The Satisfiability Problem - Algorithms and Analyzes (Lehmanns, 2013).
Sus artículos de investigación incluyen:
- Schöning, Uwe (1983), "Una jerarquía baja y alta dentro de NP", Journal of Computer and System Sciences , 27 (1): 14-28, doi : 10.1016 / 0022-0000 (83) 90027-2 , MR 0730913.
- Schöning, Uwe (1988), "El isomorfismo de grafos está en la jerarquía baja", Journal of Computer and System Sciences , 37 (3): 312–323, doi : 10.1016 / 0022-0000 (88) 90010-4 , MR 0975447.
- Schoning, U. (1999), "Un algoritmo probabilístico para k-SAT y problemas de satisfacción de restricciones", Actas del 40º Simposio anual sobre fundamentos de la informática , págs. 410–414, doi : 10.1109 / SFFCS.1999.814612 , S2CID 123177576.
Referencias
- ^ Uwe Schöning en el Proyecto de genealogía matemática
- ^ Perfil de la facultad , Univ. of Ulm, consultado el 7 de septiembre de 2013.
- ^ Revisión de complejidad y estructura por Juris Hartmanis (1987), MR0827009
- ^ Revisión de Logik für Informatiker por Neculai Curteanu (1989), MR0944086 ; también listado como MR1244106 (3.a ed.) Y MR2683474 (ed. En inglés)
- ^ Revisión de lógica para científicos informáticos por Riccardo Pucella (2005), SIGACT News 36 (3): 17-19, doi : 10.1145 / 1086649.1086657
- ^ Revisión del problema del isomorfismo gráfico por Pavol Hell (1995), MR1232421
- ^ Revisión de las gemas de la informática teórica por Rohit Jivanlal Parikh (2000), Journal of Logic, Language and Information 9 (1): 131-132, doi : 10.1023 / A: 1008379701961
- ^ Revisión de las gemas de la informática teórica por Danny Krizanc (2000), SIGACT News 31 (2): 2-5, doi : 10.1145 / 348210.1042072
- ^ Revisión de las gemas de la informática teórica por Marius Zimand (2000), MR1667079
enlaces externos
- Perfil académico de Google