گروه‌های پس‌زمینه

https://en.wikipedia.org/wiki/Wallpaper_group

منظورش از گروه تعریف ریاضی آن است. جالب‌ترین قسمتش این است که کلاً ۱۷ نوع از اینها می‌شود داشت. چند تا مثال ایرانی هم دارد.

حل تمرین اول الگوریتم تصادفی استنفورد (۲۰۱۸)

سوالها: http://theory.stanford.edu/~valiant/teaching/CS265_2018/ps1.pdf

سوال ۱- قسمت اول) یک راه حل این است که سکه را دو بار بیندازیم، احتمال HT و TH با هم مساوی هستند و اگر چیزی غیر از این آمد یعنی HH یا TT دوباره آزمایش را تکرار می‌کنیم. احتمال جواب ندادن آزمایش ۱۷/۲۵ است، پس به طور متوسط باید ۲۵/۱۸ بار تکرارش کنیم.

قسمت دوم) دو بار سکه را می‌اندازیم. اگر HH آمد اعلام موفقیت می‌کنیم، اگر HT یا TH آمد اعلام شکست می‌کنیم، اگر TT آمد آزمایش را تکرار می‌کنیم. احتمال موفقیت ۳/۴ است، پس به طور متوسط باید ۴/۳ بار تکرارش کنیم (آزمایش برنولی با احتمال موفقیت p به طور متوسط نیاز به p^(-1) بار تکرار دارد تا به موفقیت برسد).

قسمت سوم) بعد از k بار سکه انداختن، اعدادی که در قسمت اول به دست می‌آیند جملات (1/5+4/5(^k هستند و در قسمت دوم جملات (1/2+1/2)^k هستند. برای اینکه بتوانیم احتمال مورد نظر خودمان را به دست بیاوریم باید بتوانیم آنها را به دو دسته تقسیم کنیم که جمع یکی از آن دسته‌ها احتمال مورد نظر ما باشد. در هر دو قسمت تعداد اعشاری از جملات را باید انتخاب کنیم که همین نشان می‌دهد این کار غیرممکن است.

سوال ۲- الف) احتمال اینکه یک نفر آلوده باشد k/n است (تقسیم تعداد حالت‌ها). احتمال آلوده بودن حداقل یک نفر از m نفر = ۱-احتمال آلوده نبودن هیچ کدام

=1-(1-k/n)^m

حالا فرض کنید به این احتمال بگوییم p. چون آلوده بودن یک گروه متغیر ۰ و ۱ (مشخصه) است پس احتمال آن با امید ریاضی آن برابر است. در کل n/m تا گروه داریم پس امید ریاضی کل (طبق خاصیت خطی بودن امیدریاضی که در سوال هم راهنمایی کرده) می‌شود جمع اینها، یعنی:

n/m p = n/m (1-(1-k/n)^m)

ب) اول اینکه n/m تا را که طبق الگوریتم مجبوریم انجام بدهیم برای مشخص شدن وضعیت گروه‌ها.

تعداد تست‌هایی که باید روی اعضای گروه‌ها انجام بدهیم به تعداد اعضای گروه‌های آلوده است. طبق قسمت الف، امیدریاضی تعداد گروه‌های آلوده را داریم، پس در کل تعداد تست‌ها برابر است با:

n/m+n (1-(1-k/n)^m)

روش دیگر محاسبه‌اش این است که هر گروهی که ۱ بود باید m تا تست دیگر هم انجام بدهیم. احتمال ۱ بودن را در قسمت قبل حساب کردیم، به کمک آن امید ریاضی را حساب می‌کنیم:

n/m * [p* (m+1)+ (1-p)*1]=np+n/m

در الگوریتم اول که همه را تست می‌کند n تا تست کلاً داریم، پس نسبت این دو حالت می‌شود:

p+1/m = [1-(1-k/n)^m]+1/m

پس جواب اینکه در چه صورتی الگوریتم دوم بهتر است معادل وقتهایی است که عبارت بالا کمتر از ۱ باشد.

