سخنرانی‌ها :: مباحث الگوریتمی

https://en.wikipedia.org/wiki/Bootstrap_aggregating
http://www.ibm.com/support/knowledgecenter/SSLVMB_22.0.0/com.ibm.spss.statistics.algorithms/alg_bootstrap.htm

۰ نظر

۰ ۰۴ دی ۹۵ ، ۲۳:۵۳

سپیده آقاملائی

Dynamic Graph Connectivity in polylogarithmic worst case time

http://webhome.cs.uvic.ca/~val/Publications/SODA13slides.pdf

۰ نظر

۰ ۱۴ مهر ۹۴ ، ۱۴:۴۵

سپیده آقاملائی

نظریه ماتروید (تعریف ماتروید)

ماتروید ویژگی بردارهای مستقل را مدل می‌کند.

تعریف مجموعه‌ی مستقل:

یک مجموعه‌ی S و تعدادی از زیرمجموعه‌های آن را انتخاب کنیم که:

۱- هر زیرمجموعه‌ی زیرمجموعه‌ی انتخاب شده را انتخاب کنیم. (ناشی از ترکیب خطی)

۲- اگر دو مجموعه‌ی مستقل داشته باشید که یکی بزرگتر از دیگر است می‌توانید به مجموعه کوچکتر اضافه کنید که بزرگتر شود. (ناشی از نظریه مجموعه‌ها)

مثال:

2^S

طبق تعریف مجموعه‌های مستقل یک ماتروید است.

مثال ۲:

S= {a,b,c}

I = {همه‌ی کمتر مساوی ۲ عضوی‌ها}

هست. {b} و {a,c} را در نظر بگیرید. می‌توانیم a یا c را به b اضافه کنیم و همچنان در جواب هست.

مثال: ستون‌های ماتریس = S

v1 v2 v3 v4 v5

1 1 1 1 0

0 0 0 1 1

0 1 1 1 1

I= بردارهای مستقل خطی =

{{v1},{v1,v2},...}

گاهی روی ماترویدها مسایل ان‌پی-کامل را می‌توان چندجمله‌ای حل کرد.

همه‌ی تعریف‌های ماتروید معادلند.

* تعریف بر اساس پایه (basis):

پایه = کمترین تعداد بردار که بتوانند بقیه را بسازند. (اما از این تعریف نمی‌توانیم استفاده کنیم چون همه معنی ندارد.)

= بزرگترین مجموعه‌ی مستقل خطی

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

در مثال اول: {a,b,c}

در مثال دوم: همه‌ی زیرمجموعه‌های دو عضوی

قضیه: همه‌ی پایه‌ها تعداد اعضایشان مساوی است.

برهان خلف:

|A| < |B|

پس می‌شود اندازه‌ی A را با اضافه کردن از B\A بزرگ کرد که این با ماکسیمال بودن A تناقض دارد.

*تعریف ماتروید با پایه:

B1) مجموعه‌ی B تهی نباشد.

B2) اگر یک عضو از A را حذف کنیم و به جای آن یک عضو از B را به A اضافه کنیم نتیجه باز هم ماتروید باشد.

اثبات: برهان خلف. اگر |A|<|B| باشد، می‌توانیم انقدر عضوها را یکی یکی اضافه کنیم تا کل B را شامل شود که با ماکسیمال بودن B تناقض دارد.

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

* تعریف با تابع رتبه (Rank Function):

تابعی می‌دهند که از روی آن ماتروید را می‌سازیم.

rank یک مجموعه، بعد فضایی است که می‌سازد. مثلاً ۳ بردار {غیر هم خط} در صفحه rankشان ۲ است.

همان ستون‌های ماتریس v1,...,vn باشند، آنگاه

r{v1,...,vn} = فضایی که آنها می‌سازند چندبعدی است.

رتبه مجموعه تهی صفر است.

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

اگر A زیرمجموعه‌ی B باشد رتبه‌ی A از B کمتر مساوی است.

تعریف ماتروید با تابع رتبه:

R1) r(A) >= 0

R2) r(A)+r(B) >= r(A u B) + r(A^B)

تبدیل از تعریف با تابع رتبه به تعریف با مجموعه‌های مستقل:

I = {T \subset S: r(T) = |T|}

... (خیلی خسته‌کننده است بعداً بقیه‌اش را شاید نوشتم.)

۱ نظر

۰ ۰۲ مهر ۹۴ ، ۰۸:۴۶

سپیده آقاملائی

On symmetric and choiceless computation (کنفرانس TTCS)

Mechanization of Abstraction (Aho, Ullman)

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

کلاس FPC:

شبیه ماشین تورینگ اما با جدولی مانند پایگاه داده یک ماشین می‌سازیم به نام ماشین رابطه‌ای (relational machine) که در زمان چندجمله‌ای مسایل کلاس FP<P را تصمیم می‌گیرد. انواع مختلفی از این ماشین هست:

