شایان اویس قرن مدال ارزشمند آباکوس در علوم کامپیوتر نظری دریافت کرد ، استاد مسئله فروشنده دوره گرد - لیسون

در این مقاله قصد داریم مسیر شگفت انگیز زندگی و دستاوردهای علمی شایان اویس قرن را آنالیز کنیم و ببینیم او چگونه توانست پس از چهار دهه، رکورد الگوریتم کلاسیک مسئله فروشنده دوره گرد را بشکند. آیا پیوند میان احتمالات، نظریه گراف و چندجمله ای ها می تواند کلید حل پیچیده ترین مسائل محاسباتی عصر ما باشد؟ چگونه نگاهی فرارشته ای و بی پروا می تواند یک بن بست ریاضی 40 ساله را فرو بریزد؟ با ما همراه باشید تا سیر اندیشه و دستاوردهای این ریاضیدان نامدار را مرور کنیم.

➕ لیست بخش های این نوشته (کلیک کنید)

1. نگاهی نو به ابزارهای ریاضیات نظری
2. امیدواری بی قرار در میان سختی ها
3. از المپیاد تا عبور از مرزها
4. مسئله فروشنده دوره گرد و میان برهای خلاقانه
5. ساختن خانه اثبات؛ آجربه آجر
6. زنجیره های مارکوف و انقلاب در نمونه گیری
7. بازگشت به ریشه ها و شکستن رکورد 40 ساله
8. نگاهی به مسئله فروشنده دوره گرد و پیچیدگی الگوریتم ها
9. چرا مدال آباکوس اهمیت دارد؟
10. تاثیر چندجمله ای های ترکیبیاتی بر علوم کامپیوتر

01

نگاهی نو به ابزارهای ریاضیات نظری

در علوم کامپیوتر نظری، کلید حل مسائل پیچیده در یافتن ابزار مناسب نهفته است. بیشتر پژوهشگران به سراغ ابزارهایی می روند که با موضوع تحقیقشان همخوانی مستقیم دارد و بعضی تمام مسیر حرفه ای خود را صرف استاد شدن در چند روش آشنا می نمایند. اما شایان اویس قرن، دانشمند علوم کامپیوتر در دانشگاه واشنگتن، هرگز به روش های تکراری قانع نبوده است. او وقت زیادی روی یک رویکرد واحد نمی گذارد، چرا که احساس بی قراری می نماید و معتقد است در صورت درجا زدن، چیز نوی یاد نخواهد گرفت.

اویس قرن نه تنها در اندیشه، بلکه در رفتار فیزیکی نیز بی قرار به نظر می رسد. هنگام صحبت درباره تحقیقاتش هیجان زده می گردد و مدام شرایط نشستن خود را تغییر می دهد. شایان به خاطر پژوهش هایش روی مسئله فروشنده دوره گرد، که مسئله ای بسیار سخت درباره یافتن بهینه ترین مسیر میان چند نقطه است، معروفیت جهانی دارد. او بعلاوه مشارکت های درخشانی در زمینه انتخاب تصادفی از میان مجموعه های بزرگ ریاضی داشته است. به پاس همین کوشش ها، اتحادیه بین المللی ریاضیات مدال آباکوس را به او اهدا کرد؛ مدالی که هر چهار سال یک بار به محققان برجسته زیر 40 سال در علوم کامپیوتر نظری داده می گردد. کمیته داوران به بهره گیری او از ابزارهای نوین از بخش های فراتر از نگاه اولیه ریاضیات اشاره نمود که در ظاهر ربطی به علوم کامپیوتر ندارند.

02

امیدواری بی قرار در میان سختی ها

پژوهشگرانی که بین حوزه های مختلف ارتباط برقرار می نمایند، معمولاً پهنای دانش خود را به قیمت کاهش عمق آن به دست می آورند، اما شایان اویس قرن از این قاعده مستثنی است. او در عین انرژی بی نهایتش، صبوری لازم برای درگیر شدن با مسائل سخت به مدت چند سال و آنالیز تمام جزئیات فنی اثبات های طولانی را دارد. همکارانش تعهد و قدرت حل مسئله او را شگفت انگیز می دانند.

حوزه تخصصی او بر درک الگوریتم ها تمرکز دارد؛ یعنی همان دستورالعمل های ریاضی که کامپیوترها برای انجام وظایف به کار می گیرند. بعضی دانشمندان در پی ترسیم مرزهای محاسبات و یافتن مسائلی هستند که حتی برای الگوریتم های هوشمند بسیار سخت اند، اما شایان در گروه خوش بینانی قرار می گیرد که قصد دارند مرزهای توانایی الگوریتم ها را توسعه دهند. او همیشه تاکید می نماید که حل مسائل پیچیده امکان پذیر است.

