Balanced Graph Partitioning

http://www.dcs.warwick.ac.uk/~harry/pdf/bpartition.pdf

A Course in Data Intensive Computing

http://www.sics.se/~amir/dic.htm

شبکه‌های جهان کوچک

این مطلب درخواستی یکی از دوستان است! :) برای اینکه مطلب مفهوم‌تر باشد سعی کردم از یک منبع کمک بگیرم!

مرجع: http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch20.pdf

۱- درجه جدایی ۶:

یعنی در گراف آن با طی کردن ۶ یال از هر رأسی می‌توانیم به هر رأس دیگری برسیم.

داستان آن از اینجا شروع شده است که یک نفر یک سری نامه برای چند نفر فرستاده و خواسته که آنها برای یک آدم خاص بفرستند یا به کسی بفرستند که آن فرد را می‌شناسد. و به طور میانگین (expected) با ۶ گام نامه‌ها به مقصد رسیده‌اند.

۲- ساختار و تصادفی بودن:

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

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

مدل Watts-Strogatz:

کافی است فقط تعدادی از افراد در شبکه تصادفی، لینک (یال) به یک فرد دور داشته باشند.

جستجوی غیرمتمرکز:

حالا سوال این است که از یک مبدأ به یک مقصد بدون دانستن لینک‌های تصادفی چطور باید یک بسته را بفرستیم؟

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

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

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

تمرین تقریبی ۲

http://ce.sharif.edu/courses/92-93/2/ce726-1/assignments/files/assignDir17/exercise%202.pdf

کدینگ

کدینگ در شبکه:

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

مثال: دو نفر می‌خواهند پیامشان را از طریق یک سرور ارسال کنند. هر دو پیام را به سرور می‌فرستند و در آنجا xor پیام محاسبه می‌شود و برای هر کس فرستاده می‌شود. با این کار هر دو پیام را با xor کردن با پیام خودشان به دست می‌آورند.

مثال: دو مبدأ می‌خواهند پیامشان را به دو مقصد بفرستند. هر کس وقتی پیام خودش را می‌فرستد، بقیه هم دریافت می‌کنند، اینجا بر خلاف قبل آن را دور نمی‌ریزند. در این صورت وقتی سرور xor پیام را می‌فرستد آنها هنوز قادرند پیام اولیه را به دست بیاورند.

در هر دو مثال بالا تعداد ارسال‌ها از ۴ گام به ۳ گام کاهش داده می‌شود.

کدینگ حافظه:

در پایگاه داده‌ها ما از افزونگی برای جلوگیری از نابودی اطلاعات به دلیل مشکل سخت‌افزاری استفاده می‌کنیم. Reed-Solomon یکی از این روش‌ها است. A+B و A+2B را به جای سه تا نمونه از هر کدام نگه می‌داشت. (اگر دو تا خراب بشه باز هم کار می‌کند.)

الگوریتم:

داده‌ها را به ۱۰ بلوک تقسیم می‌کنیم و با ۵ تا رابطه که هر کدام بر حسب ۵ تا بلوک هستند می‌توانیم جواب مسأله را حساب کنیم. اما می‌توان طوری این روابط را محاسبه کرد که تکراری داشته باشند و نیاز به ۲۵ عمل نداشته باشیم. برای ۲۰ تا رابطه‌ی آن ارائه شد. سوال: آیا کمتر هم می‌شود؟

broadcast در شبکه بیسیم وایرلس

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

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

این مسأله np-hard است.

تقریب مسأله با فرض داشتن اطلاعات محلی: اگر هر گره همسایه‌های خودش را بداند (شعاع ارسال ثابت باشد) می‌توان الگوریتمی با تقریب ثابت برای مسأله ارائه داد.

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

ایراد: ممکن است یک نفر دو بار پیام دریافت کند و این کار ممکن است باعث تداخل و نامفهوم شدن پیام شود.

ارائه‌ی هندسه پیشرفته

انقدر مطمئنم که فردا هیچ کس بهم نمره نمیده اصلاً دلم میخواد نروم ارائه بدهم. همه میان ارائه میدن چرت و پرت هیچی ازش نمیشه فهمید بعد من به اونها نمره کامل میدم اونها به من صفر. این همه کارشناسی که درس رو ندارن میان سر کلاس نمره میدن به ارشدها قطعاً به حساب دوست-رفیق بازیه. آخه کجای دنیا این طوری نمره میدن؟ اصلاً همین که هیچ کس تهش هیچی نمی‌پرسه خودش به قدر کافی گویاست. من هم این ترم نپرسیدم هیچی گفتم کمتر از نمره‌ام کم کنن! :| باز از اعداد تصادفی که هر ترم تولید میشه برای ترتیب ارائه‌ها که بهتره! :| حالا یکی نیست بگه مقاله‌ای که من قراره ارائه بدم که خود شما انتخاب کردید استاد محترم، دیگه چرا وقت ارائه‌ی من رو ۵ دقیقه می‌کنید که نرسم توضیح بدهم؟ اونوقت یکی مثل عزیزکرده کلاس میاد عین مطالب سر کلاس رو تکرار می‌کنه که کاملاً توهین به شعور آدمه و میره. آخرشم من باید از استعدادهای اونها استفاده کنم!!! واقعاً اینجا دانشگاه به درد نخوریه. (از هر جهت)

موضوع ارائه: net & prune روشی برای حل مسائل فاصله اقلیدسی در زمان خطی (expected)

دریافت
حجم: 994 کیلوبایت

Parallel Programming with Microsoft Visual C++

http://msdn.microsoft.com/en-us/library/gg675934.aspx

هنر برنامه‌نویسی با R

من یادم است که برای داده‌کاوی گیر یاد گرفتن R بودیم. لینک دانلود کتاب آموزش R:

http://it-ebooks.info/book/1734/

زبان R بیشتر برنامه‌نویسی است اما RapidMiner بیشتر تصویری و برای کاربردهای عمومی است. پس همان طور که از توضیحات قبلی معلوم است پیاده‌سازی الگوریتم‌های داده‌کاوی جدید با R ممکن است اما با RapidMiner نیست. (البته رپیدماینر یک کامپوننت R دارد که بسیار دردسرساز است و نصب آن باعث می‌شود هیچ قسمت دیگری کار نکند!!)

نظریه پردازش موازی

https://wiki.cites.illinois.edu/wiki/display/cs498tpc/Theory+of+Parallel+Computing