مساله تقریب فاصله ویرایش

این نوشته در مورد مقاله زیر است و پیوند آن این است.

Chakraborty, Diptarka, et al. “Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.” (2018).

مساله فاصله ویرایش یک مساله معروف در علوم کامپیوتر است که معمولا در درس‌های ابتدایی الگوریتم تدریس می‌شوند. مساله بدین صورت است که دو رشته S و T را داریم و می‌خواهیم با کم‌ترین تغییرات شامل حذف، اضافه کردن، و یا تغییر حرف به حرف دیگر دو رشته را به هم تبدیل کنیم. هدف مساله یافتن کم‌ترین تعداد تغییرات برای تبدیل دو رشته به یکدیگر است.

در درس الگوریتم یاد می‌گیریم که الگوریتیمی با زمان اجرای متناسب با mn که m و n طول رشته‌های ورودی هستند برای مساله وجود دارد.

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

مساله تقریب فاصله ویرایش مساله جذابی بوده و نتایج زیادی در موردش مطرح شده. در حقیقت یک الگوریتم دو پارامتر دارد که با آن‌ها سنجیده می‌شود: ضریب تقریب و زمان اجرا. ضریب تقریب توضیح می‌دهد که پاسخ الگوریتم حداکثر چندبرابر جواب بهینه است و با زمان اجرا هم که آشنا هستید.

در سال ۲۰۱۰ الگوریتمی ارائه شد که ضریب تقریب آن یک چندجمله‌ای برحسب لگاریتم n است (اینجا فرض می‌کنید n و m برابر هستند) و زمان اجرای آن تقریبا خطی است، یعنی زمان اجرای آن n ضربدر یک چندجمله‌ای برحسب لگاریتم n است.

در سال ۲۰۱۷ نشان داده شده که اگر فرض‌های معمول پیچیدگی را قبول کنیم، الگوریتمی با ضریب کمتر از \(1+o(1)\) برای مساله وجود ندارد.

در کنفرانس FOCS امسال الگوریتمی ارائه شده که با ضریب ثابت و در زمان کمتر از توان دوم n مساله را حل می‌کند. پس از سال‌ها دستاورد خیلی جالبی است. 

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

سمینار ترم آینده

احتمالا یک سمینار ترم آینده ارائه می‌کنم. موضوعش مشخص نیست. گزینه‌های روی میز این‌ها هستند:

۱) الگوریتم‌های با زمان اجرای میانگین سریع. این موضوع جدیدا مورد توجه قرار گرفته. منبع‌های محتمل: درس آقای ترویسان

۲) کران پایین برای الگوریتم‌های چندجمله‌ای.

۳) نظریه پیچیدگی ریزدانه. منبع احتمالی: درس خانم ویلیامز

سوالی که مطرح است این است که چگونه درس ارائه شود. یا چگونه نمره داده شود. محتمل‌ترین گزینه این است که جزوه‌های یک درس را دانشجویان به ترتیب ارائه کنند. ولی جذاب‌تر این است که فیلم‌های یک درس یا یک سخنرانی را با هم ببینیم. مشکل اینجاست که در صورت اخیر، چگونه به دانشجویان نمره بدهیم؟! اگر گزینه‌ای دارید بفرمایید که موجب کیفیت این سمینار خواهد بود.

درس‌های ترم آینده

ساختمان داده

ترم آینده یک درس کارشناسی ساختمان داده ارائه می‌کنم. این درس از دروس سال دوم است، در نتیجه احتمالا در خدمت سال دومی‌هایی هستم که سال گذشته هم در خدمتشان بودم. امیدوارم که خیلی بهشان سخت نگذشته باشد و این ترم هم خیلی بهشان سخت نگذرد. 

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

به عنوان پیش‌نیاز باید دانشجویان برنامه‌نویسی پیشرفته را بلد باشند. فکر کنم گسسته هم پیش‌نیاز درس بوده، به هر حال دانستن گسسته هم خیلی کمک می‌کند.

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

برخی می‌پرسند بدون پاس کردن درس برنامه‌نویسی پیشرفته می‌توانند درس ساختمان داده را بگیرند؟ پاسخ: اگر برنامه‌نویسی بلدند و فقط مشکل این است که درس پاس نکرده‌اند مشکلی نیست، وگرنه خیلی سختشان خواهد بود و تمرین‌ها را نمی‌توانند انجام دهند. مثلا از تعریف درسی که در سایت دانشکده برای درس نوشته، ۷۰ درصدش را بلد باشند.

