23-10-2023
Стивен Артур Кук | |
Stephen Arthur Cook | |
Дата рождения: |
14 декабря 1939 (72 года) |
---|---|
Место рождения: | |
Страна: | |
Научная сфера: | |
Место работы: | |
Альма-матер: | |
Научный руководитель: |
Хао Ванг (Hao Wang) |
Известные ученики: | |
Известен как: | |
Награды и премии | |
Сайт: |
http://www.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 года, скажет об этом
Это навсегда останется нашей виной, что мы не смогли уговорить факультет математики дать ему этот статус.Оригинальный текст (англ.)It is to our everlasting shame that we were unable to persuade the math department to give him tenure.
— Ричард Карп к 30-летию факультета информатики Беркли[2]
Эту честь ему оказал Торонтский университет, назначив Стивена Кука профессором в 1975 году.
Лауреаты премии Тьюринга | |
---|---|
Перлис (1966) • Уилкс (1967) • Хэмминг (1968) • Минский (1969) • Уилкинсон (1970) • Маккарти (1971) • Дейкстра (1972) • Бахман (1973) • Кнут (1974) • Ньюэлл + Саймон (1975) • Рабин + Скотт (1976) • Бэкус (1977) • Флойд (1978) • Айверсон (1979) • Хоар (1980) • Кодд (1981) • Кук (1982) • Томпсон + Ритчи (1983) • Вирт (1984) • Карп (1985) • Хопкрофт + Тарьян (1986) • Кок (1987) • Сазерленд (1988) • Кэхэн (1989) • Корбато (1990) • Милнер (1991) • Лэмпсон (1992) • Хартманис + Стернс (1993) • Фейгенбаум + Редди (1994) • Блюм (1995) • Пнуели (1996) • Энгельбарт (1997) • Грей (1998) • Брукс (1999) • Яо (2000) • Даль + Нюгорд (2001) • Ривест + Шамир + Адлеман (2002) • Кэй (2003) • Серф + Кан (2004) • Наур (2005) • Аллен (2006) • Кларк + Эмерсон + Сифакис (2007) • Лисков (2008) • Текер (2009) • Вэлиант (2010) • Перл (2011) |
Кук, Стивен Артур.