ستيفن كوك

الموسوعة الحرة

ستيفن آرثر كوك (مواليد 14 ديسمبر 1939) عالم حاسوب ورياضيات أمريكي-كندي ، قدم إسهامات كبيرة في مجالي نظرية التعقيد وتعقيد البرهان . وهو أستاذ جامعي فخري في جامعة تورنتو ، قسم علوم الحاسوب وقسم الرياضيات .

يُعتبر كوك أحد رواد نظرية التعقيد الحسابي . وقد فاز بجائزة تورينج من جمعية آلات الحوسبة عام 1982 .

سيرة

كوك عام 1968

حصل كوك على درجة البكالوريوس عام 1961 من جامعة ميشيغان ، ودرجتي الماجستير والدكتوراه من جامعة هارفارد ، على التوالي عامي 1962 و1966، من قسم الرياضيات. [ 2 ] انضم إلى قسم الرياضيات بجامعة كاليفورنيا، بيركلي ، عام 1966 كأستاذ مساعد، وبقي هناك حتى عام 1970 حين رُفض تجديد تعيينه. وفي خطاب ألقاه بمناسبة الذكرى الثلاثين لتأسيس قسم الهندسة الكهربائية وعلوم الحاسوب في بيركلي، قال زميله الحائز على جائزة تورينج ، الأستاذ في بيركلي، ريتشارد كارب : "من المؤسف حقًا أننا لم نتمكن من إقناع قسم الرياضيات بمنحه التثبيت الأكاديمي". [ 3 ] انضم كوك إلى هيئة التدريس في قسمي علوم الحاسوب والرياضيات بجامعة تورنتو عام 1970 كأستاذ مشارك، حيث رُقّي إلى أستاذ عام 1975، ثم إلى أستاذ متميز عام 1985.

بحث

خلال دراسته للدكتوراه، ركز كوك على تعقيد الدوال، وخاصةً الضرب. في بحثه الرائد عام ١٩٧١ بعنوان "تعقيد إجراءات إثبات النظريات" [ ٤ ] ، صاغ كوك مفهومي الاختزال متعدد الحدود (المعروف أيضًا باختزال كوك ) واكتمال NP ، وأثبت وجود مسألة NP-كاملة من خلال إظهار أن مسألة إرضاء العبارات المنطقية (المعروفة اختصارًا بـ SAT) هي مسألة NP-كاملة . وقد أثبت ليونيد ليفين هذه النظرية بشكل مستقل في الاتحاد السوفيتي ، ومن هنا جاء اسم نظرية كوك-ليفين . كما صاغ البحث أشهر مسألة في علوم الحاسوب، وهي مسألة P مقابل NP . وبصورة غير رسمية، تسأل مسألة "P مقابل NP" عما إذا كان بالإمكان حل كل مسألة تحسين يمكن التحقق من صحة/مثالية إجاباتها بكفاءة، بشكل أمثل باستخدام خوارزمية فعالة. بالنظر إلى وفرة مشاكل التحسين هذه في الحياة اليومية، فمن المرجح أن يكون للإجابة الإيجابية على سؤال "P مقابل NP" عواقب عملية وفلسفية عميقة.

يفترض كوك وجود مسائل تحسين (ذات حلول يسهل التحقق منها) لا يمكن حلها باستخدام خوارزميات فعالة، أي أن P لا تساوي NP. وقد أثار هذا الافتراض قدراً كبيراً من الأبحاث في نظرية التعقيد الحسابي ، مما حسّن بشكل ملحوظ فهمنا للصعوبة الكامنة في المسائل الحسابية وما يمكن حسابه بكفاءة. ومع ذلك، لا يزال هذا الافتراض مفتوحاً، وهو من بين مسائل جائزة الألفية السبع الشهيرة . [ 5 ] [ 6 ]

في عام 1982، حصل كوك على جائزة تورينج لإسهاماته في نظرية التعقيد. وجاء في حيثيات منحه الجائزة ما يلي:

تقديراً لمساهمته القيّمة في تعزيز فهمنا لتعقيد الحوسبة بشكلٍ جوهري وعميق، أرست ورقته البحثية الرائدة، " تعقيد إجراءات إثبات النظريات"، التي قُدّمت في ندوة ACM SIGACT عام 1971 حول نظرية الحوسبة، أسس نظرية اكتمال NP. وقد شكّل استكشاف حدود وطبيعة فئة مسائل NP-كاملة أحد أهمّ وأنشط الأنشطة البحثية في علوم الحاسوب خلال العقد الماضي.

