تاریخچه ی:
استفن کوک
تفاوت با نگارش: 1
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| | ^@#16: | | ^@#16: |
| | !استفن کوک | | !استفن کوک |
| | __ایده این که الگوریتمی برای حل یک مساله وجود ندارد، برای من بسیار جالب بود. «استفن کوک»__ | | __ایده این که الگوریتمی برای حل یک مساله وجود ندارد، برای من بسیار جالب بود. «استفن کوک»__ |
| | استفن کوک: منطق و سنت غربی | | استفن کوک: منطق و سنت غربی |
| - | استفن کوک در سال 1939 در شهر بوفالو در ایالت نیویورک به دنیا آمد. پدر او شیمیدان بود و در دانشگاه بوفالو تدرسی می‌کرد و همواره در آرزوی زندگی در بیرون شهر بود. هنگامی که استفن ده ساله بود. خانواده‌اش به مزرعه‌ای در کلارنس نیویورک نقل مکان کردند. آنها زمین مزرعه را به یک کشاورز اجاره دادند و یک گاو و چند حیوان دیگر را برای خود نگاه داشتند. مسئوولیت دوشیدن شیر گاو بر عهده استفن بود. او می‌گوید: |
+ |
{picture=img/daneshnameh_up/7/7f/compics030.jpg} |
{*استفن کوک در سال 1939 در شهر بوفالو در ایالت نیویورک به دنیا آمد. پدر او شیمیدان بود و در دانشگاه بوفالو تدرسی می‌کرد و همواره در آرزوی زندگی در بیرون شهر بود. هنگامی که استفن ده ساله بود. خانواده‌اش به مزرعه‌ای در کلارنس نیویورک نقل مکان کردند. آنها زمین مزرعه را به یک کشاورز اجاره دادند و یک گاو و چند حیوان دیگر را برای خود نگاه داشتند. مسئوولیت دوشیدن شیر گاو بر عهده استفن بود. او می‌گوید: |
| | «من علاقه معمولی به شطرنج و برخی بازیهای دیگر داشتم. ریاضیاتم در مدرسه خوب بود ولی مدرسه ما یک مدرسه کاملاً معمولی و متوسط بود. من هرگز فکر نمی‌کردم که روزی ریاضیدان شوم. عموی مادرم، استاد ریاضیات در دانشگاه ویچیتا بود و تا جایی که من می دانم که او تنها ریاضیدان در بین پشینیان من بود.» | | «من علاقه معمولی به شطرنج و برخی بازیهای دیگر داشتم. ریاضیاتم در مدرسه خوب بود ولی مدرسه ما یک مدرسه کاملاً معمولی و متوسط بود. من هرگز فکر نمی‌کردم که روزی ریاضیدان شوم. عموی مادرم، استاد ریاضیات در دانشگاه ویچیتا بود و تا جایی که من می دانم که او تنها ریاضیدان در بین پشینیان من بود.» |
| | ویلسن گریت‌بچ، مخترع دستگاه ضربان‌ساز قلب نیز در کلارنس نیویورک زندگی می‌کرد. او الهام بخش کوک برای ادامه تحصیل در رشته مهندسی برق شد: | | ویلسن گریت‌بچ، مخترع دستگاه ضربان‌ساز قلب نیز در کلارنس نیویورک زندگی می‌کرد. او الهام بخش کوک برای ادامه تحصیل در رشته مهندسی برق شد: |
| | «من در تابستان برای او کار می‌کردم. او در اتاق زیر شیروانی انبارش یک مغازه کوچک درست کرده بود. دهه پنجاه بود و ترانزیستورها تازه به بازار آمده بودند و او سرگرم آزمایش مدارهای ترانزیستوری بود. من به او در لحیم کردن مدارها کمک می‌کردم و این کار برایم بسیار جالب بود. | | «من در تابستان برای او کار می‌کردم. او در اتاق زیر شیروانی انبارش یک مغازه کوچک درست کرده بود. دهه پنجاه بود و ترانزیستورها تازه به بازار آمده بودند و او سرگرم آزمایش مدارهای ترانزیستوری بود. من به او در لحیم کردن مدارها کمک می‌کردم و این کار برایم بسیار جالب بود. |
| | هنگامی که تحصیلات عالی خود را دانشگاه میشیگان آغاز کردم، نام رشته تحصیلی‌ام مهندسی علوم بود ولی علاقه شخصی‌ام به مهندسی برق بود. در سال اول دانشگاه (1957)، یک واحد برنامه‌نویسی با برنارد گالر برداشتم. | | هنگامی که تحصیلات عالی خود را دانشگاه میشیگان آغاز کردم، نام رشته تحصیلی‌ام مهندسی علوم بود ولی علاقه شخصی‌ام به مهندسی برق بود. در سال اول دانشگاه (1957)، یک واحد برنامه‌نویسی با برنارد گالر برداشتم. |
| | کوک و یکی از دوستانش برنامه ای برای آزمایش فرضیه معروف گلدباخ که هر عدد زوج بزرگتر از 3، حاصل جمع دو عدد اول است، نوشتند. تا جایی که آنها توانستند محاسبه کنند فرضیه برقرار بود. (این فرضیه همچنان باز باقی مانده است، زیرا اثبات خواص کلی و فراگیر در مورد اعداد اول بسیار دشوار است. از سوی دیگر، هنوز کسی هم نتوانسته است مثال نقضی ارائه کند.) | | کوک و یکی از دوستانش برنامه ای برای آزمایش فرضیه معروف گلدباخ که هر عدد زوج بزرگتر از 3، حاصل جمع دو عدد اول است، نوشتند. تا جایی که آنها توانستند محاسبه کنند فرضیه برقرار بود. (این فرضیه همچنان باز باقی مانده است، زیرا اثبات خواص کلی و فراگیر در مورد اعداد اول بسیار دشوار است. از سوی دیگر، هنوز کسی هم نتوانسته است مثال نقضی ارائه کند.) |
| | کوک در دوره کارشناسی تا حدودی با نظریه محاسبات و مسائل حل نشدنی نظیر مساله توقف تورینگ (که در بخش مربوط به رابین مورد بحث قرارگرفت) آشنا شد. او سپس به دانشگاه هاروارد رفت و دوره دکتری خود را در رشته ریاضیات آغاز کرد و قصد داشت که در زمینه جبر به مطالعه بپردازد. اما اتفاقاً تاثیرگذارترین استاد او یعنی هائووانگ از بخش علوم کاربردی بود. وانگ که خود در زمینه منطق ریاضی و فلسفه تحصیل کرده بود، بر روی اثبات خودکار قضایا، یعنی به دست آوردن اثبات توسط رایانه، کار می‌کرد. زمینه تاثیرگذار دیگر، نظریه پیچیدگی بود که به تازگی توسط مایکل رابین دارای بنیاد ریاضی گشته بود. بسیاری از افراد موثر و پیشتاز در نظریه پیچیدگی نظیر رابین، هارتمانیس، و استرنز در دانشگاههای مختلف در مورد این نظریه سخنرانی می‌کردند و درصدد جلب همکاری دانشجویان دوره دکتری نظیر کوک بودند: | | کوک در دوره کارشناسی تا حدودی با نظریه محاسبات و مسائل حل نشدنی نظیر مساله توقف تورینگ (که در بخش مربوط به رابین مورد بحث قرارگرفت) آشنا شد. او سپس به دانشگاه هاروارد رفت و دوره دکتری خود را در رشته ریاضیات آغاز کرد و قصد داشت که در زمینه جبر به مطالعه بپردازد. اما اتفاقاً تاثیرگذارترین استاد او یعنی هائووانگ از بخش علوم کاربردی بود. وانگ که خود در زمینه منطق ریاضی و فلسفه تحصیل کرده بود، بر روی اثبات خودکار قضایا، یعنی به دست آوردن اثبات توسط رایانه، کار می‌کرد. زمینه تاثیرگذار دیگر، نظریه پیچیدگی بود که به تازگی توسط مایکل رابین دارای بنیاد ریاضی گشته بود. بسیاری از افراد موثر و پیشتاز در نظریه پیچیدگی نظیر رابین، هارتمانیس، و استرنز در دانشگاههای مختلف در مورد این نظریه سخنرانی می‌کردند و درصدد جلب همکاری دانشجویان دوره دکتری نظیر کوک بودند: |
| | «این سوال به نظر خیلی طبیعی و در عین حال اساسی می‌آمد. مسائلی وجود داشتند که از نظر اصولی توسط الگوریتمها قابل حل بودند ولی از نظر عملی اینچنین نبودند و دستیابی به راه حل آنها، زمان فوق‌العاده زیادی می‌طلبید. بنابراین، پرسش در مورد پیچیدگی ذاتی مسائل، بسیار طبیعی بود. | | «این سوال به نظر خیلی طبیعی و در عین حال اساسی می‌آمد. مسائلی وجود داشتند که از نظر اصولی توسط الگوریتمها قابل حل بودند ولی از نظر عملی اینچنین نبودند و دستیابی به راه حل آنها، زمان فوق‌العاده زیادی می‌طلبید. بنابراین، پرسش در مورد پیچیدگی ذاتی مسائل، بسیار طبیعی بود. |
| | پیش از ساخته شدن رایانه‌ها، الگوریتمها فقط با دست قابل اجرا بودند. این فرآیند به قدری خسته کننده و وقتگیر بود که سوال در مورد پیچیدگی محاسباتی، زیاد جالب نبود. ولی پس از به وجود آمدن این ماشینهای قدرتمند که به عنوان ابزار موثری در اختیار پژوهشگران قرار داشتند و قادر به انجام هزاران عمل در ثانیه بودند، بسیار طبیعی بود که پرسیده شود چه نوع مسائلی واقعاً قابل حل هستند.» | | پیش از ساخته شدن رایانه‌ها، الگوریتمها فقط با دست قابل اجرا بودند. این فرآیند به قدری خسته کننده و وقتگیر بود که سوال در مورد پیچیدگی محاسباتی، زیاد جالب نبود. ولی پس از به وجود آمدن این ماشینهای قدرتمند که به عنوان ابزار موثری در اختیار پژوهشگران قرار داشتند و قادر به انجام هزاران عمل در ثانیه بودند، بسیار طبیعی بود که پرسیده شود چه نوع مسائلی واقعاً قابل حل هستند.» |
| | هائووانگ، استاد راهنمای کوک، دیدگاه منطقی جدیدی را در این زمینه مطرح ساخت: | | هائووانگ، استاد راهنمای کوک، دیدگاه منطقی جدیدی را در این زمینه مطرح ساخت: |
| | «من کاملاً در جیان ایده‌های وانگ و روشهای او قرار داشتم. نتایجی که من بعداً در مورد مسائل NP کامل به دست آوردم مشابه نتایج او بود. تورینگ و وانگ درباره حساب محمولات صحبت می‌کردند و من درباره حساب گزاره‌ها.» | | «من کاملاً در جیان ایده‌های وانگ و روشهای او قرار داشتم. نتایجی که من بعداً در مورد مسائل NP کامل به دست آوردم مشابه نتایج او بود. تورینگ و وانگ درباره حساب محمولات صحبت می‌کردند و من درباره حساب گزاره‌ها.» |
| | حساب محمولات و حساب گزاره‌ها دو زبان مختلف هستند که در منطق ریاضی به کار می‌روند. وانگ پیچیدگی «مساله ارضاءپذیری» را در حساب محمولات مورد مطالعه قرار داد. کوک بعداً به همین مساله در حساب گزاره‌ها علاقه‌مند شد. برای درک تفاوت بین آنها، مثال زیر را در نظر بگیرید. | | حساب محمولات و حساب گزاره‌ها دو زبان مختلف هستند که در منطق ریاضی به کار می‌روند. وانگ پیچیدگی «مساله ارضاءپذیری» را در حساب محمولات مورد مطالعه قرار داد. کوک بعداً به همین مساله در حساب گزاره‌ها علاقه‌مند شد. برای درک تفاوت بین آنها، مثال زیر را در نظر بگیرید. |
| - | حساب محمولات، جملاتی درباره گروههایی از عناصر منفرد می‌سازد. برای نمونه، جمله "All Olympic Athlete(x) implies fit(x)" (تمام قهرمانان المپیک سالم هستند) به این صورت نوشته می‌شود: |
+ | حساب محمولات، جملاتی درباره گروههایی از عناصر منفرد می‌سازد. برای نمونه، جمله "All Olympic Athlete(x) implies fit(x)" (تمام قهرمانان المپیک سالم هستند) به این صورت نوشته می‌شود:*} |
| | @@for all x Olympic Athlete(x) implies fit(x)@@ | | @@for all x Olympic Athlete(x) implies fit(x)@@ |
| - | حساب محمولات به ما اجازه می‌دهد که یک عنصر خاص را جایگزین x کنیم. برای مثال، اگر بدانیم که آشیل قهرمان المپیک است، یا به عبارت Olympic athlete (Achilles) درست است، آنگاه فرمول بالا ما را به این نتیجه می‌رساند که fit(A chilles) هم درست است.
اما حساب گزاره‌ها که مورد مطالعه کوک قرار گرفت، زبان ساده‌ترین است که تنها اجازه می‌دهد ادعاهایی درباره عناصر منفرد بکنیم. مانند: "Tweety is a bird" (گنجشک یک پرنده است). قواعد حساب گزاره‌ها اجازه می‌دهد تا از روی گزاره‌های قبلی، گزاره‌های جدیدی را نتیجه‌گیری کنیم. برای مثال، اگر گزاره‌های "Eiether Tweety is a bird or Luke is a gazelle" و "Luke is not a gazelle" هر دو درست باشند، می‌توان نتیجه گرفت که گزاره "Tweety is bird" درست است. |
+ |
{*حساب محمولات به ما اجازه می‌دهد که یک عنصر خاص را جایگزین x کنیم. برای مثال، اگر بدانیم که آشیل قهرمان المپیک است، یا به عبارت Olympic athlete (Achilles) درست است، آنگاه فرمول بالا ما را به این نتیجه می‌رساند که fit(A chilles) هم درست است.
اما حساب گزاره‌ها که مورد مطالعه کوک قرار گرفت، زبان ساده‌ترین است که تنها اجازه می‌دهد ادعاهایی درباره عناصر منفرد بکنیم. مانند: "Tweety is a bird" (گنجشک یک پرنده است). قواعد حساب گزاره‌ها اجازه می‌دهد تا از روی گزاره‌های قبلی، گزاره‌های جدیدی را نتیجه‌گیری کنیم. برای مثال، اگر گزاره‌های "Eiether Tweety is a bird or Luke is a gazelle" و "Luke is not a gazelle" هر دو درست باشند، می‌توان نتیجه گرفت که گزاره "Tweety is bird" درست است.*} |
| | --- | | --- |
| | !تعریف مسائل NP کامل | | !تعریف مسائل NP کامل |
| - | کوک پس از پایان رساندن دوره دکتری در هاروارد، مدت کوتاهی را در دانشگاه برکلی در کالیفرنیا گذراند و سپس راهی دانشگاه تورنتو در کانادا شد. |
+ |
{*کوک پس از پایان رساندن دوره دکتری در هاروارد، مدت کوتاهی را در دانشگاه برکلی در کالیفرنیا گذراند و سپس راهی دانشگاه تورنتو در کانادا شد. |
| | در سال 1971، ایده‌های او درباره مساله ارضاءپذیری در مقاله‌ای که به سومین همایش سالانه انجمن ماشینهای محاسب (ACM) درباره نظریه محاسبات فرستاد منتشر شد. او در این مقاله، مسائلی را مورد بحث قرار داد که برای آنها یک راه‌حل ممکن (که او آن را «نامزد» نامیده بود)، قابل ارزیابی در زمان چند جمله‌ای بود. از آنجا که همیشه تصمیم‌گیری در مورد این که کدام نامزد برای آزمایش مناسب است امکانپذیر نیست، برنامه باید به طور حدسی یک راه حل را برگزیند. به این دلیل، کوک این مسائل را مسائل از رتبه چندجمله‌ای غیرقطعی یا NP نامید. بخش مربوط به حدس زدن، غیرقطعی است و بخش مربوط به آزمودن، چندجمله‌ای. | | در سال 1971، ایده‌های او درباره مساله ارضاءپذیری در مقاله‌ای که به سومین همایش سالانه انجمن ماشینهای محاسب (ACM) درباره نظریه محاسبات فرستاد منتشر شد. او در این مقاله، مسائلی را مورد بحث قرار داد که برای آنها یک راه‌حل ممکن (که او آن را «نامزد» نامیده بود)، قابل ارزیابی در زمان چند جمله‌ای بود. از آنجا که همیشه تصمیم‌گیری در مورد این که کدام نامزد برای آزمایش مناسب است امکانپذیر نیست، برنامه باید به طور حدسی یک راه حل را برگزیند. به این دلیل، کوک این مسائل را مسائل از رتبه چندجمله‌ای غیرقطعی یا NP نامید. بخش مربوط به حدس زدن، غیرقطعی است و بخش مربوط به آزمودن، چندجمله‌ای. |
| | مساله فروشنده دوره‌گرد و مساله ارضاءپذیری هر دو این خاصیت را دارند زیرا به سرعت می‌توان بررسی کرد که یک مسیر سفر که نامزد شده است با بودجه فروشنده تناسب دارد یا خیر و یا یک نحوه تخصیص مقادیر که نامزد شده، مقدار عبارت را درست می‌گرداند یا نه. | | مساله فروشنده دوره‌گرد و مساله ارضاءپذیری هر دو این خاصیت را دارند زیرا به سرعت می‌توان بررسی کرد که یک مسیر سفر که نامزد شده است با بودجه فروشنده تناسب دارد یا خیر و یا یک نحوه تخصیص مقادیر که نامزد شده، مقدار عبارت را درست می‌گرداند یا نه. |
| | سوال بزرگی که اکنون پیش می‌آید این است که یافتن یک نامزد مناسب، در زمان چندجمله‌ای امکانپذیر است یا نه. | | سوال بزرگی که اکنون پیش می‌آید این است که یافتن یک نامزد مناسب، در زمان چندجمله‌ای امکانپذیر است یا نه. |
| | کوک نشان داد که مساله ارضاءپذیری یکی از مشکلترین مسائل در بین مسائل NP است. به ویژه، او نشان داد که اگر مساله ارضاءپذیری دارای الگوریتمی از رتبه چندجمله‌ای باشد، تمام مسائل NP نیز چنین الگوریتمی خواهند داشت. به این خاطر به مساله ارضاءپذیری NP کامل گفته می‌شود. بنابراین، نشان دادن این که یک مساله NP کاملا ست به این معنی است که حل کردن آن بسیار دشوار می‌باشد. و هر گاه کسی بتواند الگوریتم موثری برای یکی از مسائل NP کامل بیاید، می‌تواند آن را برای تمام این گونه مسائل به کار بندد. | | کوک نشان داد که مساله ارضاءپذیری یکی از مشکلترین مسائل در بین مسائل NP است. به ویژه، او نشان داد که اگر مساله ارضاءپذیری دارای الگوریتمی از رتبه چندجمله‌ای باشد، تمام مسائل NP نیز چنین الگوریتمی خواهند داشت. به این خاطر به مساله ارضاءپذیری NP کامل گفته می‌شود. بنابراین، نشان دادن این که یک مساله NP کاملا ست به این معنی است که حل کردن آن بسیار دشوار می‌باشد. و هر گاه کسی بتواند الگوریتم موثری برای یکی از مسائل NP کامل بیاید، می‌تواند آن را برای تمام این گونه مسائل به کار بندد. |
| - | کوتاه‌زمانی پس از انتشار مقاله کوک، ریچارد کارپ از دانشگاه برکلی نشان داد که 31 مساله دیگر، از جمله مساله‌ای بسیار نزدیک و مرتبط به مساله فروشنده دوره‌گرد، نیز NP کامل هستند. او برای این منظور از روشی به نام کاهش‌پذیری استفاده کرد: اگر هر کدام از این مسائل را بتوان با الگوریتم سریعی حل کرد، آنگاه مسأله ارضاءپذیری را نیز می‌توان به سرعت حل کرد. در نتیجه، این مسائل حداقل به همان سختی مساله ارضاءپذیری هستند. البته متاسفانه باید اذعان کرد که هیچکدام از این نتایج ثابت نمی‌کند که این مسائل واقعاً پیچیده هستند! |
+ | کوتاه‌زمانی پس از انتشار مقاله کوک، ریچارد کارپ از دانشگاه برکلی نشان داد که 31 مساله دیگر، از جمله مساله‌ای بسیار نزدیک و مرتبط به مساله فروشنده دوره‌گرد، نیز NP کامل هستند. او برای این منظور از روشی به نام کاهش‌پذیری استفاده کرد: اگر هر کدام از این مسائل را بتوان با الگوریتم سریعی حل کرد، آنگاه مسأله ارضاءپذیری را نیز می‌توان به سرعت حل کرد. در نتیجه، این مسائل حداقل به همان سختی مساله ارضاءپذیری هستند. البته متاسفانه باید اذعان کرد که هیچکدام از این نتایج ثابت نمی‌کند که این مسائل واقعاً پیچیده هستند!*}
---
!پیوندهای خارجی
*[http://en.wikipedia.org/wiki/Stephen_Cook ]
---
!همچنین ببینید
*(( فردریک بروکز))
*((ادوارد فایگن بام))
*((لئونید لوین)) |
| | #@^ | | #@^ |