03

از المپیاد تا عبور از مرزها

شایان اویس قرن در اصفهان و در خانواده ای دانشگاهی رشد کرد. مادرش معلم زیست شناسی بود که علاقه شدیدی به ریاضیات داشت و فرزندانش را به تحصیل تشویق می کرد. شایان که کوچک ترین فرزند خانواده بود، همیشه پروژه ها و کوشش های برادران و خواهران بزرگ تر خود را الگو قرار می داد. رابطه نزدیک او با برادرش شهاب، که در المپیاد کامپیوتر فعال بود، باعث شد تا شایان نیز شیفته معماهای ریاضی گردد. این علاقه تا جایی پیش رفت که او در سال 2004 مدال طلای المپیاد جهانی کامپیوتر را کسب کرد.

او سپس دوره کارشناسی مهندسی کامپیوتر را در دانشگاه صنعتی شریف گذراند. در همین دوران با همسرش فرناز رونقی آشنا شد. این دو پس از اتمام تحصیلات دانشگاهی، تصمیم به ادامه تحصیل در خارج از کشور گرفتند و وارد دانشگاه استنفورد شدند. ورود به دوره دکتری استنفورد دوباره آتش علاقه شایان را به تحقیقات بنیادی و ریاضیات نظری شعله ور ساخت.

04

مسئله فروشنده دوره گرد و میان برهای خلاقانه

در دوران دکتری، شایان برای اولین بار با مسئله فروشنده دوره گرد روبه رو شد. سوال اصلی این است: با داشتن نقشه ای از شهرها و راه ها، کوتاه ترین مسیر دوری که از همه شهرها بگذرد چیست؟ از آنجا که یافتن پاسخ دقیق برای تمام نقشه ها در زمان کوتاه عملاً غیرممکن تلقی می گردد، پژوهشگران در پی الگوریتم های تقریبی هستند. الگوریتم کلاسیک نیکوس کریستوفیدس که در دهه 1970 ارائه شد، مسیری فراوری می کرد که حدبیشتر 50 درصد از مسیر بهینه بلندتر بود. چندین دهه، هیچ دانشمندی نتوانسته بود این حد تقریب را بهبود ببخشد.

شایان اویس قرن و همکارانش تصمیم گرفتند با ترکیب عنصر تصادف و مفاهیم درخت های فراگیر (Spanning Trees)، الگوریتم نوینی طراحی نمایند. آن ها عبارت های پیچیده احتمالی را به فرمول های چندجمله ای تبدیل کردند. تبدیل مسئله به دنیای چندجمله ای ها اجازه داد ابزارهای نو ریاضی وارد کار شوند و بن بست های قبلی از بین بروند.

05

ساختن خانه اثبات؛ آجربه آجر

شایان تحقیقات علمی را فرایندی آرام و تدریجی می داند. از نظر او اثبات یک قضیه مانند چیدن آجرهای یک ساختمان است که تا لحظات پایانی تعیین نیست آیا بنا راسخ می ماند یا خیر. او اغلب هنگام تفکر ریاضی، خود را با فعالیت های دیگر سرگرم می نماید. در دوران دانشجویی بازی تتریس ابزار تمرکز او بود و گاهی ایده ها در خواب به سراغش می آمدند.

او به همکاری های علمی نزدیک علاقه مند است و جلسات طوفان فکری طولانی برگزار می نماید. او همراه با نیما اناری، دوست و همکار قدیمی اش، استفاده از روش های چندجمله ای را برای پیشبرد مسائل نظریه گراف و احتمالات توسعه دادند که در نهایت منجر به حل معماهای بزرگ دیگری در علوم کامپیوتر شد.

06

زنجیره های مارکوف و انقلاب در نمونه گیری

یکی از دستاوردهای بزرگ شایان اویس قرن و تیمش، حل حدس معروف نمونه گیری پایه های متروئید بود که حدود 30 سال بدون پاسخ مانده بود. الگوریتم های نمونه گیری مانند بورک زدن کارت های بازی، بر پایه زنجیره های مارکوف عمل می نمایند. مسئله اصلی این بود که چند بار باید فرایند تصادفی تکرار گردد تا نمونه نهایی واقعاً تصادفی و یکنواخت باشد.

تیم او با ترجمه ساختار متروئیدها به زبان چندجمله ای ها و استفاده از خصوصیات هندسی آن ها، توانست زمان ترکیب زنجیره های مارکوف را به اثبات برساند. این دستاورد یک تحول تحسین برانگیز در ریاضیات محض و الگوریتم های کاربردی ایجاد کرد و چارچوب نوی برای مطالعه سیستم های پیچیده فیزیکی و آماری فراهم ساخت.

