استیون کوک

استیون آرتور کوک
زادهٔ۱۴ دسامبر ۱۹۳۹ ‏(۸۵ سال)
ملیتآمریکایی
محل تحصیلدانشگاه هاروارد
دانشگاه میشیگان
شناخته‌شده
برای
ان‌پی کامل
Proof complexity
قضیه کوک لوین
جوایزجایزه تورینگ (۱۹۸۲)
پیشینه علمی
شاخه(ها)علوم کامپیوتر
محل کاردانشگاه کالیفرنیا، برکلی
دانشگاه تورنتو
استاد راهنماهائو وانگ
دانشجویان دکتریوالتر ساویتچ
کوک در سال ۱۹۶۸

استیون آرتور کوک (به انگلیسی: Stephen Arthur Cook) (زاده ۱۴ دسامبر، ۱۹۳۹-بوفالو، نیویورک)، یک دانشمند آمریکایی علوم رایانه و یک ریاضیدان سرشناس است که سهم عمده‌ای در رشته‌های نظریه پیچیدگی محاسباتی و پیچیدگی اثبات داشته‌است. وی در حال حاضر یک استاد دانشگاه در بخش علوم کامپیوتر و ریاضیات دانشگاه تورنتو است.

زندگی‌نامه

کوک در سال ۱۹۳۹ در بوفالو، نیویورک به دنیا آمد. پدرش یک شیمیدان بود و برای Union Carbide کار می‌کرد و در دانشگاه محلی بوفالو نیز تدریس می‌کرد.

وقتی کوک ۱۰ ساله شد، خانواده‌اش به مزرعه‌ای در کلارنس، نیویورک، نقل مکان کردند. در آنجا با ویلسون گریت بچ، مخترع ضربان ساز قابل کشت، آشنا شد. کوک، رابطه دوستی را با گریت بچ برقرار کرد و وقت زیادی را در کمک کردن به وی در لحیم کاری ترانزیستور صرف کرد. همین تجربه‌ها، دوره‌ای از مهندسی برق را برایش به ارمغان آورد.

در سال ۱۹۵۷ به دانشگاه میشیگان رفت. در آنجا او و دوستش برنامه‌ای برای تست کردن حدس گلدباخ نوشتند. تا وقتی که برنامه ادامه پیدا می‌کرد، بیانگر درستی حدس بود. در سال ۱۹۶۱ وی مدرک لیسانس خود را که بخش عمده‌اش را ریاضیات تشکیل می‌داد گرفت.

مدرک کارشناسی ارشد و دکترای خود را به ترتیب در سال‌های ۱۹۶۲ و ۱۹۶۶ از دانشگاه هاروارد دریافت کرد که هر دوی آن‌ها در ریاضیات بودند. هدف اولیهٔ کوک، تحقیقات در زمینه جبر بود، ولی در مقطع دکترا به طلسم علوم کابردی هائو ونگ، کسی که در منطق ریاضی و فلسفه تعلیم دیده بود، دچار شد. در این زمان، ونگ در حال کار روی اثبات خودکار قضیه، کشف خودکار اثبات‌ها به وسیلهٔ رایانه، بود.

کوک همچنین به کار مایکل رابین، به ویژه مقاله‌اش بر روی نظریه محاسبات پی برد. در ادامه، رابین تعدادی از لکچرها را به دست کوک رساند و در پایان، این اتفاقات کوک را به سمت مطالعه در زمینه محاسبات گزاره‌ای سوق داد.

او در سال ۱۹۶۶ به عنوان پروفسور دستیار به بخش ریاضیات دانشگاه کالیفرنیا، برکلی، پیوست و تا سال ۱۹۷۰، هنگامی که از انتصاب مجددش منع شد در آنجا ماند.

در یک سخنرانی که با سی‌امین سالگرد بخش EECS برکلی همراه بود، برنده جایزه تورینگ و پروفسور برکلی، ریچارد کارپ اظهار داشت: «سرافکندگی ابدی ماست که ما قادر نبودیم بخش ریاضی را ترغیب کنیم تا او را نگه دارند».

کوک در سال ۱۹۷۰ به عنوان یک پروفسور دستیار به هیئت علمی دانشگاه تورنتو، بخش‌های علوم کامپیوتر و ریاضیات پیوست که بعدها در آنجا، در سال ۱۹۷۵ به مقام پروفسور و در سال ۱۹۸۵ به مقام پروفسور دانشگاه ارتقا پیدا کرد.

