عبدالرحیم بهرامی دانشجوی کارشناسی ارشد مهندسی رایانه، نماینده تیم دانشگاه صنعتی اصفهان با ارائه برنامه ای با عنوان Power-SAT موفق به کسب مقام اول جهان در مسابقات الگوریتم رایانه ای با نام ۲۰۱۰ Race-SAT در شاخه دانشجویی و مقام سوم جهان در شاخه اصلی این مسابقات شد.
در این مسابقات که در دانشگاه ادینبرگ اسکاتلند برگزار شد فقط ۱۹ برنامه در ۲۰۱۰ SAT از کشورهای ایران، اسپانیا، آمریکا، چین، فرانسه، سوئد، اتریش و آلمان به مرحله نهایی راه یافتند که تیم دانشگاه صنعتی اصفهان شامل عبدالرحیم بهرامی، مریم فرشچیان و دکتر سید رسول موسوی بود. SAT یکی از مهمترین مسائل رایانه ای است که تا کنون الگوریتمی با مرتبه زمانی چند جمله ای برای آن یافت نشده، اما اثبات نیز نشده است که چنین الگوریتمی برای آن وجود ندارد.
اهمیت این مسائل به اندازه ای است که از سال ۱۹۹۸ هر ساله همایشی درباره آن و مسائل مشتق شده از آن برگزار شده و برنامه های مختلفی از سراسر جهان برای حل این مسائل به رقابت می پردازند. برنامه هایی که بیشترین نمونه ها را در کمترین زمان حل کنند به عنوان برنده شناخته می شوند.
محاسبات در دنیای رایانه به سه دسته تقسیم می شود که دسته اول شامل مسائلی است که راه حلی با مرتبه زمانی چند جمله ای دارند. دسته دوم شامل مسائلی است که اثبات شده که هیچگاه راه حلی با مرتبه زمانی چند جمله ای ندارد. دسته سوم نیز شامل مسائلی است که تا کنون الگوریتمی با مرتبه زمانی چند جمله ای برای آن یافت نشده اما اثبات نیز نشده که چنین الگوریتمی برای آن وجود ندارد. بخش عمده ای از مسائل دسته سوم را Complete-NP تشکیل می دهد که مساله SAT به عنوان مادر این مسائل از اهمیت بالایی برخورداراست.
منبع: خبرگزاری ایرنا، ۱۳۸۹/۵/۱۰، کد خبر: ۷۱۶۶۴۳۴