abiteboul, vardi, .. + counting

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

P-Complete < FPC

در سال ۲-۱- Grohe ثابت کرد که مسایل P که proper minor-closed class of graph هستند زیرمجموعه‌ی FPC هستند.

LPها (برنامه‌ریزی خطی) زیرمجموعه‌ی FPC هستند.

آنهایی که CFI property را دارند زیرمجموعه‌ی P هستند اما زیرمجموعه‌ی FPC نیستند. {در نتیجه P و FPC یکی نیستند.}

*Abstract state machineها از ماشین‌های رابطه‌ای قوی‌تر هستند چون اجازه‌ی مواردی مانند مجموعه‌ها، مجموعه‌ای از مجموعه‌ها و .. را می‌دهند. این ماشین‌ها در زمان چندجمله‌ای مسایلی را تصمیم‌گیری می‌کنند که به آنها Choiceless Polynomial Time می‌گویند. زمان این ماشین با تعداد گام‌های آن اندازه‌گیری می‌شود و حافظه‌ی آن با تعداد مجموعه‌ها.

می‌دانیم FPC < CPT است اما نمی‌دانیم چه رابطه‌ای با P دارد.

*مدارها برای مسایل گراف (Circuits for graph problems)

گراف با ماتریس مجاورت آن داده می‌شود. چیزی به نام Invariant Circuits داریم که جایگشت دادن رأسهای ورودی، خروجی را تغییر نمی‌دهد. پس FPCها زیرمجموعه‌ی این کلاس هستند.

* Polynomial Time Graph Properties

با مدارهای متقارن که زیرمجموعه‌ی مدارهای invariant هستند می‌شود تشخیص داد. مثالی از مداری که متقارن نیست اما invariant هست مدل آبشاری (اگر اسمش را اشتباه نگویم) است که در آن مثلاً برای به دست آوردن or همه خروجی قبلی‌ها را با عدد بعدی می‌گیریم. (یک درخت با ارتفاع n)

جایگشت‌هایی که گیت g را به خودش می‌برند را stabilizer group of g می‌نامیم.

تعداد مدارهای متقارن برابر است با:

n! / |stab(g)|

* مسئله‌ی pebble game (bijection game) در سال ۹۶ توسط Hella

* 3-SAT عضو FPC نیست (با CFI ثابت می‌شود).

این نتایج هیچ فرضی برای P vs. NP نیاز ندارند.

یک سری لیست مطالب هم هست که چون در پست‌های قبلی اسلاید اصلی ارائه هست دوباره نمی‌نویسم. مثلاً ۲-رنگ پذیری در این کلاس هست اما ۳-رنگ پذیری نیست. ۲-sat هست اما 3-sat نیست. ...

سوالی که من پرسیدم که چه کتابی در مورد این هست یک کتاب ۱۹۹۹ معرفی کردند که در کتابچه‌ی TTCS هست.

۰ نظر

۰ ۰۲ مهر ۹۴ ، ۰۸:۰۹

سپیده آقاملائی

جهت‌های جدید در الگوریتم‌های پارامتری (کنفرانس TTCS)

در اکثر مسایل ساختارهایی در داده‌ها هست که کمک می‌کند برخلاف الگوریتم‌هایی که فقط به n بستگی دارند، بدون نیاز به حل P vs. NP مسئله را حل کنیم.

مثلاً مسئله‌ی Multiple Sequence Alignment را می‌توان در O(2^n^c) حل کرد و NPC است اما در عمل پارامترهایی مانند طول، میزان تطابق، تعداد حروف الفبا می‌توانند کوچک باشند که می‌توان مسئله را در زمان زیر حل کرد:

2^N+2^|Sigma|+2^delta+2^(1/epsilon)

مسایل دو دسته هستند:

۱- پارامتر ثابت (FPT) هستند که این خودش دو نوع multiplicative (که در آن زمان f(k)n^c است) و additive (که در آن زمان f(k)+n^c است) دارد.

۲- مسایل w-hard و XP که زمان آنها n^g(k) است.

اولین بار که الگوریتم‌های پارامتر ثابت ارائه شدند همه اعتراض کردند که نمایی بر حسب k در کنار n قابل قبول نیست.

این مسئله اولین بار برای Type Checking در زبان ML استفاده شد که آنجا پی بردند که الگوریتم‌هایی که در عمل به کار می‌روند بر خلاف تحلیل تئوری آنها خوب جواب می‌دهند. این مسئله NP-hard است ولی الگوریتم پارامتر ثابت با زمان O(2^k n) دارد که در آن k عمق typeها و n طول برنامه است.

