جاك إدموندز

جاك ر. إدموندز (مواليد 5 أبريل 1934) عالم حاسوب ورياضيات أمريكي المولد والتعليم، عاش وعمل في كندا معظم حياته. قدم إسهامات جوهرية في مجالات التحسين التوافقي ، والتوافقية متعددة السطوح ، والرياضيات المتقطعة ، ونظرية الحوسبة. حاز على جائزة جون فون نيومان النظرية عام 1985 .

التحق إدموندز بمدرسة ماكينلي الثانوية للتكنولوجيا ، وتخرج منها عام 1952؛ ^{[ 1 ]} وقد تحدث عن تأثير هذه المدرسة على مسيرته المهنية (على سبيل المثال، خلال حفل انضمامه إلى معرض المعهد الوطني للمعايير والتكنولوجيا عام 2014 ^{[ 2 ] [ 3 ] [ 4 ]} ). درس إدموندز في جامعة ديوك قبل أن يُكمل دراسته الجامعية في جامعة جورج واشنطن عام 1957. ثم حصل على درجة الماجستير عام 1960 من جامعة ميريلاند تحت إشراف بروس ل. راينهارت، برسالةٍ حول مشكلة تضمين الرسوم البيانية في الأسطح. ^{[ 5 ] [ 6 ]} عمل إدموندز في المعهد الوطني للمعايير والتكنولوجيا (الذي كان يُعرف آنذاك بالمكتب الوطني للمعايير) من عام 1959 إلى عام 1969، وكان عضوًا مؤسسًا في قسم بحوث العمليات الذي أنشأه آلان غولدمان حديثًا عام 1961. وقد أثبت غولدمان تأثيره الحاسم من خلال تمكينه إدموندز من العمل في ورشة عمل برعاية مؤسسة راند في سانتا مونيكا، كاليفورنيا. هنا قدم إدموندز لأول مرة نتائجه حول تعريف فئة من الخوارزميات التي يمكن تشغيلها بكفاءة أكبر. لم يكن معظم علماء التوافقية، في ذلك الوقت، يركزون على الخوارزميات. ومع ذلك، انجذب إدموندز إليها، وكانت هذه الدراسات الأولية بمثابة تطورات رئيسية لأعماله اللاحقة في مجال المصفوفات والتحسين. أمضى السنوات من 1961 إلى 1965 في دراسة موضوع NP مقابل P، وفي عام 1966 وضع الفرضيتين NP ≠ P و NP ∩ coNP = P.

كانت ورقة إدموندز البحثية لعام 1965 بعنوان "المسارات والأشجار والزهور" ورقةً رائدةً في اقتراح إمكانية وضع نظرية رياضية للخوارزميات التوافقية الفعّالة. ومن أوائل إسهاماته البارزة خوارزمية الزهرة لإنشاء المطابقات القصوى على الرسوم البيانية، والتي اكتُشفت عام 1961 ^{[ 7 ]} ونُشرت عام 1965 ^{[ 8 ].} وكانت هذه أول خوارزمية تعمل في زمن متعدد الحدود لإيجاد المطابقات القصوى في الرسوم البيانية. وشكّل تعميمها على الرسوم البيانية الموزونة ^{[ 9 ]} نقلةً نوعيةً في استخدام مفاهيم البرمجة الخطية في التحسين التوافقي . وقد أكّدت هذه الخوارزمية على أهمية وجود براهين، أو "أدلة"، تُثبت أن الإجابة على سؤال ما هي "نعم"، ووجود براهين، أو "أدلة"، تُثبت أن الإجابة على سؤال ما هي "لا". وفي ورقة خوارزمية الزهرة هذه، يُعرّف إدموندز أيضًا المسائل الممكنة بأنها تلك التي يُمكن حلّها في زمن متعدد الحدود. هذا أحد أصول أطروحة كوبام-إدموندز . ^{[ 10 ]}

