Уве Шёнинг - Uwe Schöning

Уве Шёнинг (родился 28 декабря 1955 г.) - немец специалист в области информатики, известный своими исследованиями в теория сложности вычислений.

Образование и карьера

Шёнинг получил докторскую степень. от Штутгартский университет в 1981 году под руководством Вольфрама Швабхойзера.[1]Он профессор Института теоретической информатики Ульмский университет.[2]

Взносы

Шёнинг представил низкие и высокие иерархии в теорию структурной сложности в 1983 году. Как позже показал Шёнинг в статье 1988 года, эти иерархии играют важную роль в сложности проблема изоморфизма графов, который Шёнинг развил в монографии 1993 года с Кёблером и Тораном.

В документе FOCS 1999 г. Шёнинг показал, что WalkSAT, а рандомизированный алгоритм ранее анализировался для 2-выполнимость Пападимитриу, хорошо ожидаемая временная сложность (хотя все еще экспоненциально) применительно к наихудшим случаям 3-выполнимость и другие НП-полный удовлетворение ограничений проблемы. В то время это был самый короткий гарантированный срок для 3SAT; последующие исследования основывались на этой идее для разработки еще более быстрых алгоритмов.

Шенинг также является изобретателем педагогического языки программирования ПЕТЛЯ, GOTO и WHILE, которые он описал в своем учебнике Теоретическая информатика - kurz gefasst.

Избранные публикации

Шёнинг - автор или редактор многих книг по информатике, в том числе

  • Сложность и структура (Springer, Lecture Notes in Computer Science 211, 1985).[3]
  • Logik für Informatiker (на немецком языке, Reihe Informatik, 1987; 5-е изд., Springer, 2000). Переведено на английский как Логика для компьютерных ученых (Биркхойзер, 1989).[4][5]
  • Теоретическая информатика - kurz gefasst (на немецком языке, BI-Wiss.-Verlag, 1992; 5-е изд., Spektrum, 2008).
  • Проблема изоморфизма графов: ее структурная сложность (совместно с Дж. Кёблером и Дж. Тораном, Биркхойзер, 1993).[6]
  • Perlen der Theoretischen Informatik (на немецком языке, Bibl. Institut Wissenschaftsverlag, 1995). Переработано и переведено на английский язык как Жемчужины теоретической информатики (совместно с Р. Дж. Пруимом, Springer, 1998 г.).[7][8][9]
  • Алгоритмы - kurz gefasst (на немецком языке, Spektrum, 1997).
  • Алгоритмик (на немецком языке, Спектрум, 2001).
  • Ideen der Informatik (на немецком языке, Oldenbourg, 2002, 2-е изд. 2005).
  • Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden (Lehmanns, 2010).
  • Криптология-Компендиум (Lehmanns, 2012).
  • Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen (совместно с Дж. Тораном, на немецком языке, Lehmanns, 2012 г.). Переведено на английский как Проблема выполнимости - алгоритмы и анализ (Lehmanns, 2013).

Его исследовательские статьи включают:

  • Шёнинг, Уве (1983), «Низкая и высокая иерархия в НП», Журнал компьютерных и системных наук, 27 (1): 14–28, Дои:10.1016/0022-0000(83)90027-2, МИСТЕР  0730913.
  • Шёнинг, Уве (1988), «Изоморфизм графов находится в низкой иерархии», Журнал компьютерных и системных наук, 37 (3): 312–323, Дои:10.1016/0022-0000(88)90010-4, МИСТЕР  0975447.
  • Шонинг, У. (1999), "Вероятностный алгоритм для k-SAT и задач удовлетворения ограничений", Материалы 40-го ежегодного симпозиума по основам компьютерных наук, стр. 410–414, Дои:10.1109 / SFFCS.1999.814612.

Рекомендации

  1. ^ Уве Шёнинг на Проект "Математическая генеалогия"
  2. ^ Профиль факультета, Univ. of Ulm, получено 7 сентября 2013 г.
  3. ^ Обзор Сложность и структура к Юрис Хартманис (1987), МИСТЕР0827009
  4. ^ Обзор Logik für Informatiker Некулаи Куртяну (1989), МИСТЕР0944086; также указан как МИСТЕР1244106 (3-е изд.) И МИСТЕР2683474 (Англ. Ред.)
  5. ^ Обзор Логика для компьютерных ученых Риккардо Пучелла (2005), Новости SIGACT 36 (3): 17–19, Дои:10.1145/1086649.1086657
  6. ^ Обзор Проблема изоморфизма графов к Павол Ад (1995), МИСТЕР1232421
  7. ^ Обзор Жемчужины теоретической информатики к Рохит Дживанлал Парих (2000), Журнал логики, языка и информации 9 (1): 131–132, Дои:10.1023 / А: 1008379701961
  8. ^ Обзор Жемчужины теоретической информатики Дэнни Крижанка (2000), Новости SIGACT 31 (2): 2–5, Дои:10.1145/348210.1042072
  9. ^ Обзор Жемчужины теоретической информатики Мариус Зиманд (2000), МИСТЕР1667079

внешняя ссылка