امروزه مسئله‌ی مهم‌تری مطرح است. الگوریتم RSA را یک Quantum Computer با variantای از الگوریتم Shore می‌تواند حل کند. برای RSA به ضرب دو عدد اول نیاز است. فاصله‌ی همینگ بین دو عدد اول همیشه ۱ یا ۲ است که این همان پارامتر ثابتی است که برای شکستن RSA به کار می‌آید. (یک چیزی هم در مورد فاکتور گیری اعداد نوشتم که الآن یادم نیست چی است.)

معمولاً brute force روی پارامتر می‌زنند اما برای بعضی مسایل مانند پوشش رأسی می‌شود کارهای بهتری هم کرد. روش bounded search tree را به کار می‌بریم. از یال u-v یا باید u را برداریم یا v را. پس در زمان O(2^k n) مسئله حل می‌شود.

یک چیزی در مورد minor graph algorithm.

سلسله مراتب مسایل پارامتری:

P < FPT < M[1] < W[1] <... <W[2]< ... < XP

مثالهای مسایل هم پوشش رأسی برای FPT، خوشه برای W[1]، مسئله‌ی dominating set برای w[2] است.

برای اثبات این مسایل به کاهشی نیاز داریم که پارامتر را کنترل می‌کند. برای سلسله مراتبی که گفته شد، مثلاً ثابت کرده‌اند که اگر dominating set پارامتر ثابت باشد، clique (خوشه) هم پارامتر ثابت است.

به جای قضیه‌ی cook-levin از قضیه‌ی k-step halting problem استفاده می‌کنند تا w[1] را تعریف کنند. k-clique هم برای w[1] کامل است. (w[1]-complete)

* روش bounded tree width

یک ویژگی مسئله است. مثلاً یک سری از رأس‌ها متناظر متغیرها و یک سری دیگر متناظر عبارت‌ها باشند. مثلاً control flow برنامه‌های ساختیافته. (پشته)

این مسئله را می‌شود با sliding window حل کرد چون یالهای آن دور ندارد. یعنی حداکثر تعداد مقادیری که باید بدانیم تا مرحله‌ی بعدی را بفهمیم کم است. می‌توانیم مثلاً با یک dfs یالهای کوتاه بعدی را پیدا کنیم.

ایده‌ی این روش شکستن ورودی به قطعات کوچکتر است.

در یک بعد نمی‌شود این کار را کرد چون تهش چیزی نمی‌ماند. اما با چند پارامتر می‌شود.

* مسئله‌ی Karsten's trains

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

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

{تا جایی که من می‌دانم این کار را kernelization می‌گویند که بخواهیم اندازه‌ی مسئله را با ساده‌سازی کم کنیم.}

*روشی برای فهمیدن اینکه کرنل با اندازه‌ی چندجمله‌ای وجود دارد یا خیر:

پوشش رأسی و خوشه دوگان یکدیگر هستند. {احتمالاً از نظر اندازه‌ی پارامتر که سایز خروجی است.}

{اشاره‌ی نامعلومی به اسم lanston}

مقایسه‌ی f(k) با اندازه‌ی کرنل.

یک پیش پردازش می‌کنیم تا به کوچکترین مسئله‌ی ممکن برسیم. {این را می‌دانم تعریف kernelization است.}

-cygan, fomina, ...

-multivariate

-fpt newsletter

*مسئله‌ی زمانبندی حساس به گرما (heat sensitive scheduling) که np-hard است در نظر بگیرید. معمولاً گرما یک عدد نیست بلکه بیشتر یک رتبه‌بندی است (مثلاً خیلی سرد، سرد، معمولی، گرم، خیلی گرم) که باعث می‌شود بتوانیم آن را پارامتر بگیریم. که به ما یک الگوریتم پارامتر ثابت می‌دهد.

*رنگ‌آمیزی گراف: حریصانه رنگ کن و اگر از k رنگ بیشتر شد برگرد و با یک روش دیگر رنگ کن.

* تعریف استقرایی عرض درختی (tree-width)

k-graph: افراز رأسها به k مجموعه که عرض هر کدام محدود است.

۱- disjoint union

۲- renaming

۳- fusion

* عرض خوشه (clique width)

۱- مثل قبلی

۲- مثل قبلی

۳- بین ui و uj همه‌ی یالها را می‌سازید (گراف دوبخشی کامل).

cw(G) <= 2^(tw(G)+1)+1

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

۰ نظر

۰ ۰۲ مهر ۹۴ ، ۰۷:۲۹

سپیده آقاملائی

مباحث الگوریتمی

مباحث الگوریتمی

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

نظریه الگوریتمی بازی‌ها

الگوریتم پیشرفته

حل‌های من

پروژه

بهینه‌سازی ترکیبیاتی

الگوریتم‌های پارامتری

درس ارائه شده در دانشگاه‌های دیگر

بهینه‌سازی محدب

الگوریتم‌های داده‌های حجیم