Уве Шёнинг
Уве Шёнинг (родился 28 декабря 1955 года) — немецкий учёный-компьютерщик на пенсии , известный своими исследованиями в области теории сложности вычислений .
Образование и карьера
[ редактировать ]Шенинг получил докторскую степень. из Штутгартского университета в 1981 году под руководством Вольфрама Швабхойзера. [ 1 ] Он был профессором Института теоретической информатики Ульмского университета до выхода на пенсию в 2021 году. [ 2 ]
Взносы
[ редактировать ]Шёнинг ввел низкие и высокие иерархии в теорию структурной сложности в 1983 году. Как позже показал Шёнинг в статье 1988 года, эти иерархии играют важную роль в сложности проблемы изоморфизма графов , которую Шёнинг далее развил в монографии 1993 года с Кёблером и Тораном. .
В статье FOCS 1999 года Шёнинг показал, что WalkSAT , рандомизированный алгоритм , ранее проанализированный Пападимитриу на предмет -выполнимости 2 , имел хорошую ожидаемую временную сложность (хотя все еще экспоненциальную) при применении к наихудшим случаям 3-выполнимости и другим NP-полным ограничениям. удовлетворения проблемы . На тот момент это было самое быстрое гарантированное время для 3SAT; последующие исследования основывались на этой идее для разработки еще более быстрых алгоритмов.
Шенинг также является изобретателем педагогических языков программирования LOOP , GOTO и WHILE, которые он описал в своем учебнике Theoretische Informatik — kurz gefasst .
Избранные публикации
[ редактировать ]Шенинг является автором или редактором многих книг по информатике, в том числе
- Сложность и структура (Спрингер, Конспект лекций по информатике, 211, 1985). [ 3 ]
- Логика для компьютерщиков (на немецком языке, серия Informatik, 1987; 5-е изд., Springer, 2000). Переведено на английский язык как «Логика для компьютерщиков» (Birkhäuser, 1989). [ 4 ] [ 5 ]
- Теоретическая информатика - в двух словах (на немецком языке, BI-Wiss.-Verlag, 1992; 5-е изд., Spektrum, 2008)
- Проблема изоморфизма графов: ее структурная сложность (совместно с Дж. Кёблером и Дж. Тораном, Биркхойзер, 1993). [ 6 ]
- Жемчужины теоретической информатики (на немецком языке, Bibl. Institut Wissenschaftsverlag, 1995). Пересмотрено и переведено на английский язык как «Жемчужины теоретической информатики» (совместно с Р. Дж. Прюимом, Springer, 1998). [ 7 ] [ 8 ] [ 9 ]
- Алгоритмы - кратко (на немецком языке, Спектрум, 1997).
- Алгоритмический (на немецком языке, «Спектр», 2001).
- Идеи в информатике (на немецком языке, Ольденбург, 2002 г., 2-е изд. 2005 г.).
- Math Toolbox — Математические обозначения, основные понятия и методы доказательства (Lehmanns, 2010).
- Справочник по криптологии (Lehmanns, 2012).
- Проблема выполнимости SAT - алгоритмы и анализ (совместно с Дж. Тораном, на немецком языке, Lehmanns, 2012). Переведено на английский как «Проблема выполнимости - алгоритмы и анализ» (Lehmanns, 2013).
Его исследовательские статьи включают:
- Шёнинг, Уве (1983), «Низкая и высокая иерархия внутри NP», Журнал компьютерных и системных наук , 27 (1): 14–28, doi : 10.1016/0022-0000(83)90027-2 , MR 0730913 .
- Шёнинг, Уве (1988), «Изоморфизм графов находится в низкой иерархии», Journal of Computer and System Sciences , 37 (3): 312–323, doi : 10.1016/0022-0000(88)90010-4 , MR 0975447 .
- Шонинг, У. (1999), «Вероятностный алгоритм для k-SAT и проблем удовлетворения ограничений», Труды 40-го ежегодного симпозиума по основам информатики , стр. 410–414, doi : 10.1109/SFCS.1999.814612 , S2CID 123177576 .
Ссылки
[ редактировать ]- ^ Уве Шёнинг в проекте «Математическая генеалогия»
- ^ Профиль факультета , Univ. из Ульма, получено 28 марта 2022 г.
- ^ Обзор сложности и структуры ( Юриса Хартманиса 1987), MR 0827009
- ^ Обзор Logik für Informatiker Некулая Куртяну (1989), MR 0944086 ; также указан как MR 1244106 (3-е изд.) и МР 2683474 (английское изд.)
- ^ Обзор логики для компьютерщиков Риккардо Пучелла (2005), SIGACT News 36 (3): 17–19, дои : 10.1145/1086649.1086657
- ^ Обзор проблемы изоморфизма графов Павола Хелла (1995), MR 1232421
- ^ Обзор жемчужин теоретической информатики Рохита Дживанлала Париха (2000), Журнал логики, языка и информации 9 (1): 131–132, два : 10.1023/A:1008379701961
- ^ Обзор жемчужин теоретической информатики Дэнни Кризанца (2000), SIGACT News 31 (2): 2–5, дои : 10.1145/348210.1042072
- ^ Обзор жемчужин теоретической информатики Мариуса Зиманда (2000), MR 1667079
Внешние ссылки
[ редактировать ]| Международный | |
|---|---|
| Национальный | |
| академики | |
| Другой | |
