Стефан Зейдер - Википедия - Stefan Szeider

Стефан Зейдер
НациональностьАвстрийский
Альма-матерВенский университет
Научная карьера
ПоляАлгоритмы
Сложность
Теоретическая информатика
Логическая выполнимость
Удовлетворение ограничений
Параметризованная сложность
УчрежденияTU Wien
Университет Дарема
Университет Торонто
Австрийская Академия Наук
ДокторантыГерберт Флейшнер
Георг Готтлоб

Стефан Зейдер австрийский ученый-компьютерщик, работающий в области алгоритмы, вычислительная сложность, теоретическая информатика, и более конкретно на пропозициональная выполнимость, проблемы удовлетворения ограничений, и параметризованная сложность. Он является профессором факультета информатики.[1] на Венский технологический университет (TU Wien), руководитель группы алгоритмов и сложности и сопредседатель Венский центр логики и алгоритмов TU Wien (VCLA).[2][3]

Образование

Зайдер получил докторскую степень по математике в Венском университете в 2001 году под руководством профессоров Герберта Флейшнера и Георг Готтлоб работая математиком в Австрийская Академия Наук.[4][5]

Карьера и исследования

Зейдер - полный профессор на факультете информатики TU Wien.[1] Ранее он был сначала лектором, а затем читателем в Университет Дарема, Великобритания (2004-2009) и постдоктор с профессором Стивен Кук Группа в Университете Торонто (2002-2004).[5][6] Он является сопредседателем Венского центра логики и алгоритмов, который он основал вместе с Гельмут Вейт в 2012.[7][8] Он входит в редколлегию Журнал компьютерных и системных наук, Журнал дискретных алгоритмов, Журнал исследований искусственного интеллекта и Fundamenta Informaticae.[5]

Зейдер опубликовал более 140 рецензируемых публикаций в области теоретической информатики, алгоритмов, сложности вычислений, искусственного интеллекта, выполнимости высказываний и удовлетворения ограничений.[9][10]

Зейдер наиболее известен популяризацией идеи наборов бэкдоров для SAT и других задач.[11][12] и введение схем зависимости для количественные булевы формулы.[13]

Зейдер также работал над мерами ширины для таких графиков, как ширина дерева и ширина клики. Он показал с соавторами, что NP-сложно определить, меньше ли ширина клики данного графа, чем заданная граница.[14] Он установил сложность результатов для обнаружения минимально невыполнимые формулы.[15][16]

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

  1. ^ а б "Факультет информатики, Венский технический университет". Получено 13 января 2017.
  2. ^ «Стефан Зейдер - Группа алгоритмов и сложности». Получено 9 января 2017.
  3. ^ "Computerwissenschafter der TU Wien wollen internationale Marke werden". Der Standard (на немецком языке). 25 января 2012 г.. Получено 20 апреля 2020.
  4. ^ "Стефан Зейдер - Проект математической генеалогии". Проект "Математическая генеалогия". Получено 9 января 2017.
  5. ^ а б c "Стефан Зейдер". LogiCS. Получено 9 января 2017.
  6. ^ «Что здесь означает« неразрешимый »? Проф. Стефан Зейдер в портрете». Получено 13 января 2017.
  7. ^ "Алгоритмы bestimmen unser Leben". Futurezone.at (на немецком). 8 февраля 2012 г.. Получено 9 января 2017.
  8. ^ "Zentrum für Grundlagen der Informatik". Der Standard (на немецком). 31 января 2012 г.. Получено 9 января 2017.
  9. ^ "Стефан Зейдер - профессор, руководитель группы алгоритмов и сложности, TU Wien". Google ученый. Получено 9 января 2017.
  10. ^ "Стефан Зейдер - Библиография по информатике". DBLP.
  11. ^ Гасперс, Серж; Зейдер, Стефан (2012). «Многофакторная алгоритмическая революция и не только». Бэкдоры к удовлетворению. С. 287–317. CiteSeerX  10.1.1.747.5422. Дои:10.1007/978-3-642-30891-8_15. ISBN  978-3-642-30890-1. S2CID  6905561.
  12. ^ Гасперс, Серж (22 апреля 2016 г.). «Бэкдоры в SAT». Энциклопедия алгоритмов. Springer Нью-Йорк. С. 167–170. Дои:10.1007/978-1-4939-2864-4_781. ISBN  978-1-4939-2863-7.
  13. ^ Самер, Марко; Шейдер, Стефан (18 декабря 2008 г.). «Наборы бэкдора квантифицированных булевых формул». Журнал автоматизированных рассуждений. 42 (1): 77–97. CiteSeerX  10.1.1.452.5953. Дои:10.1007 / s10817-008-9114-5. S2CID  13030704.
  14. ^ Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Шейдер, Стефан (январь 2009 г.). «Ширина клики является NP-полной». Журнал SIAM по дискретной математике. 23 (2): 909–939. Дои:10.1137/070687256.
  15. ^ Шейдер, Стефан (декабрь 2004 г.). «Минимальные невыполнимые формулы с ограниченной разницей условных переменных являются управляемыми с фиксированным параметром» (PDF). Журнал компьютерных и системных наук. 69 (4): 656–674. Дои:10.1016 / j.jcss.2004.04.009.
  16. ^ Флейшнер, Герберт; Куллманн, Оливер; Шейдер, Стефан (октябрь 2002 г.). «Распознавание минимальных невыполнимых формул за полиномиальное время с фиксированной разностью разделительных переменных». Теоретическая информатика. 289 (1): 503–516. Дои:10.1016 / S0304-3975 (01) 00337-1.

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