Русская Википедия:Кук, Стивен Артур
Шаблон:Однофамильцы Шаблон:Учёный Стивен Артур Кук (Шаблон:Lang-en; род. 14 декабря 1939 года, Буффало, США) — американский учёный в области теории вычислительных систем. Знаменит своей работой над теорией сложности вычислений, лауреат премии Тьюринга.
В своей работе «The Complexity of Theorem Proving Procedures»[1] Кук доказал, что задача выполнимости булевых формул является NP-полной. Тем самым он поднял вопрос о равенстве классов сложности P и NP, один из сложнейших вопросов теории вычислительных систем, на который до сих пор нет ответа.
Член Канадского королевского общества (1984), Национальной академии наук США (1985)[2], Лондонского королевского общества (1998)[3].
Биография
Кук получил титул бакалавра в Мичиганском университете в 1961 году. Год спустя он получил степень магистра наук в Гарварде, где в 1966 году достиг степени доктора философии. До 1970 года работал ассистентом (Шаблон:Lang-en) по математике в Беркли, где так и не получил статус постоянного сотрудника. Ричард Карп, лауреат премии Тьюринга 1985 года, скажет об этом Шаблон:Начало цитатыЭто навсегда останется нашей виной, что мы не смогли уговорить факультет математики дать ему этот статус. Шаблон:Oq Шаблон:Конец цитаты Эту честь ему оказал Торонтский университет, назначив Стивена Кука профессором в 1975 году.
Награды
- 1982 — Премия Тьюринга «За существенный прогресс, достигнутый им в понимании сложности вычислений. Его работа положила основу теории NP-полноты. Исследование свойств и границ этого класса стало одним из важнейших направлений теории вычислительных систем за последние десять лет.»[4]Шаблон:Ref-en
- 1999 — CRM-Fields-PIMS prize
- 2012 — Канадская золотая медаль Герхарда Херцберга
- 2015 — BBVA Foundation Frontiers of Knowledge Awards «За его важную роль в определении того, что компьютеры могут и не могут эффективно решать. Его работы оказали огромное влияние на всех полях, где сложные вычисления имеют решающее значение.»[5]Шаблон:Ref-en
См. также
Примечания
Ссылки
- Сайт Стивена Кука при Торонтском университетеШаблон:Ref-en
- «Stephen Cook» на сайте Шаблон:AbbrШаблон:Ref-en
Шаблон:Выбор языка Шаблон:- Шаблон:Премия Тьюринга
- Русская Википедия
- Родившиеся в Буффало
- Учёные в области информатики США
- Выпускники Гарвардского университета
- Члены Канадского королевского общества
- Члены Национальной академии наук США
- Члены Лондонского королевского общества
- Члены Гёттингенской академии наук
- Награждённые канадской золотой медалью Герхарда Херцберга
- Лауреаты премии Джона Синга
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии