من پت هستم

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

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

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

روش بسیار ساده و معمول برای نگهداری رمز کاربرها بر روی سرور به این صورت است که رمز از یک تابع هش (۱، ۲) رد می‌کنند و به این ترتیب رمز تبدیل به یک رشته‌ی تقریبا تصادفی تبدیل می‌شود که و دیگر زیاد به درد جناب کارمند ناراضی نمی‌خورد. هر موقع هم که خواستید رمز یک کاربر را چک کنید کافی است که رمز وارد شده را از همان تابع هش رد کنید اگر نتیجه با مقدار ذخیره شده یکی بود، رمز درست وارد شده وگرنه که نه.  آخه کاری داشت این الگوریتم؟

پس‌نوشت۱: این روشی که بالاتر گفتم صرفا یک روش ساده و ابتدایی است و نمی‌شود بدون در نظر گرفتن شرایط مساله از آن استفاده کرد.
پس‌نوشت۲: روش احراز هویتی که خیلی از سایت‌های معروف (گوگل، فیسبوک، توییترِ‌، فلیکر و ...) استفاده می‌کنند تقریبا اپن-سورس است و مشابه‌اش را می توانید در OAuth ببیند.

فرض کنید n تا توپ قرمز داریم و m تا توپ آبی. توپ‌ها را می‎‌ریزیم توی یک کلاه. حالا اگر یک توپ را به صورت تصادفی برداریم احتمال قرمز بودن توپ چقدر می‌شود؟

جواب ساده است، احتمال قرمز بودن توپ می‌شود $\frac{n}{m+n}$  مثلا اگر ۲ تا توپ قرمز داشته باشید و ۳ تا توپ آبی، احتمال برداشتن یک توپ قرمز ۰/۴۰می‌شود.

*- حالا اگر من یک توپ از درون کلاه بردارم و بدون نگاه کردن به رنگ توپ بخواهم یک توپ دیگر بردارم، احتمال قرمز بودن توپ بعدی چقدر است؟

*- حالا اگر من اول k توپ بردارم و بدون نگاه کردن به رنگ‌‌شان بخواهم توب k+1 را بردارم. توپ k+1 با چه احتمالی قرمز خواهد بود؟

این مساله خواص جالبی داره، که بعدا در مورد آن‌ها خواهم نوشت.

پرده‌ی اول:

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

پرده‌ی دوم:

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

پرده‌ی سوم:

اما خواندن قسمت سوم برمی‌گرده به دوران دانشجویی! حالا ملت چی می‌خوندند ما چی می‌خواندیم بماند . اما به لطف وبلاگ‌های فارسی که اون موقع تازه جون گرفته بودند و گوگل هم اون‌ها را کم-کم-ک توی نتایج جستجو نشان می‌داد, توانستم بفهمم که اسم قسمت داستان «برکه‌ی آتش» است و آن را خواندم.

و امروز:

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

پس نوشت: ظاهرا یک قسمت دیگر هم بوده (لینک) بروم پیداش کنم و بخوانمش

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

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

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

بالاخره امروز موفق شدم که با رییس کوچک (شنگول) یک قرار ملاقات بگذارم. فکر کن یک هفته بدوی و ایمیل بزنی برای یک قرار ۱۰ دقیقه‌ای!

Click the image to see it in the original size

Originally from: http://herbsutter.com/2012/01/10/map-of-c/

صورت مساله را می‌توانید اینجا و یا اینجا ببینید.

و اما جواب مساله‌ی اول:

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

فرض کنید فقط می‌خواستیم جمع اعداد کوچک‌تر از ۱۰۰۰ را که بر ۳ بخش‌پذیرند را محاسبه کنیم ( $S_3$)

$S_3 = 3+6+...+999 = 3*(1+2+...333) = 3*\frac{333*334)}{2}=166833$

و اگر فقط می‌خواستیم جمع اعداد کوچک‌تر از ۱۰۰۰ را که بر ۵ بخش‌پذیرند را محاسبه کنیم ( $S_5$)

$S_5 = 5+10+...+995 = 5*(1+2+...199) = 5*\frac{199*200)}{2}=99500$

حالا، اگر به جمع $S_3$  و $S_5$ نگاه کنیم می‌بینیم که این تقریبا همان چیزی است که به دنبال آن بوده‌ایم. تنها تفاوت در این است که اعدادی مانند ۱۵ و ۳۰ و ... را ۲ بار جمع زده‌ایم که باید اصلاح‌شان کنیم. پس حاصل جمع مورد نظر ما می‌شود: ۲۳۳۱۶۸

$S=S_3+S_5-S_{15} =166833+99500-33165=233168$

صورت مساله‌ی ۱

مجوعه‌ی اعداد طبیعی کوچک‌تر از ۱۰ که بر ۳ و ۵ بخش‌پذیراند شامل ۳، ۵، ۶ و ۹ است و حاصل جمع این اعداد ۲۳ است. حالا شما مجموع تمام اعضای مجموعه‌ی اعداد طبیعی کوچکتر از ۱۰۰۰ را که بر ۳ و ۵ بخش‌پذیرند را بدست آورید؟

خوب این اول مساله بود، خیلی آسان و برای دست‌گرمی. منتظر مسایل جالب‌تر باشید

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

پروژه‌ی اویلر، مجموعه‌ای مساله‌های جالبی که اگر اهل برنامه‌نویسی باشید احتمالا می‌تواند تا مدت‌ها شما را سرگرم کند. یک نگاهی بیندازید جالبه

http://projecteuler.net