كان من أبرز إنجازات أطروحة كوبام-إدموندز تعريف مفهوم الوقت متعدد الحدود الذي يميز الفرق بين الخوارزمية العملية والخوارزمية غير العملية (أو بعبارة أخرى، المسألة القابلة للحل أو المسألة غير القابلة للحل). تُسمى المسائل القابلة للحل في وقت متعدد الحدود اليوم فئة التعقيد PTIME ، أو ببساطة P.

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

من أبرز أعمال إدموندز الأخرى مجال الماترويدات . فقد وجد وصفًا متعدد الأوجه لجميع الأشجار الممتدة في الرسم البياني، وبشكل أعم، لجميع المجموعات المستقلة في الماترويد. ^{[ 11 ]} وانطلاقًا من هذا، وكتطبيق مبتكر للبرمجة الخطية على الرياضيات المتقطعة، أثبت نظرية تقاطع الماترويدات ، وهي نظرية عامة جدًا في مجال التوافقية للحد الأدنى والحد الأقصى ^{[ 12 ] [ 13 ]} والتي، بتعبير حديث، أظهرت أن مشكلة تقاطع الماترويدات تقع ضمن كل من NP و co-NP . يشتهر إدموندز بنظرياته حول خوارزميات التفرع ذات الوزن الأقصى ^{[ 14 ]} وتفرعات التعبئة غير المتداخلة الحواف ^{[ 15 ]} وعمله مع ريتشارد كارب على خوارزميات التدفق الأسرع . تصف نظرية إدموندز-غالاي للتحليل الرسوم البيانية المحدودة من منظور المطابقات. قدّم مفهوم البوليماترويدات ^{[ 12 ]} ، والتدفقات شبه المعيارية مع ريتشارد جايلز ^{[ 16 ]} ، ومصطلحي التشويش والحجب في دراسة المخططات الفائقة ^{[ 7 ]} . ومن المواضيع المتكررة في أعماله ^{[ 17 ]} البحث عن خوارزميات يكون تعقيدها الزمني محدودًا بحدود متعددة الحدود بحجم مدخلاتها وتعقيدها البتّي ^{[ 7 ] .}

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

في الفترة من عام 1991 إلى عام 1993، دخل في نزاع ("قضية إدموندز") مع جامعة واترلو، ^{[ 18 ] [ 19 ]} حيث ادعت الجامعة أن الرسالة المقدمة تُعدّ بمثابة استقالة، وهو ما نفاه إدموندز. ^{[ 20 ]} تم حل النزاع في عام 1993، وعاد إلى الجامعة.

تقاعد إدموندز من جامعة واترلو عام 1999.

حصل إدموندز على جائزة جون فون نيومان النظرية عام 1985 .

في عام 2001، حظيت ورقته البحثية بعنوان "المسارات والأشجار والزهور" بتكريم المعهد الوطني للمعايير والتكنولوجيا كمنشور متميز في طبعته الاحتفالية من كتاب "قرن من التميز في معايير القياس والتكنولوجيا".

تم انتخابه لعضوية دفعة 2002 من زملاء معهد بحوث العمليات وعلوم الإدارة . ^{[ 21 ]}

في عام 2006، منحت ملكة الدنمارك إدموندز درجة الدكتوراه الفخرية من جامعة جنوب الدنمارك .

في عام 2014 تم تكريمه كعالم متميز وتم إدخاله في معرض المعهد الوطني للمعايير والتكنولوجيا.

تم تخصيص ورشة العمل الخامسة للأوسوا حول التحسين التوافقي في عام 2001 له. ^{[ 13 ]}

ابن جاك، جيف إدموندز، هو أستاذ علوم الحاسوب في جامعة يورك ، وزوجته كاثي كاميرون هي أستاذة الرياضيات في جامعة لورييه .

• مصفوفة إدموندز
• قائمة بأسماء الأشخاص في جامعة واترلو

• جاك إدموندز في مشروع علم الأنساب الرياضي
• سيرة جاك إدموندز من معهد بحوث العمليات وعلوم الإدارة