او در سال ۱۹۶۸ ازدواج کرد. دو فرزند دارد که یکی از آن‌ها در حال تحصیل در مقطع دکترا در دانشگاه برکلی، رشته علوم رایانه است. کوک در حال حاضر به همراه همسر خود در تورنتو زندگی می‌کند. وی ویولن می‌نوازد و از قایقرانی لذت می‌برد.

پژوهش‌ها

کوک یکی از پدران نظریه پیچیدگی محاسباتی قلمداد می‌شود. در طول دوره دکترا، کوک در زمینه پیچیدگی توابع، به ویژه ضرب، کار کرد.

در اواسط دههٔ ۱۹۷۰ کوک تبادل بین زمان و حافظه در عملیات کامپیوتری را مورد بررسی قرار داد. وی قادر بود اثبات کند که هیچ روشی نمی‌تواند هم از نظر زمان کارا باشد و هم از نظر حافظه. سال بعد، در مقاله سال ۱۹۷۱ خود، «پیچیدگی رویه‌های اثبات قضیه»، مفاهیم کاهش چندجمله‌ای زمانی (که با کاهش کوک نیز شناخته شده‌است) و ان پی کامل بودن را رسمی‌کرد و وجود یک مسئله ان پی کامل را به وسیلهٔ نشان دادن این‌که مسئله ارضاپذیری بولی ان پی کامل است، اثبات کرد. این قضیه به‌طور مستقل توسط لئونید لوین در اتحاد جماهیر شوروی ثابت شد و به همین دلیل نام قضیه کوک-لوین را به خود گرفته‌است.

پروفسورد کوک و کرایچک

این مقاله، مشهورترین مسئله علوم کامپیوتر، یعنی مسئله برابری پی و ان‌پی را نیز رسمی‌کرده‌است. به بیان ساده‌تر مسئله برابری پی و ان‌پی به دنبال این است که آیا هر مسئله بهینه‌سازی که جواب‌هایش می‌توانند به‌طور مؤثری برای درستی/بهینگی مورد بررسی قرار گیرند، می‌تواند به‌طور بهینه‌ای با یک الگوریتم مؤثر و کارآمد حل شود یا خیر. با فراوانی این‌گونه مسائل بهینه‌سازی در زندگی روزمره، یک جواب مثبت به این سؤال، احتمالاً پیامدهای عملی و فلسفی عمیقی را دربر خواهد داشت.

کوک حدس می‌زند که مسائل بهینه‌سازی (با حل‌هایی که به آسانی بررسی شوند) وجود دارند که نمی‌توانند با الگوریتم‌های مؤثری حل شوند. به عبارت دیگر پی با ان پی برابر نیست. این حدس تعداد زیادی از تحقیقات در زمینه نظریه پیچیدگی محاسباتی را موجب شده‌است، که به‌طور قابل ملاحظه‌ای درک ما را از سختی ذاتی مسائل محاسباتی و اینکه چه چیزی می‌تواند به‌طور مؤثری محاسبه شود بهبود بخشیده‌است. در حال حاضر، این حدس، باز است و در میان ۷ مسئله ی یک میلیون دلاری قرار دارد.

در سال ۱۹۸۲ کوک جایزه معتبر تورینگ را به خاطر سهمش در نظریه پیچیدگی دریافت کرد. تقدیر از وی این‌گونه آغاز شد: «برای بالا بردن درک ما از پیچیدگی محاسبات با یک روش مهم و عمیق».

کوک بیش از ۱۰۰ مقاله در زمینه‌های علوم کامپیوتر نظری و پیچیدگی موازی منتشر کرده‌است. با این حال، هنوز هم به دلیل رسمی‌کردن ایده ان پی کامل بودن است که شناخته شده‌است.

جستارهای وابسته

منابع

پیوند به بیرون

Read other articles:

