ريتشارد إم. كارب

ريتشارد مانينغ كارب (مواليد 3 يناير 1935) هو عالم حاسوب أمريكي ونظري في الحوسبة في جامعة كاليفورنيا، بيركلي . اشتهر بأبحاثه في نظرية الخوارزميات ، والتي نال عنها جائزة تورينج من جمعية آلات الحوسبة عام 1985 ، وميدالية بنجامين فرانكلين في علوم الحاسوب والإدراك عام 2004 ، وجائزة كيوتو عام 2008. ^{[ 2 ]}

تم انتخاب كارب عضواً في الأكاديمية الوطنية للهندسة (1992) لمساهماته الكبيرة في نظرية وتطبيق اكتمال NP، وبناء خوارزميات توافقية فعالة، وتطبيق الأساليب الاحتمالية في علوم الحاسوب.

وُلد كارب لوالديه أبراهام وروز كارب في بوسطن، ماساتشوستس ، ولديه ثلاثة أشقاء أصغر منه: روبرت، وديفيد ، وكارولين. كانت عائلته يهودية ، ^{[ 3 ]} ونشأ في شقة صغيرة، في حي دورشستر الذي كان يغلب عليه الطابع اليهودي آنذاك في بوسطن.

كان والداه من خريجي جامعة هارفارد (حصلت والدته على شهادتها من هارفارد في سن 57 بعد دراسة مسائية)، بينما كان والده يطمح لدراسة الطب بعد هارفارد، لكنه أصبح مدرسًا للرياضيات لعدم قدرته على تحمل تكاليف دراسة الطب. ^{[ 3 ]} التحق بجامعة هارفارد ، حيث حصل على درجة البكالوريوس عام 1955، ودرجة الماجستير عام 1956، ودرجة الدكتوراه في الرياضيات التطبيقية عام 1959. بدأ العمل في مركز توماس ج. واتسون للأبحاث التابع لشركة آي بي إم .

في عام ١٩٦٨، أصبح كارب أستاذًا لعلوم الحاسوب والرياضيات وبحوث العمليات في جامعة كاليفورنيا، بيركلي . وكان أول نائب رئيس لقسم علوم الحاسوب ضمن قسم الهندسة الكهربائية وعلوم الحاسوب. ^{[ ٤ ]} وباستثناء فترة أربع سنوات قضاها أستاذًا في جامعة واشنطن ، فقد بقي في بيركلي. ومن عام ١٩٨٨ إلى عام ١٩٩٥، ومن عام ١٩٩٩ حتى الآن، عمل أيضًا باحثًا علميًا في المعهد الدولي لعلوم الحاسوب في بيركلي، حيث يرأس حاليًا مجموعة الخوارزميات.

حصل ريتشارد كارب على الميدالية الوطنية للعلوم ، وجائزة هارفي من معهد التخنيون ، وميدالية بنجامين فرانكلين لعام 2004 في علوم الحاسوب والإدراك، وذلك لإسهاماته في مجال التعقيد الحسابي . وفي عام 1994، انتُخب زميلًا في جمعية آلات الحوسبة . كما انتُخب زميلًا في معهد بحوث العمليات وعلوم الإدارة لعام 2002. ^{[ 5 ]} وهو حاصل على العديد من الشهادات الفخرية، وعضو في الأكاديمية الوطنية للعلوم في الولايات المتحدة ، ^{[ 6 ]} والأكاديمية الأمريكية للفنون والعلوم ، ^{[ 7 ]} والجمعية الفلسفية الأمريكية . ^{[ 8 ]}

في عام 2012، أصبح كارب المدير المؤسس لمعهد سيمونز لنظرية الحوسبة في جامعة كاليفورنيا، بيركلي . ^{[ 9 ]}

حقق كارب العديد من الاكتشافات المهمة في علوم الحاسوب، والخوارزميات التوافقية ، وبحوث العمليات . وتشمل اهتماماته البحثية الحالية الرئيسية المعلوماتية الحيوية .

في عام 1962 شارك في تطوير خوارزمية هيلد-كارب مع مايكل هيلد ، وهي خوارزمية دقيقة ذات وقت أسي لحل مشكلة البائع المتجول .

في عام 1971 شارك في تطوير خوارزمية إدموندز-كارب مع جاك إدموندز لحل مشكلة التدفق الأقصى على الشبكات، وفي عام 1972 نشر ورقة بحثية رائدة في نظرية التعقيد بعنوان "الاختزال بين المسائل التوافقية"، والتي أثبت فيها أن 21 مسألة هي مسائل كاملة من فئة NP . ^{[ 10 ]}

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

في عام 1980، أثبت كارب، بالاشتراك مع ريتشارد جيه ليبتون ، نظرية كارب-ليبتون (التي تثبت أنه إذا كان من الممكن حل SAT بواسطة الدوائر المنطقية ذات عدد متعدد الحدود من البوابات المنطقية ، فإن التسلسل الهرمي متعدد الحدود ينهار إلى مستواه الثاني).

في عام 1987 شارك في تطوير خوارزمية البحث عن السلاسل النصية رابين-كارب مع مايكل أو . رابين .

• مقابلة/سيرة ذاتية لريتشارد كارب في مجلة ACM Crossroads
• الصفحة الرئيسية لكارب في بيركلي
• سيرة ريتشارد كارب من معهد بحوث العمليات وعلوم الإدارة