في بحثه "البراهين البنّاءة الممكنة وحساب القضايا" [ 7 ] المنشور عام 1975، قدّم نظرية المعادلات PV (اختصارًا لـ "قابل للتحقق في زمن متعدد الحدود") لصياغة مفهوم البراهين باستخدام مفاهيم زمن متعدد الحدود فقط. وقدّم إسهامًا هامًا آخر في هذا المجال في بحثه المنشور عام 1979، بالاشتراك مع طالبه روبرت أ. ريكهاو ، بعنوان "الكفاءة النسبية لأنظمة إثبات القضايا" [ 8 ] ، حيث صاغا مفهومي المحاكاة p ونظام إثبات القضايا الفعال ، مما أسس لمجال يُعرف الآن باسم تعقيد إثبات القضايا . وأثبتا أن وجود نظام إثبات يكون فيه لكل صيغة صحيحة برهان قصير يُكافئ NP = coNP . وشارك كوك في تأليف كتاب مع طالبه فونغ ثي نغوين في هذا المجال بعنوان "الأسس المنطقية لتعقيد الإثبات" [ 9 ] .

تتركز مجالات بحثه الرئيسية على نظرية التعقيد وتعقيد البرهان ، مع إسهامات في دلالات لغات البرمجة ، والحوسبة المتوازية ، والذكاء الاصطناعي . وتشمل المجالات الأخرى التي ساهم فيها الحساب المحدود ، والرياضيات العكسية المحدودة ، وتعقيد الدوال من النوع الأعلى ، وتعقيد التحليل ، والحدود الدنيا في أنظمة البرهان الافتراضي .

بعض المساهمات الأخرى

أطلق على فئة التعقيد اسم NC نسبةً إلى نيك بيبنجر . كما سُميت فئة التعقيد SC باسمه. [ 10 ] وقد قدّم أيضًا تعريف فئة التعقيد AC0 وتسلسلها الهرمي AC . [ 11 ]

وفقًا لدون كنوث، استُلهمت خوارزمية KMP من آلات كوك للتعرف على المتواليات المتناظرة المتسلسلة في وقت خطي . [ 12 ]

الجوائز والتكريمات

حصل كوك على زمالة ستيسي التذكارية من مجلس أبحاث العلوم الطبيعية والهندسية الكندي (NSERC) عام 1977، وزمالة كيلام البحثية عام 1982، وجائزة سي آر إم-فيلدز-بي آي إم إس عام 1999. كما فاز بجائزة جون إل. سينج وميدالية برنارد بولزانو من الأكاديمية التشيكية للعلوم (2008)، [ 13 ] وهو زميل في الجمعية الملكية بلندن والجمعية الملكية الكندية . انتُخب كوك عضوًا في الأكاديمية الوطنية للعلوم (الولايات المتحدة) والأكاديمية الأمريكية للفنون والعلوم . وهو عضو مراسل في أكاديمية غوتنغن للعلوم والإنسانيات .

فاز كوك بجائزة تورينج من جمعية آلات الحوسبة (ACM) عام 1982. وكرمته الجمعية بمنحه زمالة عام 2008 لمساهماته الجوهرية في نظرية التعقيد الحسابي . [ 14 ] واختارته جمعية المنطق الرمزي لإلقاء محاضرة غودل عام 1999. [ 15 ]

عيّنته حكومة أونتاريو في وسام أونتاريو عام 2013، وهو أعلى وسام في المقاطعة . [ 16 ] كما فاز بميدالية غيرهارد هيرزبيرغ الذهبية الكندية للعلوم والهندسة عام 2012 ، وهي أعلى وسام يُمنح للعلماء والمهندسين في كندا. [ 17 ] تُمنح ميدالية هيرزبيرغ من قِبل مجلس أبحاث العلوم الطبيعية والهندسية في كندا (NSERC) تقديرًا لـ "التميز المستمر والتأثير الشامل للأبحاث التي تُجرى في كندا في العلوم الطبيعية أو الهندسة". [ 18 ] وقد مُنح لقب ضابط في وسام كندا عام 2015. [ 19 ] [ 20 ]

حصل كوك على جائزة مؤسسة BBVA لآفاق المعرفة لعام 2015 في فئة تكنولوجيا المعلومات والاتصالات "لدوره المهم في تحديد ما يمكن للحواسيب حله بكفاءة وما لا يمكنها حله"، وفقًا لما جاء في بيان لجنة التحكيم. ويضيف البيان أن عمله "كان له أثر بالغ في جميع المجالات التي تُعد فيها العمليات الحسابية المعقدة أساسية".

