stringtranslate.com

Юрий Гуревич

Юрий Гуревич в Швейцарской высшей технической школе Цюриха в мае 2004 года, фотография Бертрана Мейера .

Юрий Гуревич , почетный профессор Мичиганского университета , американский ученый-компьютерщик и математик , изобретатель абстрактных конечных автоматов .

Гуревич родился и получил образование в Советском Союзе . [1] Он преподавал математику там и затем в Израиле, прежде чем переехал в Соединенные Штаты в 1982 году. Самая известная работа его советского периода посвящена классической проблеме принятия решений . [2] В Израиле Гуревич работал с Сахароном Шелахом над монадическими теориями второго порядка . [3] Теорема Гуревича- Харрингтона о забывчивой определенности также относится к тому периоду. [4]

С 1982 по 1998 год Гуревич преподавал информатику в Мичиганском университете , где он начал работать над различными аспектами теории сложности вычислений [5], включая сложность в среднем случае. [6] Он стал одним из основателей новой области теории конечных моделей . [7]

Но самое главное, он заинтересовался проблемой того, что такое алгоритм . Это привело его к теории абстрактных конечных автоматов (ASM). Тезис ASM гласит, что поведенчески каждый алгоритм является ASM. [8] Несколько убедительных аксиом позволили вывести последовательный тезис ASM [9] и тезис Чёрча–Тьюринга. [10] Тезис ASM также был доказан для некоторых других классов алгоритмов. [11] [12]

С 1998 по 2018 год Гуревич работал в Microsoft Research , где основал группу по основам программной инженерии. Группа создала Spec Explorer на основе теории абстрактных конечных автоматов. Инструмент был принят командой Windows ; модифицированная версия инструмента помогла Microsoft удовлетворить требования Европейского союза к высокоуровневым исполняемым спецификациям. Позже Гуревич работал с различными группами Microsoft над различными вопросами эффективности, безопасности и защиты, [13] включая контроль доступа, [14] дифференциальное сжатие, [15] и конфиденциальность. [16]

С 1988 года Гуревич руководит рубрикой «Логика в информатике» в Бюллетене Европейской ассоциации теоретической информатики. [1] С 2013 года Гуревич в основном занимается квантовыми вычислениями , [17] продолжая при этом исследования в своих традиционных областях.

Гуревич является стипендиатом AAAS 2020 года [18] , стипендиатом ACM 1997 года [19] , стипендиатом Guggenheim 1995 года [20] , первым членом Европейской ассоциации теоретической информатики [21] , членом Academia Europaea и почетным доктором Хасселтского университета в Бельгии и Уральского государственного университета в России .

Ссылки

  1. ^ аб Бласс, Андреас; Дершовиц, Нахум; Райзиг, Вольфганг (2010), Бласс, Андреас; Дершовиц, Нахум; Рейзиг, Вольфганг (ред.), «Юрий, логика и информатика», «Области логики и вычислений » , конспекты лекций по информатике, том. 6300, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–48, doi : 10.1007/978-3-642-15025-8_1, ISBN 978-3-642-15024-1, получено 2023-07-05
  2. ^ Э. Бёргер, Э. Гредель и Ю. Гуревич. Классическая проблема принятия решений. Спрингер, 1997.
  3. ^ Ю. Гуревич. Монадические теории второго порядка. В J. Barwise и S. Feferman (ред.), Model-Theoretic Logics, Springer, 1985, 479-506.
  4. ^ Я. Гуревич и Л. Харрингтон. Автоматы, деревья и игры. STOC '82: Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений, 1982, 60-65.
  5. ^ Я. Гуревич и С. Шелах. Ожидаемое время вычислений для задачи о гамильтоновом пути. SIAM Journal on Computing 16:3, 1987, 486-502.
  6. ^ Гуревич Ю. Средняя полнота случая. Журнал компьютерных и системных наук 42:3, 1991, 346-398.
  7. ^ Y. Gurevich. К логике, приспособленной для вычислительной сложности. В M Richter et al. (ред.), Computation and Proof Theory. Springer Lecture Notes in Mathematics 1104, 1984, 175-216.
  8. ^ Y. Gurevich. Evolving Algebra 1993: Lipari Guide. В E. Börger (ред.), Specification and Validation Methods, Oxford University Press, 1995, 9–36. https://arxiv.org/abs/1808.06255
  9. ^ Ю. Гуревич. Последовательные абстрактные машины состояний захватывают последовательные алгоритмы. ACM Transactions on Computational Logic 1(1), 2000.
  10. ^ Н. Дершовиц и Ю. Гуревич. Естественная аксиоматизация вычислимости и доказательство тезиса Чёрча. Бюллетень символической логики 14:3, 2008, 299-350.
  11. ^ А. Бласс и Ю. Гуревич. Абстрактные конечные автоматы захватывают параллельные алгоритмы. ACM Transactions on Computational Logic 4(4), 2003, 578–651 и 9(3), 2008, статья 19.
  12. ^ A. Blass, Y. Gurevich, D. Rosenzweig и B. Rossman . Интерактивные алгоритмы с малым шагом II: Абстрактные конечные автоматы и теорема о характеризации. Logical Methods in Computer Science 3(4), 2007, статья 4.
  13. ^ «Патенты Google».
  14. ^ A. Blass, Y. Gurevich, M. Moskal и I. Neeman. Доказательное разрешение. В S. Nanz (ред.), Будущее программной инженерии, Springer 2011, 77–99.
  15. ^ Н. Бьёрнер, А. Бласс и Ю. Гуревич. Контентно-зависимое разбиение на фрагменты для дифференциального сжатия: подход локального максимума. Журнал компьютерных систем науки 76(3-4), 2010, 154-203.
  16. ^ Y. Gurevich, E. Hudis и JM Wing. Обратная конфиденциальность. Сообщения ACM 59(7), 2016, 38-42.
  17. ^ А. Бочаров, Ю. Гуревич и К. М. Своре . Эффективное разложение однокубитных вентилей в схемы на основе V-базиса. Physical Review A 88:1, 2013.
  18. ^ AAAS Fellows, получено 11 января 2021 г.
  19. ^ ACM Fellows, Association for Computing Machinery . Доступ 16 февраля 2010 г.
  20. ↑ Список стипендиатов, архив 22 июня 2011 г., в Wayback Machine John Simon Guggenheim Memorial Foundation . Доступ 16 февраля 2010 г.
  21. ^ "EATCS называет стипендиатов 2014 года", Вехи: награды в области компьютерных наук, назначения, сообщения ACM , 58 (1): 24, январь 2015 г., doi : 10.1145/2686734, S2CID  11485095

Внешние ссылки

Викискладе есть медиафайлы, связанные с Юрием Гуревичем .