Stephen Cook – Wikipedia, wolna encyklopedia

Stephen Arthur Cook (ur. 14 grudnia 1939 w Buffalo, Nowy Jork^[1]) – amerykański informatyk, za wkład w rozwój teorii złożoności obliczeniowej otrzymał nagrodę Turinga w 1982 roku^[1].

Życiorys[edytuj | edytuj kod]

Ojciec Cooka pracował jako chemik w filii Union Carbide, a także był adiunktem w SUNY Buffalo^[2]. Jego matka pracowała jako gospodyni domowa, a także jako nauczycielka języka angielskiego w Erie Community College^[2]. W wieku 10 lat przeprowadził się wraz z rodziną do Clarence w stanie Nowy Jork^[2]. Jako nastolatek zainteresował się elektroniką i pracował dla Wilsona Greatbatcha^[2].

Cook rozpoczął studia na Uniwersytecie Michigan w 1957 roku na kierunku inżynieria nauk ścisłych^[2]. Zmienił kierunek na matematykę i uzyskał tytuł licencjata w 1961 roku^[2]. Następnie rozpoczął studia podyplomowe na Wydziale Matematyki Uniwersytetu Harvarda^[2]. Cook uzyskał raz tytuł magistra (1962) i doktorat (1966) w dziedzinie informatyki na Uniwersytecie Harvarda^[1].

Jego praca magisterska zatytułowana O minimalnym czasie obliczania funkcji dotyczy wewnętrznej złożoności obliczeniowej mnożenia^[2]. Jednym z wkładów było ulepszenie algorytmu mnożenia Andrei Tooma, znanego obecnie jako Toom–Cook multiplication^[2]. Algorytm ten jest nadal przedmiotem badań i ma praktyczne znaczenie w arytmetyce o wysokiej precyzji^[2].

Po opuszczeniu Harvardu podjął pracę na wydziale Uniwersytetu Kalifornijskiego w Berkeley^[1].

W 1970 Cook przeniósł się na Uniwersytet w Toronto, gdzie w 1985 został profesorem nadzwyczajnym^[1][2]. W 1971 roku Cook opublikował „The Complexity of Theorem Proving Procedures”, przełomowy artykuł, który położył podwaliny pod teorię problemów NP-zupełnych – problemów, dla których nie jest znany skuteczny algorytm rozwiązania^[1][2]. Cook wykazał, że niektóre problemy w NP, znane obecnie jako problemy NP-zupełne, są tak samo trudne do rozwiązania jak inne w NP, w tym sensie, że jeśli którykolwiek z tych problemów jest łatwy do rozwiązania, to wszystkie problemy w NP są łatwe do rozwiązania^[2].

Cook opracował metodę redukcji ograniczonej zasobami^[2]. Technika ta jest podstawowym narzędziem w teorii złożoności obliczeniowej i stanowi podstawę w bezpieczeństwie kryptograficznym opartym na złożoności^[2].

Cook miał również duży wpływ w dziedzinach, jak teoria automatów, obliczenia równoległe, semantyka i weryfikacja języka programu, algebra obliczeniowa oraz obliczalność^[2].

Cook jest członkiem Royal Society of London, Royal Society of Canada, U.S. National Academy of Sciences oraz American Academy of Arts and Sciences^[1]. Był stypendystą NSERC Steacie w latach 1978-79, otrzymał stypendium Killam Research Fellowship w latach 1982-83 i wiele nagród^[2].

Obecnie mieszka w Toronto z żoną Lindą i ma dwóch synów^[2]. Jest żeglarzem i wieloletnim członkiem Royal Canadian Yacht Club^[2].

Przypisy[edytuj | edytuj kod]