Acqua Acetosastazione ferroviaria LocalizzazioneStato Italia LocalitàRoma Coordinate41°55′53.04″N 12°29′12.12″E / 41.9314°N 12.4867°E41.9314; 12.4867Coordinate: 41°55′53.04″N 12°29′12.12″E / 41.9314°N 12.4867°E41.9314; 12.4867 Altitudine18 m s.l.m. Lineeferrovia Roma-Civita Castellana-Viterbo StoriaStato attualein uso Attivazione1932 CaratteristicheTipoStazione in superficie, passante Binari3 + 5 rimesse GestoriASTRAL (1º lug...

 

Gottfried Leibniz argumentó que debían introducirse números idealizados que contuvieran infinitesimales La historia del cálculo está repleta de debates filosóficos sobre el significado y la validez lógica de los números denominados fluxiones o infinitesimales. La forma estándar de resolver estos debates es definir las operaciones de cálculo utilizando procedimientos épsilon-delta en lugar de infinitesimales. El análisis no estándar[1]​[2]​[3]​ reformula el cálc...

 

Esta é uma lista dos filmes vencedores do Prémio Sophia de Melhor Filme, principal prémio outorgado anualmente pela Academia Portuguesa de Cinema.[1][2][3][4][5][6][7] História O número máximo possível que um filme pode receber é de 17 Sophias, considerando 7 das 8 categorias principais e as 10 categorias técnicas, contando que um filme somente pode integrar uma das duas categorias de Melhor Argumento. Desde a criação dos Prémios, de entre os vencedores do Sophia de Melhor Filme o...

Pacific Electric lines emanating from Downtown Los Angeles, 1917 The following passenger rail lines were operated by the Pacific Electric Railway and its successors from the time of its merger in 1911 until the last line was abandoned in 1961. One count indicated that the company and its successors operated as many as 143 different routes in that time.[1] List of lines There were three primary terminals in downtown Los Angeles: 6th & Main Station, opened 1905 on the south side of ...

 

Musée de la révolution ukrainienne (1917-1921)Informations généralesType Attraction touristique, bâtimentBâtimentProtection Monument du patrimoine architectural (d)LocalisationLocalisation rue Volodymyrska (en) UkraineCoordonnées 50° 26′ 41″ N, 30° 30′ 49″ Emodifier - modifier le code - modifier Wikidata Le Musée de la révolution ukrainienne (ukrainien : Київський міський будинок учителя) est un musée co...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مارس 2020) راتنا ساري ديوي سوكارنوラトナ・サリ・デヴィ・スカルノ (باليابانية: ラトナ・サリ・デヴィ・スカルノ)‏  راتنا ساري ديوي سوكارنو في عام 1970 معلومات شخصية اسم الولادة (بالياب

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يناير 2022) عمر طارق   معلومات شخصية الميلاد 8 سبتمبر 1991 (32 سنة)  الحياة العملية تعديل مصدري - تعديل   عمر طارق سيد عرابي (مواليد 8 سبتمبر 1991) هو لاعب كرة سلة مصري يلعب...

 

Aimi TerakawaNama asal寺川 愛美Lahir25 Desember 1991 (umur 31)Kobe, Prefektur Hyōgo, JepangPekerjaan pengisi suara penyanyi Tahun aktif2010–sekarangAgenHibikiTinggi158 cm (5,18 ft)[1]Karier musikGenre J-pop Anison Instrumen Vokal Gitaris Tahun aktif2011–sekarangLabelPony CanyonKing Records (2020–sekarang)Artis terkaitMilky Holmes FeathersPoppin'PartyPeaky P-KeySitus webaimi.info Aimi Terakawa (寺川 愛美, Terakawa Aimi, lahir 25 Desember ...

 

Hurfeish חֻרְפֵישׁ, חורפישحرفيشTranskripsi bahasa Ibrani • ISO 259Ḥurp̄eišHurfeishTampilkan peta Israel Barat LautHurfeishTampilkan peta IsraelKoordinat: 33°01′04″N 35°20′46″E / 33.01778°N 35.34611°E / 33.01778; 35.34611Koordinat: 33°01′04″N 35°20′46″E / 33.01778°N 35.34611°E / 33.01778; 35.34611Posisi kisi182/269 PALNegara IsraelDistrikUtaraPemerintahan • Jen...

For the New York City Subway station, see President Street (IRT Nostrand Avenue Line). United States historic placePresident Street StationU.S. National Register of Historic PlacesBaltimore City Landmark An 1856 illustration of President Street Station in BaltimoreLocationPresident Street at Fleet Street (southeast corner)Baltimore, Maryland, U.S.Coordinates39°17′2.4″N 76°36′8.8″W / 39.284000°N 76.602444°W / 39.284000; -76.602444Arealess than one acreBuilt1...

 

2005 single by Angie StoneI Wasn't KiddingSingle by Angie Stonefrom the album Stone Hits: The Very Best of Angie Stone Released2005Length4:28Songwriter(s) Andrea Martin Adrian Austin Cecil Womack Linda Womack Producer(s) Andrea Martin Vada Nobles Angie Stone singles chronology Stay for a While (2004) I Wasn't Kidding (2005) Baby (2007) I Wasn't Kidding is a song by American recording artist Angie Stone. It was written by Andrea Martin and Adrian Austin for Stone's first compilation album Ston...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (فبراير 2019) اضغط هنا للاطلاع على كيفية قراءة التصنيف محبة النحاس البامبية المرتبة التصنيفية نوع  التصنيف العلمي  فوق النطاق  حيويات مملكة عليا  حيويات مملكة&...