در مقابل جمله‌ی اول می‌توانیم از دومی صرف نظر کنیم چون صورت سوال هم گفته خیلی بهتر بشود. برای زیاد کردن (1-k/n)^m باید m را تا جای ممکن کم کنیم چون عدد 1-k/n بین ۰ و ۱ است و هر چه توانش کمتر باشد بزرگتر می‌شود. این مقدار m=2 است (چون به ازای ۱ می‌شود همان الگوریتم اول).

قسمت سوم) طبق قسمت قبل می‌شود:

n/2+n(1-(1-k/n)^2)=3n/2-n(1-k/n)^2

سوال ۳- الف) در هر حالت باید به یک ترتیبی یالها را فشرده کند پس می‌توانیم دقیقاً همان اثبات قبلی را تکرار کنیم تا جایی که k تا رأس بماند. تعداد مراحل می‌شود n-k چون n تا رأس داریم و هر بار که دو تا را با هم ادغام می‌کنیم (با فشرده کردن یال) یکی از تعداد رأسها کم می‌شود. احتمال اینکه یک یال در i مرحله‌ی اول فشرده نشود همان F_i اثبات کتاب است. به جای حساب کردن F_{n-2} ما باید F_{n-k} را حساب کنیم. با همان روش کتاب می‌رسیم به:

prod_{i=1}^{n-k} (n-i-1)/(n-i+1) = (n-2)/n ... (k-1)/(k+1)

= (n-2) ... (k-1) / [ n ... (k+1) ] = k (k-1) / [ n (n-1) ]

احتمال اینکه با اجرای الگوریتم روی k به یک min-cut برسیم طبق قضیه کتاب 2/(k(k-1)) است. اگر آن را L بار تکرار کنیم و بهترین جوابش را در نظر بگیریم، احتمال اینکه جواب به دست نیاید می‌شود:

(1-2/k(k-1) )^ L <= e^{-2L/k(k-1)}

پس احتمال موفقیتش حداقل می‌شود:

1-e^{-2L/k(k-1)}

در مقدار زنده ماندنش در مراحل قبلی ضرب کنیم به دست میاد:

k (k-1) / [ n (n-1) ] * [1-e^{-2L/k(k-1)} ]

ب) ما در قسمت اول که n-k تا از فشرده‌سازی‌هایمان را استفاده کردیم، پس 2n-(n-k) = n+k تای دیگر باقی می‌ماند. یک نسخه‌ی k رأسی به x-2 تا فشرده‌سازی نیاز دارد که یک یالش باقی بماند (منظور از x تعداد یالهای min-cut است، یعنی همان چیزی که در کتاب اسمش را k گذاشته بود). به لطف این قید می‌توانیم برای L کران پیدا کنیم، یعنی (n+k)/x. واضح است که هر چقدر تعداد تکرارها بیشتر باشد جوابش بدتر نمی‌شود در نتیجه ما L را هر چه نزدیک‌تر به این مقدار بگذاریم بهتر است، ولی ما تنها کرانی که می‌توانیم روی x داشته باشیم همین است که از k کمتر مساوی است پس

L=(n+k)/k = n/k+1

با جایگذاری این مقدار در عبارت قسمت قبل به دست می‌آید:

k (k-1) / [ n (n-1) ] * [1-e^{-2(n/k+1)/k(k-1)} ]

به ظاهر عبارتش میاد که اگر k=n بگذاریم بهترین جوابش است. با این کار مقدار زیر به دست می‌آید:

1-(1-2/n(n-1) )^2 ~ 4/n^2

خودش در راهنمایی سوال یک تقریب (هم‌ارزی) استفاده کرده است که ما هم با فرض ثابت بودن L می‌توانیم همین را استفاده کنیم:

1-(1-2/k(k-1) )^{n/k+1} = 2(n/k+1)/k^2

k (k-1) / [ n (n-1) ] * [2(n/k+1)/k^2] =k^2 * n / [ n^2 * k^3] = 1/(nk) = 1/n^2

الگوریتم تصادفی استنفورد

http://theory.stanford.edu/~valiant/teaching/CS265_2018/index.html
سوالهای تمرین این درس روی سایتش هست که احتمالاً در سری جدید شروع می‌کنم به حل کردن اینها. چون اکثر کامنت‌هایی که برای مطالب وبلاگ‌ها می‌گیرم درخواست حل سوالهاست.

