داده کاوی داده‌های حجیم (دانشگاه استنفورد)

http://web.stanford.edu/class/cs246/handouts.html

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

http://web.stanford.edu/~rrwill/cs266.html

در این درس الگوریتم‌های پارامتر ثابت و روش‌های آنها بررسی می‌شوند.

تحلیل سرشکن (پشته)

نحوه‌ی ساخت پشته از پایین به بالا

http://cs.stackexchange.com/questions/11415/how-to-perform-bottom-up-construction-of-heaps

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

پس در مجموع زمان O(n) است پس زمان سرشکن هر عمل O(1) است. (مشابه مثال خرس! می‌توانیم بگوییم که هر بار نصف گره‌های باقیمانده برگ هستند.)

مثال خرس: یک خرس در غار خود گوشت‌های با اندازه‌های 1,...,n دارد و هر روز یا یک گوشت فرد را کامل می‌خورد یا یک گوشت زوج را نصف می‌کند و نصف آن را می‌خورد. خرس اگر هر روز گوشت بخورد زنده می‌ماند. خرس چقدر عمر می‌کند؟

جواب: تحلیل سرشکن زمان 2 را برای هر گوشت می‌دهد. (تعداد روزهایی که خرس را زنده نگه می‌دارد.) پس خرس 2n روز زنده می‌ماند.

T(n) = n+T(n/2) = n(1+1/2+1/4+...) = 2n

(تصاعد هندسی)

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

مستمع آزاد راه نمیدن! :))

این خودش ملاک کیفیت کلاسه. هیچ وقت درسی که ترم اولیه که ارائه میشه برندارید.

سوالهای کنکور دکتری (نرم افزار)

http://www6.sanjesh.org/Download/Doctora93Q/2354.pdf

اصلاً معلوم نیست کیا سوالها رو طرح کردن که! :)

ولی الآن یک سوال برای من پیش اومد اینکه سوالهای الگوریتم رو ما باید جواب بدیم؟ کلش ۴۵ تا سواله ولی ۲۰ تای اولش الگوریتمه! (در ضمن چطوری اونهایی که درس پردازش موازی نگرفتن می‌خوان سوالی مثل سوال 20 رو جواب بدن؟)

حداقل این شد که این اتفاقات اخیر من را مطمئن کرد که نمی‌خواهم توی شریف بمونم. فقط می‌مونه اینکه برم خارج یا برگردم امیرکبیر. با توجه به اینکه دومی آسون‌تر به نظر می‌رسه شاید اون بهتر باشه.

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

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

تست‌ها رو هم زدم بعد دیدم که جواب ندارن! :)) حالا یا می‌گردم جوابش رو پیدا می‌کنم یا خودم حل می‌کنم میذارم یا کلاً یادم میره! :)

نوشتن عدد در مبنای فیبوناچی

در این سوال هدف نوشتن یک عدد با ارقام ۰ و ۱ است که iامین رقم از سمت راست اگر ۱ باشد یعنی Fi (عدد فیبوناچی i-ام) واحد به عدد اضافه می‌شود.

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

می‌خواهیم طوری عدد را بسازیم که زمان یک واحد افزایش و کاهش عدد به صورت سرشکن ثابت باشد. (در صورت سوال گفته درج و حذف که احتمالاً منظورش این بوده است که عدد را به صورت یک رشته در نظر بگیریم، هر چند باز هم معنی حذف و درج با افزایش و کاهش متفاوت است)

حل:

برای کاهش و افزایش یک عدد در مبنای فیبوناچی، چون دو عدد اول در فیبوناچی ۱ هستند، حالتی که یکی از دو رقم ۰ باشد (هنگام افزایش) یا ۱ باشد (هنگام کاهش) به سادگی می‌توانیم با تغییر این بیت عدد را بسازیم.

(این داستان ادامه دارد...)

تحلیل سرشکن (amortized analysis)

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

ولی اگر بخواهیم مستقل از مقدار فعلی شمارنده به دست بیاوریم، زمانش O(1) می‌شود.

روش‌های تحلیل سرشکن:

روش انبوهه (aggregate): جمع هزینه‌ی کل اعمال تقسیم بر تعداد اعمال

روش حسابداری (accounting): یک مخزن پول (تعداد اعمال) داریم و برای هر عمل یک هزینه داریم.

روش تابع پتانسیل (potential function): یک تابع پتانسیل تعریف می‌کنیم و هزینه‌ی هر عمل را به صورت cost+pot(i)-pot(i-1) تعریف می‌کنیم.

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