بهینه‌سازی برای علوم داده

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

مباحث گفته شده در کتاب‌های بالا هستند. می‌توانید نگاه کنید و پیشاپیش از درس لذت ببرید. امیدوارم در ترم آینده بیشتر من این درس را درس بدهم و دکتر علیشاهی بیشتر شنونده باشند.

طبیعتا درس کمی طعم ریاضی خواهد داشت و کم‌تر طعم الگوریتمی. از درس بهینه‌سازی محدب کم‌تر و از درس‌های ارشدی که معمولا من درس می‌دهم بیشتر ریاضی‌گونه خواهد بود.

به عنوان پیش‌نیاز الگوریتم و ریاضی ۲ که لازم هستند. دانستن آمار موجب می‌شود مثال‌ها را خیلی بهتر متوجه شوید.

توصیف درس در قالب فایل پی‌دی‌اف در این فایل آمده است. به نظر می‌آید از کتاب آقای بوبک در این درس استفاده نکنیم.

پنل ویژه در همایش پیوند

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

پوستر برنامه:

در مورد پنل هم نوشته‌اند:

ریاضیات؛ از نظریات محض تا مدلهای کاربردی

بررخلاف برنامه‌های معمول انتخاب رشته، هدفمان از این پنل یافتن پلاسخ به سوالات اساسی‌تری مثل این‌هاست:

هر کدام از این رشته‌های دانشگاهی چه مشکلی را، واقعا می‌توانند حل کنند؟ تفکیک علوم، به علوم پایه و کاربردی تا چه حد لازم و واقعی تا چه اندازه، معنی‌دار است؟ آیا واقعا ریاضیات زبان همه‌ی علوم است؟

حقیقت چیست؟ آیا این تنها تلاش ماست که تمام دانشمان از دنیای اطراف را به ریاضیات تبدیل کنیم یا اینکه اساسا دنیا بر مدارهای منطقی ریاضیات استواد شده است؟

این میان، ترویج علم چه جایگاهی دارد؟ چه مقدار نیاز است که ما بدانیم دانشمندان در آزمایشگاه‌هایشان چه می‌کنند؟

خوبی پنل این است که لازم نیست چیزی برایش آماده کنی. پیوند به سایت پیوند هم اینجاست.

سمینار الگوریتم تقریبی برای شمارش پایه‌های ماتروید

سخنرانی دکتر شایان اویس‌قرن دوشنبه مرداد ۱۶ تا ۱۸ برگزار می‌شود. از همه طیفی‌کاران و دانشجویان ارشد و دکتری خود دعوت می‌کنم که در این سخنرانی شرکت کنند. احتمالا سخنرانی پرمغز و بسیار جالبی خواهد بود.

راهنمای پژوهشی و دیگر داستان‌های مرزها

امروز مرزهای علوم ریاضی تمام شد. مرزهای علوم ریاضی جایی است که افراد جالبی را می‌بینیم که کارهای جالبی انجام می‌دهند. لازم نیست ما زحمت بکشیم برویم و کارهای آن‌ها را ببینیم، آن‌ها خودشان می‌آیند و کارهایشان را به ما نشان می‌دهند. جالب است.

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

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

مشخصات یک پروژه کارشناسی (فنی‌تر)

پروژه کارشناسی با تولید یک نرم‌افزار تمام نمی‌شود. برای پروژه کارشناسی شما باید:
    1. یک موضوع درست و درمان داشته باشید
    2. فعالیت‌های پیشین در زمینه موضوع خود را مطالعه کنید.
    3. یک پایان‌نامه بنویسید شامل:
      • مقدمه: موضوع چیست و چرا مهم است
      • پیشینه پژوهش: همه کارهای مرتبط با موضوع شما. اگر کار مرتبطی با موضوعتان وجود ندارد، موضوعتان خوب نیست. پس باید حتما همه کارهای مرتبط را پیدا کرده و جمع‌بندی کنید و به طور کاملا مفصل توضیح بدهید
      • فعالیت‌های شما: کارهایی که انجام داده‌اید. اگر الگوریتمی دارید. اگر الگوریتم‌هایی داشتید و جواب نداده‌اند. همه را بهتر است بنویسید.
      • نتایج: کارهایی که انجام داده‌اید چه جواب‌هایی داده‌اند و این جواب‌ها را با یکدیگر و با دیگر کارهای مشابه مقایسه کنید.
      • جمع‌بندی: آخرش چه شد. مساله شما خوب بود یا نبود. چرا خوب بود چرا نبود. پس از شما دنیا چه تغییری کرده و از این صحبت‌ها
