Стефан Шейдер
Стефан Шейдер | |
|---|---|
| Национальность | австрийский |
| Альма-матер | Венский университет |
| Научная карьера | |
| Поля | Алгоритмы Сложность Теоретическая информатика Булева выполнимость Удовлетворение ограничений Параметризованная сложность |
| Учреждения | TU Wien Университет Дарема Университет Торонто Австрийская академия наук |
| Руководители докторской диссертации | Герберт Флейшнер Георг Готтлоб |
Стефан Сейдер — австрийский ученый-компьютерщик, работающий в области алгоритмов , вычислительной сложности , теоретической информатики и, в частности, над пропозициональной выполнимостью , проблемами удовлетворения ограничений и параметризованной сложностью . Он является штатным профессором факультета информатики [1] Венского технического университета (TU Wien), руководителем группы алгоритмов и сложности и сопредседателем Венского центра логики и алгоритмов (VCLA) TU Wien. [2] [3]
Образование
Сейдер получил докторскую степень по математике в Венском университете в 2001 году под руководством профессоров Герберта Фляйшнера и Георга Готтлоба , работая математиком в Австрийской академии наук . [4] [5]
Карьера и исследования
Сейдер — профессор факультета информатики Венского технического университета . [1] Ранее он был сначала преподавателем, а затем доцентом в Университете Дарема , Великобритания (2004–2009) и постдоком в группе профессора Стивена Кука в Университете Торонто (2002–2004). [5] [6] Он является сопредседателем Венского центра логики и алгоритмов, который он основал вместе с Хельмутом Вейтом в 2012 году. [7] [8] Он входит в редколлегии Journal of Computer and System Sciences , Journal of Discrete Algorithms , Journal of Artificial Intelligence Research и Fundamenta Informaticae . [5]
Сейдер опубликовал более 140 рецензируемых публикаций в областях теоретической информатики, алгоритмов, вычислительной сложности, искусственного интеллекта, пропозициональной выполнимости и удовлетворения ограничений. [9] [10]
Сейдер наиболее известен популяризацией понятия бэкдор-множеств для SAT и других задач [11] [12] и введением схем зависимости для квантифицированных булевых формул . [13]
Szeider также работал над мерами ширины для графов, такими как treewidth и clique-width . Он показал с соавторами, что NP-трудно определить, меньше ли clique-width данного графа, чем заданная граница. [14] Он установил результаты сложности для обнаружения минимально невыполнимых формул . [15] [16]
Ссылки
- ^ ab "Факультет информатики, TU Wien" . Получено 13 января 2017 г.
- ^ "Stefan Szeider - Algorithms and Complexity Group" . Получено 9 января 2017 г.
- ^ "Computerwissenschafter der TU Wien wollen Internationale Marke Werden" . Дер Стандарт (на немецком языке) . 25 января 2012 года . Проверено 20 апреля 2020 г.
- ^ "Stefan Szeider - The Mathematics Genealogy Project". Mathematics Genealogy Project . Получено 9 января 2017 г. .
- ^ abc "Stefan Szeider". LogiCS . Получено 9 января 2017 г. .
- ^ "Что здесь означает "нерастворимый"? Портрет профессора Стефана Шейдера" . Получено 13 января 2017 г.
- ^ "Алгоритмы лучших результатов в жизни" . Futurezone.at (на немецком языке). 8 февраля 2012 года . Проверено 9 января 2017 года .
- ^ "Центр информатики" . Дер Стандарт (на немецком языке). 31 января 2012 года . Проверено 9 января 2017 года .
- ^ "Stefan Szeider - Professor, Head of Algorithms and Complexity Group, TU Wien". Google Scholar . Получено 9 января 2017 г. .
- ^ "Stefan Szeider - Библиография по компьютерным наукам". DBLP .
- ^ Гасперс, Серж; Сейдер, Стефан (2012). «Backdoors to Satisfaction». Многомерная алгоритмическая революция и не только . Конспект лекций по информатике. Том 7370. С. 287–317. CiteSeerX 10.1.1.747.5422 . doi :10.1007/978-3-642-30891-8_15. ISBN 978-3-642-30890-1. S2CID 6905561.
- ^ Gaspers, Serge (22 апреля 2016 г.). «Backdoors to SAT». Энциклопедия алгоритмов . Springer New York. стр. 167–170. doi :10.1007/978-1-4939-2864-4_781. ISBN 978-1-4939-2863-7.
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - ^ Самер, Марко; Сейдер, Стефан (18 декабря 2008 г.). «Backdoor Sets of Quantified Boolean Formulas». Journal of Automated Reasoning . 42 (1): 77–97. CiteSeerX 10.1.1.452.5953 . doi :10.1007/s10817-008-9114-5. S2CID 13030704.
- ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (январь 2009 г.). «Clique-Width is NP-Complete». SIAM Journal on Discrete Mathematics . 23 (2): 909–939. doi :10.1137/070687256.
- ^ Szeider, Stefan (декабрь 2004 г.). "Минимальные невыполнимые формулы с ограниченной разностью переменных в предложениях являются фиксированно-параметрически трактуемыми" (PDF) . Журнал компьютерных и системных наук . 69 (4): 656–674. doi :10.1016/j.jcss.2004.04.009.
- ^ Флейшнер, Герберт; Куллманн, Оливер; Сейдер, Стефан (октябрь 2002 г.). «Распознавание минимальных невыполнимых формул с фиксированной разностью клаузулярных переменных за полиномиальное время». Теоретическая информатика . 289 (1): 503–516. doi : 10.1016/S0304-3975(01)00337-1 .
Внешние ссылки
- Официальный сайт