07

بازگشت به ریشه ها و شکستن رکورد 40 ساله

پس از موفقیت در الگوریتم های نمونه گیری، شایان اویس قرن دوباره به مسئله فروشنده دوره گرد بازگشت. او با ابزارهای قدرتمندی که در طول سال ها اندوخته بود، همراه با آنا کارلین و نیتن کلین، آنالیز حالت عمومی این مسئله را شروع کرد. آن ها روش های نوینی برای تحلیل بخش های متداخل گراف ارائه دادند.

خاتمه این مقاله 90 صفحه ای دقیق، رکورد 40 ساله الگوریتم کریستوفیدس را شکست و نشان داد که می توان به تقریب های بهتری در حالت کلی دست یافت. این موفقیت تحسین بزرگ ترین پژوهشگران دنیای الگوریتم را به همراه داشت و جایگاه او را در صدر محققان این رشته تثبیت کرد.

08

نگاهی به مسئله فروشنده دوره گرد و پیچیدگی الگوریتم ها

مسئله فروشنده دوره گرد (TSP) یکی از مشهورترین مسائل کلاس NP-hard در علوم کامپیوتر است. اهمیت این مسئله تنها به پیدا کردن مسیر سفر مربوط نمی گردد، بلکه کاربردهای وسیعی در طراحی تراشه های سیلیکونی، مسیریابی داده ها در شبکه های اینترنت، لجستیک و حتی زنجیره تامین پروتئین ها دارد. زمانی که تعداد نقاط افزایش می یابد، تعداد حالت های ممکن به صورت فاکتوریل رشد می نماید؛ بنابراین روش های جستجوی ساده کاملاً ناکارآمد می شوند.

شکسته شدن حد تقریب کریستوفیدس به وسیله شایان اویس قرن و همکارانش نشان داد که مرزهای نظری محاسبات هنوز شناور هستند. پیشرفت در این حوزه می تواند مستقیماً به بهینه سازی الگوریتم های هوش مصنوعی و پردازش داده های بسیار سنگین در صنایع مدرن یاری کند.

09

چرا مدال آباکوس اهمیت دارد؟

مدال آباکوس (که پیش تر با نام جایزه نوانلینا شناخته می شد) هم ارز مدال فیلدز در حوزه علوم کامپیوتر نظری است. این جایزه جایگاهی فوق العاده در جوامع علمی دارد و هر چهار سال یک بار به وسیله اتحادیه بین المللی ریاضیات اهدا می گردد. اعطای این جایزه به شایان اویس قرن، ارزش تفکر فرارشته ای را اثبات کرد.

نگاه نوآورانه او در وارد کردن ابزارهای هندسه جبر و چندجمله ای های پایداری به مسائل ترکیبیاتی، مسیرهای پژوهشی تازه ای را برای نسل نو دانشمندان علوم کامپیوتر گگردده است.

10

تاثیر چندجمله ای های ترکیبیاتی بر علوم کامپیوتر

استفاده از چندجمله ای ها برای حل مسائل گسسته، یکی از زیباترین جهش های فکری در ریاضیات مدرن است. در الگوریتم های کلاسیک، گراف ها اشیائی گسسته شامل یال و رأس دیده می شوند، اما وقتی این ساختارها به صورت ضرایب چندجمله ای نگاشته می شوند، ابزارهای حساب دیفرانسیل و هندسه وارد عمل می شوند.

این روش که شایان اویس قرن از پیشگامان بهره گیری از آن در الگوریتم هاست، اجازه می دهد خواص پیچیده شانس و احتمال را با دقت بالا تحلیل کنیم؛ دستاوردی که در تحلیل الگوریتم های تصادفی انقلابی به پا نموده است.

جمع بندی نهایی

مسیر علمی شایان اویس قرن گواهی روشن بر اهمیت کنجکاوی بی حدومرز و جسارت فکری در مواجهه با چالش های علمی است. دستاوردهای او در حل مسئله فروشنده دوره گرد و الگوریتم های نمونه گیری نشان می دهد که بن بست های دیرینه علوم کامپیوتر تنها زمانی شکسته می شوند که مرزهای میان شاخه های گوناگون ریاضیات از میان برداشته شوند. مدال آباکوس تنها پاسداشتی برای گذشته نیست، بلکه نویدبخش افق های تازه ای است که تفکر پیونددهنده و خلاق می تواند در آینده الگوریتم ها و دنیای محاسبات بگشاید. خردمندی علمی در این است که هرگز به ابزارهای موجود قانع نباشیم و همیشه راه های نرفته را جستجو کنیم.

منبع