کلا دکتر رستگار دانشمند جالبی است. فعالیت‌های عجیب و غریب علمی و سیاست‌گذاری علم انجام می‌دهد که همگی جالب هستند. معمولا هم کارهایشان مملو است از ایده‌های جالب.

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

ظاهرا در این کنفرانس سعی می‌کنند به مسائل مربوط به یادگیری ماشین بپردازند و مخصوصا در نظر نظری! اخیرا خیلی هم مورد توجه قرار گرفته. شاید نگاهی به مقاله‌هایش بد نباشد.

مثلا لیست مقاله‌ها را نگاه کنید شامل چند تا مقاله است؟! اگر فردی شمرد بگوید چند تا بوده.

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

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

عنوان این نوشته نام تقریبی مقاله‌ای است که به تحلیل دوباره الگوریتم کارگر-اشتاین برای k-برش در گراف پرداخته. تا آن‌جایی که متوجه شدم مقاله نشان داده که احتمال انتخاب برش‌های مناسب در الگوریتم مورد بحث بهینه است.

مقاله تحلیل جدیدی برای الگوریتم قدیمی کارگر-اشتاین ارائه کرده و نتایج حاشیه‌ای دیگری نیز گرفته است.

لینک مقاله.

The Karger-Stein Algorithm is Optimal for k-cut

Anupam Gupta, Euiwoong Lee, Jason Li(Submitted on 20 Nov 2019)

In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n2k−2). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut, and show that solving k-cut is likely to require time Ω(nk). Our recent results have given special-purpose algorithms that solve the problem in time n1.98k+O(1), and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that for any fixed k≥2, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least O^(n−k), where O^(⋅) hides a 2O(lnlnn)2 factor. This also gives an extremal bound of O^(nk) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are tight up to O^(1) factors. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most (2−δ)OPT/k, using the Sunflower lemma.

عنوان مقاله‌ای است در نیچر. مقاله را می‌توانید در اینجا پیدا کنید.

یکی از دوستان این کتاب را معرفی کرد. خیلی کتاب جالبی است و مساله‌های زیادی را به صورت برنامه‌ریزی خطی-صحیح صورت‌بندی کرده. برای افرادی که بخواهند مساله‌هایی پیدا کنند که به صورت ریاضی می‌توان صورت‌بندی کرد منبع خوبی است. حتی برای اینکه درسی در این زمینه ارائه بشود شاید خوب باشد.

مشخصات کتاب:

Publisher: Cambridge University Press

Online publication date: May 2019

Print publication year: 2019

Online ISBN: 9781108377737

DOI: https://doi.org/10.1017/9781108377737

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

در ترم آینده دکتر اعتصامی و دکتر دهقانی درسی ارائه می‌کنند با نام الگوریتم‌های امروزی. هر دو مدرسین از پژوهشگران برجسته در زمینه‌های نظریه علوم کامپیوتر هستند و مباحث درس نیز مباحث جالبی است. کلا توصیه می‌شود.

یکی از اساتید بسیار جالب علوم/مهندسی کامپیوتر که در دانشگاه نوشیروانی بابل مشغول به استادی هستند، آقای دکتر غلامی رودی هستند.

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

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

تعریف خود ایشان از نیتراف را ببینید:

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

دانشجویی ماه‌ها پیش نوشته بود:

من دو یا سه ماهی است که ذهنم درگیر این ۲ سوال شده‌است:
۱. آیا ساختار (هم روابط انسانی، هم قواعد سازمانی دانشگاه)‌ توانایی و کشش این را دارد که بتوان کاری کرد.
۲. در صورتی که جواب به سوال ۱ بله باشد، چه فیلدهایی پیشگام در این زمینه است یا بهتر بگویم در چه فیلد‌هایی کار‌های بزرگ(!) انجام می‌شود.

در مورد سوال ۲ گرایش‌های مختلف کامپیوتر و ریاضی (ماشین لرنینگ، الگوریتم، OR و بایوانفورماتیک) و رشته‌های مختلف (سیاست‌گذاری عمومی، MBA، فلسفه علم) را به شکل گذری بررسی کردم ولی آنی نبود که بگویم: «این می‌تواند مشکلی بزرگ حل کند». شاید این طرز تفکر غلط باشد. نمیدانم.

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

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

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

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

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

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