Koordinat: 2°43′51″S 101°26′40″E / 2.7308445°S 101.4443209°E / -2.7308445; 101.4443209 Kabupaten MukomukoKabupatenTari Gandai, tarian tradisional dari Mukomuko LambangMotto: Kapuang sakti ratau batuahSakti di wilayahnya sendiri serta bertuah bagi wilayah lainnyaPetaKabupaten MukomukoPetaTampilkan peta SumatraKabupaten MukomukoKabupaten Mukomuko (Indonesia)Tampilkan peta IndonesiaKoordinat: 2°35′00″S 101°07′01″E / 2.5833°S 101...

 

Murder of British teenager in drug- and gang-related circumstances Murder of Mary-Ann LeneghanMary-Ann LeneghanWallingford ArmsAbbey House HotelProspect ParkMurder of Mary-Ann Leneghan (Reading, Berkshire)LocationProspect Park, Reading, Berkshire, United KingdomDate7 May 2005 (2005-05-07) c. 03:00 BSTAttack typeStabbing, rape, assault, shootingWeaponsFlick knife, firearm[a]Injured2VictimMary-Ann Leneghan[b]PerpetratorsLlewellyn Adams, Indrit Krasniqi, Mich...

 

Greek mythological king This article is about figure from Greek mythology. For the butterfly genus, see Danaus (genus). For the former cruise ship Danaos, see CS Salamis Glory. In Greek mythology, Danaus (/ˈdæneɪ.əs/,[1] /ˈdæni.əs/;[2] Ancient Greek: Δαναός Danaós) was the king of Libya. His myth is a foundation legend of Argos, one of the foremost Mycenaean cities of the Peloponnesus. In Homer's Iliad, Danaans (tribe of Danaus) and Argives commonly designate the...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Joachim KunertLahir(1929-09-24)24 September 1929Berlin, JermanMeninggal18 September 2020(2020-09-18) (umur 90)PekerjaanSutradara, penulis naskahTahun aktif1954–1989 Joachim Kunert (24 September 1929 – 18 September 2020) ada...

 

Live music venue in Pennsylvania, U.S. Mr. SmallsMr. Smalls exteriorFormer namesSt. Ann's Catholic ChurchAddress400 Lincoln AvenueLocationMillvale, Pennsylvania 15209 United StatesOwnerMike Speranzo, Liz BerlinTypeLive music venue, nightclub, barGenre(s)MusicSeating typestanding and seatingCapacity1000 (800 in Theatre)ConstructionBuilt1924Opened2002Renovated2000Expanded2014ArchitectVariousWebsitewww.mrsmalls.com Mr. Smalls is a live music venue in the Millvale neighborhood of Pittsburgh, Penn...

 

2008 video by Static-XCannibal Killers LiveVideo by Static-XReleasedOctober 7, 2008 (2008-10-07)[1][2]RecordedJune 2, 2007 (2007-06-02)VenueThe Big Easy, Spokane, WashingtonGenreIndustrial metal, nu metal, alternative metalLabelReprise[2]Static-X chronology Cannibal(2007) Cannibal Killers Live(2008) Cult of Static(2009) Cannibal Killers Live is a CD/DVD box set by American industrial metal band Static-X. It is the first time the ba...

YaelGambar Yael yang hendak membunuh Sisera, karya James Tissot dalam koleksi Museum Yahudi di New York.KebangsaanKeniNama lainJael, Ya'elSuami/istriHeber, orang Keni Yael (bahasa Ibrani: יָעֵל, Ya'el, artinya: rusa Ibex; bahasa Inggris: Jael) adalah seorang tokoh perempuan dalam Alkitab Ibrani atau Perjanjian Lama di Alkitab Kristen. Ia adalah istri Heber, orang Keni (Hakim-hakim 4:17).[1][2] Ia mengundang Sisera, sang panglima pasukan Raja Yabin, orang Kanaan d...

 

Cantón de Le Caylar Cantón Situación del cantón de Le Caylar Coordenadas 43°51′N 3°18′E / 43.85, 3.3Capital Le CaylarEntidad Cantón • País  Francia • Región Languedoc-Rosellón • Departamento Hérault • Distrito LodèveConsejero general Frédéric Roig (2004-2015)Subdivisiones Comunas 8Superficie   • Total 227.57 km²Población (2012)   • Total 1052 hab.Código cantonal 3408 Mapa del cantón con su...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!