اگر چه اندازه پایان‌نامه معمولا کیلویی نیست، اما یک پایان‌نامه کارشناسی خوب است حداقل ۳۰ صفحه اصلی (بدون فهرست و منابع و این‌ها) داشته باشد.
و باید این کارها را پیش از اینکه بخواهید نمره را بگیرید انجام بدهید و نسخه نهایی را به استاد راهنمایتان تحویل بدهید. این خیلی کار وقت‌گیری است. اگر دیر بشود، متاسفانه نمره شما رد نمی‌شود و تنها نمره P در کارنامه شما قرار خواهد گرفت

سوال درباره ادامه تحصیل در خارج از کشور‎

نامه‌ای دیگر:

با سلام خدمت دکتر فروغمند

من در هماش پیوند شرکت کردم و آن جا با شما اشنا شدم. اول می خواستم ازتون به خاطر سخنرانی خیلی خوبتون تشکر ویژه بکنمواقعا استفاده کردم.

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

از طرفی تجربه ای که ادم اونجا کسب می کنه چقدر به درد کار کردن در اینجا می‌خوره؟

می خواستم بدونم نظر شما در رابطه با این موضوع ها چی هست؟

با تشکر فراوان

فلانی

دانشجوی کارشناسی مهندسی کامپیوتر دانشگاه امیرکبیر

و پاسخ:

ممنون از تشکرتان

۱- تعداد استادهای خوب خارج خیلی خیلی بیشتر از تعداد استادهای خوب ایران است. شما به عنوان دانشمند باید با چندین دانشمند و روش‌های پژوهششان آشنا شوید. در نتیجه این دلیل برای ماندن کافی نیست.

۲- منابع در اختیار هستند، درست است. اما یک منبع مهم که شما در ایران در اختیار ندارید اعتماد استادها برای گفتن ایده‌هایشان به شماست. با ایمیل زدن نمی‌توانید ایده‌هایشان را بگیرید، در حالی‌که دانشجوهایشان ایده‌هایشان را می‌شناسند و برروی آن‌ها کار می‌کنند.

۳- برای اینکه در میان دانشمندان مهم شوید، کارهایتان دیده شود، با شما همکاری کنند و به شما بودجه بدهند، باید دانشمندان شما را بشناسند. متاسفانه این داستان اصلا عادلانه نیست و بسیار به روابط انسانی وابسته است. در نتیجه بودن شما آن‌جه بسیار به این موضوع کمک می‌کند. حتی اگر شما را دیده باشند، مقاله‌تان را با احتمال بیشتری قبول می‌کنند.

۴- فردی که می‌خواهد اینجا مفید باشد، چرا می‌خواهد اینجا مفید باشد؟ این فرد معمولا پس از گذشت دورانی به این نتیجه می‌رسد که حالا چه فرقی می‌کند برای ایران مفید باشد یا برای جای دیگری. یا معمولا به این نتیجه می‌رسد که حالا مهم هم نیست که اصلا مفید باشد، زندگی‌اش را بکند کافی است.

۵- افرادی که می‌روند، چون برگشتن برایشان سخت است، کم‌کم برای خودشان تئوری‌هایشان را تغییر می‌دهند به صورتی که ماندن آن‌جا در تئوری‌شان کار بهتری به نظر برسد.

اما این‌ها همه پاسخ نکاتی بود که شما گفته بودید.

آدم باید برود یا نباید برود؟ خیلی سخت است! هر دو ضررها و سودهایی دارند. تحلیل این مسئله خیلی طولانی و کار سختی است. اگر همه چیز خوب و عادی بود، شاید بهترین گزینه برای چنین فردی که شما توصیف کردید این بود که این‌جا می‌ماند ولی در دوران تحصیلات تکمیلی تقریبا ۳/۴ زمان را در خارج از کشور می‌گذراند و با افراد مختلف کار می‌کرد و مقاله تولید می‌کرد. البته این کار الآن هم امکان‌پذیر است، اما کار سختی است.