اسپنرها، رسم گراف و داده‌های متحرک

درس هندسه محاسباتی پیشرفته دکتر آبام:
http://ce.sharif.edu/courses/96-97/2/ce795-1/index.php

جزوه الگوریتم موازی (ETH)

http://people.csail.mit.edu/ghaffari/CHParallel18.pdf

Solving Linear Programs in the Current Matrix Multiplication Time

https://arxiv.org/pdf/1810.07896.pdf

ساده‌سازی مسیر

منبع: https://conference.imp.fu-berlin.de/eurocg18/download/paper_25.pdf

یکی از مسئله‌های مشهور هندسه محاسباتی ساده‌سازی مسیر است. هر چند که اکثراً در فیلدهای دیگر از آن استفاده می‌کنند.
در این مسئله یک دنباله از نقاط به ما داده شده است و هدف این است که یک زیردنباله از آن را انتخاب کنیم به طوری که فاصله‌ی بین مسیر اولیه و مسیر ساده شده کمینه بشود. ملاک‌های فاصله‌ی زیادی بین مسیرها تعریف شده‌اند، مثل فاصله عمودی، فاصله هاسدورف، فاصله فرشه.
یکی از الگوریتم‌های مشهور در این زمینه الگوریتم Imai-Iri بود که روی رأسهای مسیر یک گراف می‌ساخت که وزن یال‌های آن فاصله‌ی بین خط مستقیم بین دو رأس با دنباله‌ای بود که شروع و پایانش دو سر این یال بودند.
در فاصله‌ی فرشه، ما سرعت حرکتمان روی مسیرها را تغییر می‌دهیم به طوری که بیشترین فاصله‌ی بین دو نقطه متناظر مسیرها مینیمم بشود. اکثراً این تعریف را با دو تا متحرک که هر کدام روی یکی از این مسیرها حرکت می‌کنند نشان می‌دهند. من خودم پیشنهادم اسب/خر و صاحبش است که طول افسار می‌شود فاصله‌ی فرشه. ولی در نسخه‌ی خارجی مسئله سگ و طناب متصل به قلاده‌اش است.
حالا نکته‌ای که در مورد این مسئله پیش می‌آید این است که جواب Imai-Iri الزاماً بهینه نیست. یعنی درست است که ما فقط اجازه داریم از یالهای مسیر استفاده کنیم، اما ممکن است فاصله‌ی فرشه بین یک رأس و یک نقطه روی یک یال رخ بدهد.

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

سوالی که به نظرم جا دارد روی آن بیشتر بحث بشود این است که اگر اجازه داشته باشیم خودمان روی یک نقطه از مسیرهای قبلی رأس اضافه کنیم، آیا می‌شود ساده‌سازی با طول کمتری پیدا کرد یا نه؟

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

asymptotic PTAS (APTAS)

من نشنیده بودم، گفتم شاید شما هم نشنیده باشید!
http://chekuri.cs.illinois.edu/teaching/fall2006/lect6.pdf

تبدیل tex به فایل متنی (مثل word)

با کمک ابزار زیر می‌توانید تبدیل را انجام بدهید:
https://blog.philippklaus.de/2010/11/use-pandoc-to-convert-latex-to-markdown/
علاوه بر تبدیل به متن، به html و موارد دیگر هم تبدیل می‌کند.

یک بسته هم هست که می‌گوید این کار را انجام می‌دهد ولی من امتحان نکردم:
https://www.ctan.org/pkg/detex

وقتی استادت میگه همه‌ی اینها را جایگزین کن و تو عبارت منظم بلدی...

جایگزین کردن همه‌ی $TXT$ با \lr{TXT} برای حداقل ۲ حرف.
\$([A-Z][A-Z]+)\$
\\lr\{\1\}
در Notepad++ این کار را کردم.
راهنمای عبارت‌های منظم Notepad++:
http://docs.notepad-plus-plus.org/index.php/Regular_Expressions

آپلود تصویر بیان کار نکرد که عکسش را بگذارم. :|