الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

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

بایگانی

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
۰ نظر موافقین ۰ مخالفین ۰ ۰۳ اسفند ۹۷ ، ۱۸:۳۲
سپیده آقاملائی
http://people.csail.mit.edu/ghaffari/CHParallel18.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۱۲ بهمن ۹۷ ، ۰۷:۳۶
سپیده آقاملائی
https://arxiv.org/pdf/1810.07896.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۲۳ آبان ۹۷ ، ۱۷:۲۹
سپیده آقاملائی
منبع: https://conference.imp.fu-berlin.de/eurocg18/download/paper_25.pdf
یکی از مسئله‌های مشهور هندسه محاسباتی ساده‌سازی مسیر است. هر چند که اکثراً در فیلدهای دیگر از آن استفاده می‌کنند.
در این مسئله یک دنباله از نقاط به ما داده شده است و هدف این است که یک زیردنباله از آن را انتخاب کنیم به طوری که فاصله‌ی بین مسیر اولیه و مسیر ساده شده کمینه بشود. ملاک‌های فاصله‌ی زیادی بین مسیرها تعریف شده‌اند، مثل فاصله عمودی، فاصله هاسدورف، فاصله فرشه.
یکی از الگوریتم‌های مشهور در این زمینه الگوریتم Imai-Iri بود که روی رأسهای مسیر یک گراف می‌ساخت که وزن یال‌های آن فاصله‌ی بین خط مستقیم بین دو رأس با دنباله‌ای بود که شروع و پایانش دو سر این یال بودند.
در فاصله‌ی فرشه، ما سرعت حرکتمان روی مسیرها را تغییر می‌دهیم به طوری که بیشترین فاصله‌ی بین دو نقطه متناظر مسیرها مینیمم بشود. اکثراً این تعریف را با دو تا متحرک که هر کدام روی یکی از این مسیرها حرکت می‌کنند نشان می‌دهند. من خودم پیشنهادم اسب/خر و صاحبش است که طول افسار می‌شود فاصله‌ی فرشه. ولی در نسخه‌ی خارجی مسئله سگ و طناب متصل به قلاده‌اش است.
حالا نکته‌ای که در مورد این مسئله پیش می‌آید این است که جواب Imai-Iri الزاماً بهینه نیست. یعنی درست است که ما فقط اجازه داریم از یالهای مسیر استفاده کنیم، اما ممکن است فاصله‌ی فرشه بین یک رأس و یک نقطه روی یک یال رخ بدهد.
البته برای فاصله‌ی فرشه گسسته باید هنوز جواب بدهد، چون آنجا دیگر فقط فاصله‌ی بین نقاط را در نظر می‌گیریم. مقاله‌ی منبع هم یک راه‌حل با استفاده از برنامه‌ریزی پویا ارائه داده است.
سوالی که به نظرم جا دارد روی آن بیشتر بحث بشود این است که اگر اجازه داشته باشیم خودمان روی یک نقطه از مسیرهای قبلی رأس اضافه کنیم، آیا می‌شود ساده‌سازی با طول کمتری پیدا کرد یا نه؟
البته مهم‌تر از آن پیدا کردن راه‌حل برای ساده‌سازی مسیر با فاصله‌ی فرشه و کمینه کردن خطا است. چون اکثر الگوریتم‌ها فقط به کمینه کردن تعداد رأسهای مسیر می‌پردازند (و خطا را ثابت می‌گیرند). برای محاسبه‌ی فاصله‌ی فرشه می‌گویند با باینری سرچ روی مقادیر خطا (اپسیلون) مسئله را حل کنید، اما برای ساده‌سازی مسیر مطمئن نیستم جواب بدهد.
۰ نظر موافقین ۰ مخالفین ۰ ۲۰ آبان ۹۷ ، ۱۴:۱۹
سپیده آقاملائی
من نشنیده بودم، گفتم شاید شما هم نشنیده باشید!
http://chekuri.cs.illinois.edu/teaching/fall2006/lect6.pdf
۰ نظر موافقین ۰ مخالفین ۰ ۳۰ مرداد ۹۷ ، ۰۸:۴۴
سپیده آقاملائی
با کمک ابزار زیر می‌توانید تبدیل را انجام بدهید:
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
آپلود تصویر بیان کار نکرد که عکسش را بگذارم. :|
۰ نظر موافقین ۰ مخالفین ۰ ۲۸ خرداد ۹۷ ، ۰۹:۵۰
سپیده آقاملائی