لازلو بابایی (Laszlo Babai) در ۱۰ نوامبر ۲۰۱۵ در دانشگاه شیکاگو به معرفی الگوریتم جدیدش پرداخت. الگوریتمی که مشکل فریبندهی گرافهای هم شکل را سریعتر از روشهای دیگر حل میکند.
گرافهای همسان یک پازل به شدت به هم ریخته است که کامپیوترها و دانشمندانی که به آن برنامه میدهند به طور ناگهانی از کنترل و مدیریت آن باز می مانند.
الگوریتم جدید، به شکلی مؤثر مشکل گرافهای همسان را حل میکند. دانشمند علوم کامپیوتر لازلو بابایی در سمینار ترکیبات و نظریات علوم کامپیوتر در۱۰ نوامبر در دانشگاه شیکاگو اعلام کرد: این مشکل نیازمند آن است که مشخص شود دو گروه مجزا از نقاط به هم پیوسته، که به عنوان گراف میشناسیم، به یک شکل به هم متصل شدهاند، حتی اگر گرافها خیلی متفاوت به نظر برسند.
در عمل، الگوریتمهای موجود میتوانند در زمان معقولی کار خود را به انجام برسانند اما این احتمال وجود دارد که گرافهای بسیار پیچیده، مسئله را غیر قابل حل کنند.
رایان ویلیامز (Ryan Williams) دانشمند علوم کامپیوتر در دانشگاه استنفورد میگوید ایدهی اولیه من یک جوک به نظر میرسید . من میخواستم با الگوریتمی خاص که در حل گرافهای همسان استفاده میشود، نام ماه جاری را چک کنم تا مطمئن شوم نام آن آپریل نباشد. این در واقع یک جهش عظیم در فهم ما از مشکل است. این دستاورد مهمترین دستاورد نظری علوم کامپیوتر در دهه اخیر است.
الگوریتم لازلو بابایی هنوز نیاز به بررسی دارد اما تخصص او به همکارانش در بررسی نتایج اعتماد به نفس میدهد. او حتی قبل از اینکه این مسئله را موضوع رسالهی دکتری خود در ۱۹۸۴ قرار دهد با این مسئله درگیر بود، زمانی که این مسئله یک مسئله کاملاً انتزاعی به نظر میرسید. این یک مثال برجسته از مدلی عجیب و غریب از پازل هاست که کامپیوتر در حل آن مشکل دارد درحالیکه اگر یک شکل را به رایانه ارائه دهیم به سرعت میتواند راه حل را نشانمان دهد. البته نتیجه ممکن است در ماورای علوم کامپیوتر معکوس باشد، مثلاً اجازه دادن به شیمیدان¬ها که مولکول¬های پیچیده را دارای ساختار پیوندی یکسان در نظر بگیرند.
برخلاف تفاوت در اشکال، این دو گراف هم شکل هستند. هر دایره در هر گراف متناظر با یک دایره در گراف دیگر است و همچنین به سایر دوایر هم شکل وصل شده است. دوایر متناظر با یک رنگ نشان داده شده اند.
در اصطلاحات ریاضی کلمه گراف یک کلمه فانتزی به معنای شبکه است، نوعی نمودار که به تصویر کشیده میشود، مثل یک صفحه وب در فیسبوک و یا پیشرفت یک بیماری. هر نقطه یا گره مثل یک توپ پینگ پونگ است که از توپهای دیگر قابل تشخیص نیست و بوسیله رشتههایی به یک توپ دیگر و یا توپهای بیشتری متصل است. حال فرض کنید ۲ نمودار از این مدل ( توپهای پینگ پونگ) در دست داشته باشیم، چگونه می توان تفاوت آنها را پیدا کرد. برای حل این چنین مسائلی گرافها را به کامپیوترها میدهند تا کامپیوتر تشخیص دهد که وجوه تمایز آنها چیست.
کامپیوترها در تشخیص گرافهای همسان اندکی مشکل دارند حتی با وجود بهترین الگوریتمها، زمان حل مسئله با افزایش هر نقطه به مقدار قابل توجهی افزایش مییابد.
بابائی ادعا میکند الگوریتمی را توسعه داده که حتی مرموزترین گرافها که بنام شبه چندجملهایها شناخته میشوند را ارزیابی کرده و پاسخی بسیار دقیق ارائه میکند، اما با این وجود دکتر ویلیامز دانشمند علوم کامپیوتر از ادعای او مطمئن نیست و میگوید ما حتی شبه چند جملهای ها نزدیک هم نشدهایم.
منبع:علمنا
No tags for this post.