Эдуард Алексеевич Гирш

Материал из Циклопедии
Перейти к: навигация, поиск

Эдуард Алексеевич Гирш

Edward.a.hirsch.jpg
Дата рождения 26 декабря 1973 года
Место рождения Благовещенск





Научная сфера математика








Эдуард Алексеевич Гирш — российский математик, специалист по теоретической информатике, в.н.с. ПОМИ РАН, д.ф.-м.н., профессор РАН, член Совета по науке Министерства образования и науки РФ[1].

Содержание

[править] Ранний период

В 1995 г. окончил мехмат (кафедра Математического обеспечения ЭВМ) СПбГУ.

[править] Карьера

В 1995 г. поступил в аспирантуру лаборатории математической логики ПОМИ РАН.

В 1998 г. стал к.ф.м.н.[Прим. 1]

С 1999 г. — в.н.с. лаборатории математической логики ПОМИ РАН.

В 2000—2010 гг. — доцент кафедры информатики СПбГУ.

С 2008 г. трудился профессором и завкафедрой Математических и информационных технологий СПАУ.

В 2011 г. стал д.ф.м.н.[Прим. 2]

[править] Вклад в науку

Его учёная деятельность описывается следующим образом:

Научные интересы и основные результаты Гирша относятся к алгоритмам и теории сложности вычислений. Основные результаты включают в себя новые алгоритмы для задачи выполнимости булевой формулы, экспоненциальные нижние оценки для полуалгебраических систем доказательств, конструкции оптимальных эвристических алгоритмов. Алгоритм для задачи выполнимости k-КНФ (k-SAT), предложенный Гиршем совместно с коллегами в 2002 году, до сих пор является самым быстрым детерминированным алгоритмом для этой задачи.
В совместной работе Э. А. Гирша с Д. Ю. Григорьевым и Д. В. Пасечником была развита теория полуалгебраических систем доказательств — формальных систем, которые используются для доказательств тавтологий, которые основаны на представлении логических выражений при помощи полиномов. Для некоторых таких систем доказаны нижние и верхние оценки.
С Д. М. Ицыксоном разработал теорию эвристических акцепторов — принимающих алгоритмов, которым разрешено иногда ошибаться на некоторых входах. Такой подход позволяет описывать более широкий круг задач, чем традиционные безошибочные алгоритмы. Для эвристических акцепторов, решающих некоторую задачу, доказано безусловное существование оптимального алгоритма (поточечная оптимальность).

[править] Труды

  • E. A. Hirsch; D. Itsykson; I. Monakhov; A. Smal. On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography // Theory of Computing Systems: journal. — Springer, 2012. — Vol. 51. — P. 179—195.
  • E. Dantsin; A. Goerdt; E. A. Hirsch; R. Kannan; J. Kleinberg; C. Papadimitriou; P. Raghavan; U. Schoning. A Deterministic (2−2/(k+1))^n Algorithm for k-SAT Based on Local Search // Theoretical Computer Science: journal. — Elsevier, 2002. — Vol. 289/1. — P. 69—83.
  • E. A. Hirsch. New Worst-Case Upper Bounds for SAT // Journal of Automated Reasoning: journal. — Kluwer Academic Publishers, 2000. — Vol. 24(4). — P. 397—420.
  • D. Grigoriev; E. A. Hirsch; D. V. Pasechnik. Complexity of Semi-Algebraic Proofs (неопр.) // Moscow Mathematical Journal. — 2002. — Т. 2(4). — С. 647—679.
  • E. Dantsin; E. A. Hirsch. Worst-Case Upper Bounds // Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications (англ.. — IOS Press, 2009. — Vol. 185. — P. 403—424.

[править] Примечания

  1. Защитил кандидатскую диссертацию на тему «Теоретические оценки времени работы алгоритмов для задачи выполнимости булевых формул».
  2. Защитил докторскую диссертацию на тему «Сложность пропозициональной логики».

[править] Источники

  1. Эдуард Алексеевич Гирш на сайте ПОМИ РАН
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты