Кук, Стивен Артур

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Стивен Артур Кук
Stephen Arthur Cook
Prof.Cook.jpg
Дата рождения:

14 декабря 1939({{padleft:1939|4|0}}-{{padleft:12|2|0}}-{{padleft:14|2|0}}) (75 лет)

Место рождения:

Буффало, штат Нью-Йорк, США

Страна:

США

Научная сфера:

Информатика

Место работы:

Калифорнийский университет в Беркли
Торонтский университет

Альма-матер:

Гарвардский университет

Научный руководитель:

Хао Ванг (Hao Wang)

Известные ученики:

Уолтер Савич

Известен как:

Теория сложности вычислений

Награды и премии


Премия Тьюринга

Сайт:

cs.toronto.edu/~sacook/

Стивен Артур Кук на Викискладе

Стивен Артур Кук (англ. Stephen Arthur Cook, 14 декабря 1939 года, Буффало, США) — американский учёный в области теории вычислительных систем. Знаменит своей работой над теорией сложности вычислений, лауреат премии Тьюринга.

В своей работе «The Complexity of Theorem Proving Procedures»[1] Кук доказал, что задача выполнимости булевых формул является NP-полной. Тем самым он поднял вопрос о равенстве классов сложности P и NP, один из сложнейших вопросов теории вычислительных систем, на который до сих пор нет ответа.

Биография[править | править вики-текст]

Кук получил титул бакалавра в Мичиганском университете в 1961 году. Год спустя он получил степень магистра наук в Гарварде, где в 1966 году достиг степени доктора философии. До 1970 года работал ассистентом (англ. assistant professor) по математике в Беркли, где так и не получил статус постоянного сотрудника. Ричард Карп, лауреат премии Тьюринга 1985 года, скажет об этом

Это навсегда останется нашей виной, что мы не смогли уговорить факультет математики дать ему этот статус.

Ричард Карп к 30-летию факультета информатики Беркли[2]

Эту честь ему оказал Торонтский университет, назначив Стивена Кука профессором в 1975 году.

Награды[править | править вики-текст]

  • 1982 — Премия Тьюринга «За существенный прогресс, достигнутый им в понимании сложности вычислений. Его работа положила основу теории NP-полноты. Исследование свойств и границ этого класса стало одним из важнейших направлений теории вычислительных систем за последние десять лет.»[3]

Примечания[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]