چای با سرطان

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

زمان اجرای الگوریتم ضرب دو ماتریس

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

در الگوریتم بدیهی برای ضرب دو ماتریس A و B، برای محاسبه هر درایه از ماتریس لازم است که n عدد ضرب انجام شود. در نتیجه زمان اجرای الگوریتم \(O(n^3)\) خواهد بود.

امروز در کلاس ساختمان داده سر الگوریتم استراسن بحث شد. الگوریتمی که با آن می‌توان دو ماتریس n در n را در زمان سریع‌تر از \(O(n^3)\)، یعنی در زمان \(O(n^{2.807})\) محاسبه کرد.

سوالی که مطرح شد این بود که زمان اجرای سریع‌ترین الگوریتم برای محاسبه ضرب دو ماتریس چقدر است؟ پس از الگوریتم استراسن که در سال ۱۹۶۹ ارائه شده بود، الگوریتم دیگری با زمان اجرای \(O(n^{2.376})\) در سال ۱۹۹۰ و الگوریتم سریع‌تری با زمان اجرای \(O(n^{2.3729})\) در سال ۲۰۱۳ و الگوریتم دیگری با زمان اجرای \(O(n^{2.3728639})\) در سال ۲۰۱۴ ارائه شد. نمودار زیر از ویکی‌پدیا توان n در زمان اجرای الگوریتم ضرب دو ماتریس را در طی زمان نشان می‌دهد.

فرض کنید سریع‌ترین الگوریتمی که برای ضرب دو ماتریس وجود دارد زمان اجرایش حدودا \(O(n^{\omega})\) است. سوال این است که این \(\omega\) چند است؟ تا کنون می‌دانیم \(\omega\leq 2.3728639\). از طرفی چون باید جواب را تولید کنیم و ورودی را باید بخوانیم حداقل باید به اندازه خود ماتریس‌ها زمان صرف کنیم، پس \(2\leq\omega\leq 2.3728639\). اما بیش از این نمی‌دانیم. یعنی حتی نمی‌دانیم آیا \(\omega\) از ۲ اکیدا بزرگ‌تر است یا خیر.

در هر صورت این مساله خیلی مساله جالبی است. و خیلی جالب است که پس از مدت‌ها هنوز نمی‌دانیم که آیا بیش از خواندن ماتریس‌های ورودی زمان لازم است برای تولید ضرب دو ماتریس و یا خیر. با این‌که مقدار \(\omega\) را نمی‌دانیم، ولی می‌توانیم از این مقدار برای محاسبه زمان اجرای الگوریتم‌های دیگر استفاده کنیم. مثلا در مقاله‌ها می‌بینیم که زمان اجرای الگوریتم‌شان را بر حسب \(\omega\) محاسبه کرده و گزارش می‌کنند.

منبع: صفحه انگلیسی ویکی‌پدیا در مورد ضرب ماتریس‌ها

دفاع‌های پیش رو

چند دفاع پیش رو دارم که جالب هستند.

۱) مدل تصادفی برای بررسی ویژگی‌های هندسی رشد تومور

دانشجو: میرابوطالبی
زمان: ساعت ۹ صبح ۳۱ شهریور ۹۷
مکان: ۲۱۷ دانشکده ریاضی.
خلاصه: به طول کلی ایشان یک مدل ریاضی برای مدل رشد تومور ارائه کرده‌اند و سعی کردند خواص هندسی آن را استخراج کنند. ایده این بود که سپس خواص هندسی تومور واقعی سرطان را با مدل‌های مختلف هندسی مقایسه کنند و در مورد اینکه واقعا تومور چگونه رشد می‌کند صحبت کنند.

۲) مبنای ریاضی  شبکه‌های عصبی ژرف: چارچوبی نظری برای رفتار تعمیم‌پذیری

دانشجو: بابایی
زمان: ساعت ۱۳ تاریخ ۳۱ شهریور ۹۷
مکان: دانشکده ریاضی.
خلاصه: پژوهش‌هایی انجام شده که سعی دارند توجیه کنند چرا شبکه‌های عصبی ژرف کار می‌کنند. ایشان سعی کرده‌اند آن‌ها را مطالعه کرده و ارائه کنند.

۳) بررسی روش به‌روزرسانی ضربی وزن‌ها و کاربردهای آن

دانشجو: سقایی
زمان: ۶:۳۰
مکان: دانشکده ریاضی
خلاصه: روش به‌روزرسانی ضربی وزن‌ها، یک الگوریتم ساده است که کاربردهای زیادی در حل مساله‌های تقریبی و هم‌چنین بهینه‌سازی و یادگیری برخط دارد. در این پایان‌نامه ایشان سعی کرده‌اند کاربردها و روش را توضیح بدهند.

۴) بررسی رابطه بین عملکرد سلول و تعاملات فامینه با استفاده از روش‌های مبتنی بر انجمن

زمان: یک‌شنبه ۱ مهر ساعت ۱۰
مکان: ۶۲۸ دانشکده کامپیوتر
خلاصه: به طور خلاصه ایشان سعی کرده‌اند انجمن‌ها را تشخیص دهند.

چالش CAGI 5

چالش  CAGI یک برنامه چالشی است که در آن تلاش می‌کنند رابطه ژنوتیپ با فنوتیپ را با الگوریتم‌هایی پیدا کنند. ژنوتیپ به معنای اطلاعات ژنتیکی فرد است (که به صورت رشته‌های بسیار طولانی از چهار حرف A و T و C و G) و فنوتیپ یعنی مشخصات فردی. مثلا فرض کنید می‌خواهد از اطلاعات ژنوم فرد تشخیص بدهند چقدر احتمال گرفتن یک مریضی را دارند.

برنامه پنجم CAGI شروع شده که ظاهرا شامل ۴۰ چالش است. البته تقریبا تمام چالش‌هایش در حال پایان هستند. اما به هر حال شناختن این چالش بد نیست. شاید حداقل برخی دانشجویان خواستند در برنامه‌های بعدی شرکت کنند.

فیلم آموزشی بازآرایی (refactoring) توسط دکتر صادق علی اکبری

همان‌طور که می‌دانید بازآرایی یا refactoring از اصول برنامه‌نویسی چابک است. و احتمالا می‌دانید که دکتر صادق علی اکبری از مدرسین بسیار خوب جاوا هستند. ایشان مطالب مربوط به درس بازآرایی را ظاهرا منتشر کرده‌اند. در این زمینه می‌توانید به این نوشته مراجعه کنید.

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

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

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 که زیست‌شناسان از آن استفاده می‌کنند برای مقایسه دو رشته از برخی از همین روش‌ها استفاده می‌کند، بدون اینکه این همه جزئیات و اثبات را بدانند. خیلی جالب است.

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

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

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

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

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

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

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

ساختمان داده

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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