ميخاليس ياناكاكيس

ميخاليس ياناكاكيس ( باليونانية : Μιχάλης Γιαννακάκης ؛ وُلد في 13 سبتمبر 1953 في أثينا ، اليونان ) ^{[ 1 ]} هو أستاذ علوم الحاسوب في جامعة كولومبيا . يُعرف بإسهاماته في مجال التعقيد الحسابي وقواعد البيانات وغيرها من المجالات ذات الصلة. وقد فاز بجائزة دونالد إي. كنوث عام 2005. ^{[ 2 ] [ 3 ]}

وُلد ياناكاكيس في أثينا، اليونان عام 1953، وتلقى تعليمه الابتدائي في مدرسة فارفاكيو الثانوية. تخرج من جامعة أثينا التقنية الوطنية عام 1975 بشهادة في الهندسة الكهربائية، ثم حصل على درجة الدكتوراه في علوم الحاسوب من جامعة برينستون عام 1979. ^{[ 1 ]} وكانت أطروحته بعنوان "تعقيد مسائل الرسم البياني الجزئي الأقصى". ^{[ 4 ]}

في عام 1978، انضم إلى مختبرات بيل وشغل منصب مدير قسم أبحاث مبادئ الحوسبة من عام 1991 حتى عام 2001، عندما غادر مختبرات بيل وانضم إلى مختبرات أفايا. وهناك شغل منصب مدير قسم أبحاث مبادئ الحوسبة حتى عام 2002. ^{[ 1 ]}

في عام 2002 انضم إلى جامعة ستانفورد ، حيث كان أستاذاً لعلوم الحاسوب، وغادرها في عام 2003 لينضم إلى جامعة كولومبيا في عام 2004، حيث يشغل حالياً منصب أستاذ بيرسي ك. وفيدا إل دبليو هدسون لعلوم الحاسوب. ^{[ 1 ]}

من عام 1992 إلى عام 2003، شغل ياناكاكيس عضوية هيئة تحرير مجلة SIAM للحوسبة ، وكان رئيس تحريرها بين عامي 1998 و2003. كما كان عضوًا في هيئة تحرير مجلة ACM من عام 1986 إلى عام 2000. ^{[ 1 ]} وشملت عضوياته الأخرى في هيئات تحرير مجلات علمية محكمة، منها مجلة علوم الحاسوب والأنظمة ، ومجلة التحسين التوافقي ، ومجلة التعقيد . كما شارك في لجان مؤتمرات وترأس العديد منها، مثل ندوة ACM حول مبادئ أنظمة قواعد البيانات ، وندوة IEEE حول أسس علوم الحاسوب . ^{[ 1 ]}

اعتبارًا من يونيو 2020، تم الاستشهاد بمنشوراته ما يقرب من 35000 مرة، ويبلغ مؤشر h الخاص به 93. ^{[ 5 ]}

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

من بين إسهاماته في نظرية التعقيد ورقتان بحثيتان حول نظرية PCP وحول صعوبة التقريب . في ندوة ACM السنوية لنظرية الحوسبة عام 1988، قدّم ياناكاكيس وكريستوس باباديميتريو تعريفات فئتي التعقيد Max-NP وMax-SNP. تحتوي فئتا Max-NP وMax-SNP (وهي فئة فرعية من Max-NP) على عدد من مسائل التحسين المهمة، وقد بيّن ياناكاكيس وباباديميتريو أن هذه المسائل تتضمن هامش خطأ محدود. وقد ساهمت هذه النتائج في تفسير قلة التقدم الذي شهده مجتمع البحث العلمي في مجال تقريب عدد من مسائل التحسين، بما في ذلك مسألة 3SAT ، ومسألة المجموعة المستقلة ، ومسألة البائع المتجول . ^{[ 6 ]}

قدّم ياناكاكيس وكارستن لوند عددًا من النتائج المتعلقة بصعوبة حساب التقريبات في ندوة ACM السنوية لنظرية الحوسبة عام 1993. وأظهرت هذه النتائج صعوبة حساب الحلول التقريبية بكفاءة لعدد من مسائل التصغير، مثل تلوين الرسوم البيانية وتغطية المجموعات . ونظرًا لاستبعاد إمكانية حلّ مسائل NP-hard، مثل تلوين الرسوم البيانية وتغطية المجموعات، على النحو الأمثل في وقت متعدد الحدود ، فقد بُذلت محاولات عديدة لتطوير حلول تقريبية فعّالة لها؛ إلا أن النتائج التي توصل إليها ياناكاكيس وكارستن أثبتت استحالة تحقيق ذلك. ^{[ 7 ]}

