Уве Шёнинг

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

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

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

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

Шёнинг также является изобретателем педагогических языков программирования LOOP , GOTO и WHILE, которые он описал в своем учебнике «Теоретическая информатика - короткий путь» .

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

• Сложность и структура (Springer, Lecture Notes in Computer Science 211, 1985). ^[3]
• Logik für Informatiker (на немецком языке, Reihe Informatik, 1987; 5-е изд., Springer, 2000). Переведено на английский язык как «Логика для компьютерщиков» (Birkhäuser, 1989). ^{[4] [5]}
• Theoretische Informatik - 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 (на немецком языке, Спектрум, 1997).
• Алгоритмик (на немецком языке, Спектрум, 2001).
• Ideen der Informatik (на немецком языке, Ольденбург, 2002 г., 2-е изд. 2005 г.).
• Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden (совместно с Х. А. Кестлером, Lehmanns, 2010).
• Kryptologie-Kompendium (Lehmanns, 2012).
• Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen (совместно с Дж. Тораном, на немецком языке, Lehmanns, 2012). Переведено на английский как «Проблема выполнимости - алгоритмы и анализ» (Lehmanns, 2013).

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

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

• Профиль ученого Google