استفن کوک
| استفن آرتور کوک | |
|---|---|
 |
|
| متولد | ۱۴ دسامبر ۱۹۳۹ (۷۳ سال) بوفالو، نیویورک |
| ملیت | آمریکایی |
| رشته فعالیت | علوم کامپیوتر |
| محل کار | دانشگاه کالیفرنیا، برکلی دانشگاه تورنتو |
| استاد راهنما | هائو وانگ |
| دانشجویان دکتری وی | والتر ساویتچ |
| دلیل شهرت | انپی کامل Proof complexity قضیه کوک لوین |
| جوایز | جایزه تورینگ (۱۹۸۲) |
استفن آرتور کوک (به انگلیسی: Stephen Arthur Cook) (زاده ۱۴ دسامبر، ۱۹۳۹-بوفالو، نیویورک)، یک دانشمند آمریکایی علوم رایانه و یک ریاضیدان سرشناس است که سهم عمده ای در رشته های نظریه پیچیدگی محاسباتی و پیچیدگی اثبات داشته است. وی در حال حاضر یک استاد دانشگاه در بخش علوم کامپیوتر و ریاضیات دانشگاه تورنتو می باشد.
محتویات |
زندگی نامه [ویرایش]
کوک در سال ۱۹۳۹ در بوفالو، نیویورک به دنیا آمد. پدرش یک شیمیدان بود و برای Union Carbide کار می کرد و در دانشگاه محلی بوفالو نیز تدریس میکرد.
وقتی کوک ۱۰ ساله شد، خانوادهاش به مزرعهای در کلارنس، نیویورک، نقل مکان کردند. در آنجا با ویلسون گریت بچ، مخترع ضربان ساز قابل کشت، آشنا شد. کوک، رابطه دوستی را با گریت بچ برقرار کرد و وقت زیادی را در کمک کردن به وی در لحیم کاری ترانزیستور صرف کرد. همین تجربهها، دوره ای از مهندسی برق را برایش به ارمغان آورد.
در سال ۱۹۵۷ به دانشگاه میشیگان رفت. در آنجا او و دوستش برنامه ای برای تست کردن حدس گلدباخ نوشتند. تا وقتی که برنامه ادامه پیدا می کرد، بیانگر درستی حدس بود. در سال ۱۹۶۱ وی مدرک لیسانس خود را که بخش عمدهاش را ریاضیات تشکیل میداد گرفت.
مدرک کارشناسی ارشد و دکترای خود را به ترتیب در سال های ۱۹۶۲ و ۱۹۶۶ از دانشگاه هاروارد دریافت کرد که هر دوی آنها در ریاضیات بودند. هدف اولیهی کوک، تحقیقات در زمینه جبر بود، ولی در مقطع دکترا به طلسم علوم کابردی هائو ونگ، کسی که در منطق ریاضی و فلسفه تعلیم دیده بود، دچار شد. در این زمان، ونگ در حال کار روی اثبات خودکار قضیه، کشف خودکار اثباتها بوسیله رایانه، بود.
کوک همچنین به کار مایکل رابین، بویژه مقالهاش بر روی نظریه محاسبات پی برد. در ادامه، رابین تعدادی از لکچرها را به دست کوک رساند و در پایان، این اتفاقات کوک را به سمت مطالعه در زمینه محاسبات گزاره ای سوق داد.
او در سال ۱۹۶۶ به عنوان پروفسور دستیار به بخش ریاضیات دانشگاه کالیفرنیا، برکلی، پیوست و تا سال ۱۹۷۰، هنگامی که از انتصاب مجددش منع شد در آنجا ماند.
در یک سخنرانی که با سیامین سالگرد بخش EECS برکلی همراه بود، برنده جایزه تورینگ و پروفسور برکلی، ریچارد کارپ اظهار داشت: «سرافکندگی ابدی ماست که ما قادر نبودیم بخش ریاضی را ترغیب کنیم تا او را نگه دارند».
کوک در سال ۱۹۷۰ به عنوان یک پروفسور دستیار به هیات علمی دانشگاه تورنتو، بخشهای علوم کامپیوتر و ریاضیات پیوست که بعدها در آنجا، در سال ۱۹۷۵ به مقام پروفسور و در سال ۱۹۸۵ به مقام پروفسور دانشگاه ارتقا پیدا کرد.
او در سال ۱۹۶۸ ازدواج کرد. دو فرزند دارد که یکی از آنها در حال تحصیل در مقطع دکترا در دانشگاه برکلی، رشته علوم رایانه است. کوک در حال حاضر به همراه همسر خود در تورنتو زندگی میکند. وی ویولن مینوازد و از قایقرانی لذت میبرد.
پژوهش ها [ویرایش]
کوک یکی از پدران نظریه پیچیدگی محاسباتی قلمداد میشود. در طول دوره دکترا، کوک در زمینه پیچیدگی توابع، به ویژه ضرب، کار کرد.
در اواسط دهه ی ۱۹۷۰ کوک تبادل بین زمان و حافظه در عملیات کامپیوتری را مورد بررسی قرار داد. وی قادر بود اثبات کند که هیچ روشی نمیتواند هم از نظر زمان کارا باشد و هم از نظر حافظه. سال بعد، در مقاله سال ۱۹۷۱ خود، «پیچیدگی رویه های اثبات قضیه»، مفاهیم کاهش چندجمله ای زمانی (که با کاهش کوک نیز شناخته شده است) و ان پی کامل بودن را رسمی کرد و وجود یک مساله ان پی کامل را بوسیله نشان دادن اینکه مساله ارضاپذیری بولی ان پی کامل است، اثبات کرد. این قضیه به طور مستقل توسط لئونید لوین در اتحاد جماهیر شوروی ثابت شد و به همین دلیل نام قضیه کوک-لوین را به خود گرفته است.
این مقاله، مشهورترین مساله علوم کامپیوتر، یعنی مسئله برابری پی و انپی را نیز رسمی کرده است. به بیان سادهتر مسئله برابری پی و انپی به دنبال این است که آیا هر مساله ی بهینه سازی که جوابهایش میتوانند به طور موثری برای درستی/بهینگی مورد بررسی قرار گیرند، میتواند به طور بهینهای با یک الگوریتم موثر و کارآمد حل شود یا خیر. با فراوانی اینگونه مسائل بهینه سازی در زندگی روزمره، یک جواب مثبت به این سوال، احتمالا پیامدهای عملی و فلسفی عمیقی را دربر خواهد داشت.
کوک حدس میزند که مسائل بهینهسازی (با حلهایی که به آسانی بررسی شوند) وجود دارند که نمیتوانند با الگوریتمهای موثری حل شوند. به عبارت دیگر پی با ان پی برابر نیست. این حدس تعداد زیادی از تحقیقات در زمینه نظریه پیچیدگی محاسباتی را موجب شده است، که به طور قابل ملاحظهای درک ما را از سختی ذاتی مسائل محاسباتی و اینکه چه چیزی می تواند به طور موثری محاسبه شود بهبود بخشیده است. در حال حاضر، این حدس، باز است و در میان ۷ مساله ی یک میلیون دلاری قرار دارد.
در سال ۱۹۸۲ کوک جایزه معتبر تورینگ را به خاطر سهمش در نظریه پیچیدگی دریافت کرد. تقدیر از وی اینگونه آغاز شد: «برای بالا بردن درک ما از پیچیدگی محاسبات با یک روش مهم و عمیق».
کوک بیش از ۱۰۰ مقاله در زمینههای علوم کامپیوتر نظری و پیچیدگی موازی منتشر کرده است. با این حال، هنوز هم به دلیل رسمی کردن ایده ان پی کامل بودن است که شناخته شده است.
نگارخانه [ویرایش]
جستارهای وابسته [ویرایش]
منابع [ویرایش]
- مشارکتکنندگان ویکیپدیا، «Stephen Cook»، ویکیپدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۰ ژوئن ۲۰۰۹).
- www.BookRegs.com
- www.cs.Toronto.edu
پیوند به بیرون [ویرایش]
|