في مجال نظرية قواعد البيانات ، تشمل إسهاماته بدء دراسة مخططات قواعد البيانات غير الدورية، والاستعلامات الاقترانية غير الدورية ( خوارزمية ياناكاكيس )، والقفل غير ثنائي الطور. مخططات قواعد البيانات غير الدورية هي مخططات تحتوي على تبعية ربط غير دورية واحدة (تبعية الربط هي علاقة تحكم ربط جداول قاعدة البيانات) ومجموعة من التبعيات الوظيفية؛ ^{[ 8 ]} وقد أشار عدد من الباحثين، بمن فيهم ياناكاكيس، إلى فائدة هذه المخططات من خلال إظهار العديد من الخصائص المفيدة التي تتمتع بها: على سبيل المثال، القدرة على حل العديد من المشكلات القائمة على المخططات غير الدورية في وقت متعدد الحدود، بينما قد تكون المشكلة من فئة NP-كاملة بالنسبة للمخططات الأخرى. ^{[ 9 ]}

فيما يتعلق بالتأمين غير ثنائي المرحلة ، أوضح ياناكاكيس كيف يمكن استخدام معرفة بنية قاعدة البيانات وأنواع المعاملات المختلفة المنفذة عليها لتحديد ما إذا كانت سياسة تأمين معينة آمنة أم لا. تتكون سياسات التأمين ثنائي المرحلة (2PL) الشائعة الاستخدام من مرحلتين - لتأمين الكيانات وفتحها على التوالي - ولتجنب هذه السياسة، من الضروري فرض بنية معينة على كيانات قاعدة البيانات. تُظهر نتائج ياناكاكيس كيف أنه باختيار رسم بياني فائق يُحاكي بنية قيود الاتساق لقاعدة البيانات، ستكون سياسة التأمين التي تزور الكيانات على طول مسارات هذا الرسم البياني الفائق آمنة. لا يشترط أن تكون هذه السياسة ثنائية المرحلة، ويمكن تصنيف هذه السياسات وفقًا لاتصال الرسم البياني الفائق المذكور أعلاه، حيث تُعد سياسات التأمين ثنائي المرحلة (2PL) مجرد مثال محدد عليها. ^{[ 10 ]} واصل ياناكاكيس إثبات أن خلو فئة سياسات القفل الآمنة الطبيعية (سياسات L) من حالات الجمود يتحدد فقط بترتيب وصول المعاملات إلى الكيانات، ومن هذا استنتج شروطًا بسيطة تضمن خلو سياسة L من حالات الجمود. ^{[ 11 ]}

كما أسهم في مجال التحقق والاختبار بمساعدة الحاسوب، حيث وضع الأسس الخوارزمية والنظرية المعقدة لهذا المجال. ومن بين إسهاماته تصميم خوارزميات فعالة من حيث الذاكرة للتحقق من الخصائص الزمنية للبرامج ذات الحالات المحدودة، ^{[ 12 ]} وتحديد تعقيد اختبار ما إذا كانت البرامج تفي بمواصفاتها المعبر عنها بمنطق زمني خطي ، ^{[ 13 ]} والتحقق من أن نموذجًا ذا قيود زمنية يفي بخاصية زمنية معينة. ^{[ 14 ]} وبالتعاون مع أليكس غروس ودورون بيليد، قدم مفهوم التحقق التكيفي من النموذج، موضحًا أنه عند وجود تناقضات بين النظام والنموذج المقابل، يمكن استخدام نتائج التحقق لتحسين النموذج. ^{[ 15 ]} كما ساهم في أبحاث حول مخططات تسلسل الرسائل (MSC)، حيث تبين أن قابلية التحقيق الضعيفة غير قابلة للتقرير بالنسبة لمخططات MSC المحدودة وأن قابلية التحقيق الآمنة تقع في EXPSPACE ، إلى جانب نتائج أخرى مثيرة للاهتمام تتعلق بالتحقق من مخططات MSC. ^{[ 16 ]}

يُعد ياناكاكيس أحد مخترعي فئة التعقيد FIXP .

ياناكاكيس عضو في كل من الأكاديمية الوطنية للهندسة والأكاديمية الوطنية للعلوم . وقد مُنح جائزة كنوت السابعة لإسهاماته في علوم الحاسوب النظرية. ^{[ 3 ]} كما نال جائزة بيل لابز للعضو المتميز في الطاقم التقني وجائزة بيل لابز الذهبية الرئاسية، في عامي 1985 و2000 على التوالي. وهو زميل في رابطة آلات الحوسبة (ACM) وزميل في مختبرات بيل . ^{[ 1 ]} وانتُخب زميلًا في الأكاديمية الأمريكية للفنون والعلوم (AAAS) عام 2020. ^{[ 17 ]}

• الصفحة الرئيسية في جامعة كولومبيا