أشرف كوك على العديد من طلاب الماجستير، وأكمل 36 طالب دكتوراه درجاتهم تحت إشرافه. [ 1 ]

الحياة الشخصية

يعيش كوك مع زوجته في تورنتو . ولديهما ولدان، أحدهما هو البحار الأولمبي غوردون كوك . [ 21 ]

انظر أيضاً

مراجع

  1. 1 2 ستيفن كوك في مشروع علم الأنساب الرياضي
  2. ↑ كابرون، بروس. "ستيفن آرثر كوك" . جائزة إيه إم تورينج . تم الاطلاع عليه بتاريخ 23 أكتوبر 2018 .
  3. ↑ ريتشارد كارب (2003). "نظرة شخصية على علوم الحاسوب في بيركلي" . جامعة كاليفورنيا، بيركلي . تم الاطلاع عليه بتاريخ 12 فبراير 2023 .
  4. ↑ ستيفن كوك (1971)، تعقيد إجراءات إثبات النظريات (ملف PDF) – عبر جامعة تورنتو
    ستيفن أ. كوك (2009) [1971]. "تعقيد إجراءات إثبات النظريات" . تم الاطلاع عليه بتاريخ 12 فبراير 2023 .
  5. ↑ مسألة P مقابل NP مؤرشفة في 14 أكتوبر 2013 على موقع Wayback Machine ، صفحة مسائل جائزة الألفية - معهد كلاي للرياضيات
  6. ↑ P مقابل NP مؤرشف في 27 سبتمبر 2007، في Wayback Machine، الوصف الرسمي للمسألة بقلم ستيفن كوك على موقع Millennium Prize Problems
  7. ↑ كوك، ستيفن أ. (5 مايو 1975). "البراهين البنائية الممكنة وحساب القضايا (نسخة أولية)" . وقائع الندوة السنوية السابعة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '75 . نيويورك: جمعية آلات الحوسبة. الصفحات 83-97 . doi : 10.1145/800116.803756 . ISBN  978-1-4503-7419-4. S2CID 13309619 . 
  8. ↑ كوك، ستيفن أ.؛ ريكهاو، روبرت أ. (1979). "الكفاءة النسبية لأنظمة إثبات القضايا". مجلة المنطق الرمزي . 44 (1 ) : 36-50 . doi : 10.2307/2273702 . ISSN 0022-4812 . JSTOR 2273702. S2CID 2187041 .   
  9. ↑ الصفحة الرسمية لـ "الأسس المنطقية لتعقيد البرهان"
  10. ↑ ""فصل ستيف": أصل SC" . علوم الحاسوب النظرية - ستاك إكستشينج .
  11. ↑ "من الذي قدم فئة التعقيد AC؟" . علوم الحاسوب النظرية – ستاك إكستشينج .
  12. ↑ "عشرون سؤالاً لدونالد كنوث" .
  13. ↑ «مُنِحَ ميداليات برنارد بولزانو الفخرية للاستحقاق في العلوم الرياضية» . ميداليات الأكاديمية التشيكية للعلوم . تم الاطلاع عليه بتاريخ 13 أبريل 2024 .
  14. ↑ رابطة آلات الحوسبة. "ستيفن أ. كوك" . awards.acm.org . تم الاطلاع عليه بتاريخ 12 فبراير 2023 .
  15. ↑ "محاضرو غودل - رابطة المنطق الرمزي" . تم الاطلاع عليه بتاريخ 8 نوفمبر 2021 .
  16. ↑ "تعيين 25 شخصًا في أعلى وسام شرف في أونتاريو" . وزارة المواطنة والهجرة .
  17. ↑ إميلي تشونغ (27 فبراير 2013). "عالمة حاسوب تفوز بأرفع جائزة علمية في كندا" . cbc.ca. تاريخ الاسترجاع: 27 فبراير 2013 .
  18. ↑ "الفائز الحالي – 2012 – ستيفن كوك" . 28 يونيو 2016.
  19. ↑ "SaltWire | Halifax" . www.saltwire.com . تم الاطلاع عليه بتاريخ 12 فبراير 2023 .
  20. ↑ «وسام كندا: أعلى الأوسمة تُمنح لرائدة الخلايا الجذعية في جامعة تورنتو، جانيت روسانت، وقائد السياسات العامة، بوب راي» . جامعة تورنتو . 2 يوليو 2015. تاريخ الاطلاع: 2 مارس 2025 .
  21. ↑ "ستيفن أ. كوك - الصفحة الرئيسية" .