Hadi's personal blog

Adleman, BPP, Modality, Resolution, Davis-Putnam, ... while being Nostalgic.

nospam@example.com (Hadi Moshayedi) — Mon, 31 May 2010 08:36:23 -0400

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

Intuitionistically Faraway

nospam@example.com (Hadi Moshayedi) — Sun, 30 May 2010 13:20:09 -0400

اژدهای شوخ طبع به من سلام کرد، ولی من او را همچنان نادیده گرفتم.

Father of all nerds died when the Search Engine invited again ...

nospam@example.com (Hadi Moshayedi) — Wed, 26 May 2010 15:21:12 -0400

برخی در بازی احتمالاتی زندگی استراتژی همواره برد دارند.

Who Knows? Part 1

nospam@example.com (Hadi Moshayedi) — Sat, 22 May 2010 17:51:33 -0400

1. آیا انسان هرگز می تواند عدم وجود خود را تصور کند؟ چگونه؟ آیا انسان در هنگام فعالیت مغزی می تواند عدم تجربه را تصور کند؟

2. آیا انسان می تواند به مرگ خود یقین داشته باشد؟

CodeForces

nospam@example.com (Hadi Moshayedi) — Sat, 06 Mar 2010 03:36:49 -0500

سلام،
يک سایت مسابقات برنامه نویسی جدیدا ایجاد شده است به نام Codeforces. اگر دوست داشتید سری بزنید. به نظر من که خیلی جذاب است.
يکی از ويژگی های این سایت این است که هر کدام از اعضاء می توانند وبلاگ هم داشته باشند. این لینک وبلاگ من در آنجاست.

IAUM CCC 6 - Online Round 1

nospam@example.com (Hadi Moshayedi) — Sun, 19 Jul 2009 12:42:09 -0400

مسابقه ی آنلاین دوم نیز برگزار شد. سوال های A و D و G را من طرح کرده بودم.

برای دریافت صورت سوال ها به http://pykello.net/iaum-c3-6-1.tar مراجعه کنید.

سوال A، تنها یک پیاده سازی معمولی بود. برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_cheaters مراجعه کنید.

سوال D، یک سوال احتمالاتی بود که از سوال احتمالاتی دفعه ی پیش کمی آسان تر بود. راه حل من برای این سوال از نوع برنامه سازی پویا بود. تنها مشکلی که برخی از شرکت کننده ها داشتند این بود که بعضی جاها 0.00000- چاپ می کردند به جای 0.00000 که چون به نظرم مشکل حادی نبود، یک clarification فرستادم تا ملت این مشکل را درست کنند. برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_quiz مراجعه کنید.

راه حل من برای سوال G جستجوی دودوئی بود. برای اینکه بفهمم آیا با زمان x می شود به هدف رسید، ترتیب های مختلف نقاط را امتحان می کردم. مکان هندسی که هر کدام از نقاط در زمان x می توانند به آن بروند یک دایره است. اگر اشتراک تمام این دایره ها ناتهی بود، با زمان x می شود به هدف رسید، وگرنه نمی شود. برای دیدن کد من برای این سوال، به http://wiki.pykello.net/doku.php?id=implementation:iaumc3_atoms مراجعه کنید.

لطفا نظرتان را درباره ی سوال ها به صورت کامنت یا ایمیل ارسال کنید.

پ.ن. : ایده ی سوال G برگرفته از http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3159 بود، که توضیح راه حل را می توانید در http://wiki.pykello.net/doku.php?id=zju:feburary09 پیدا کنید. دلیلی که باعث شد فکر کنم تغییر من بر روی این سوال تبدیل به یک سوال جدید جالب می شود، این بود که گمان می کردم قسمت اشتراک دایره ها سخت ترین بخش سوال است، و راه حل های اولی که به ذهنم رسیده بود هم سخت بود، ولی راه حل آخرم چندان هم سخت نبود :)

در ضمن، نمی دانم چرا سوال B با اینکه سخت نبود تنها توسط یک نفر حل شد.

IAUM CCC 6 - Online Round 0

nospam@example.com (Hadi Moshayedi) — Fri, 17 Jul 2009 12:03:41 -0400

امروز مسابقه ی آنلاین اول IAUM CCC 6 برگزار شد. سه سوال از 7 سوال توسط من طرح شده بود. در این پست، ابتدا انتقاداتی از طرز انتقاد مسابقه دهندگان می کنم، و سپس به توضیح کوتاهی در باره ی سوال ها می پردازم.

سه سوال A و B و G توسط من طرح شده بود. برای دریافت صورت سوال ها، به آدرس http://pykello.net/iaumc3-6-0.tar مراجعه کنید. البته صورت سوال B در مسابقه یک اشتباه تایپی داشته که در این نسخه درست شده است.

سوال A مشکل خاصی نداشت، راه حل من که سعی کردم کندترین راه حل معقول باشد( از مرتبه ی زمانی (O(n^2 بود)، در کمتر از یک ثانیه اجرا می شد. سوال آسانی بود، و وقتی کد طولانی برخی شرکت کنندگان را دیدم بسی تعجب کردم. و واقعا چگونگی دست یافتن برخی شرکت کننده ها به نتیجه ی Time Limit Exceeded واقعا حیرت آور بود. به هر حال، عده ای به طرز Judge شدن این سوال معترض بودند که دلیلش را نمی دانم. من هم جزو Judge ها نبودم تا دلیل اعتراض آن ها را بدانم. داده های تست مشکلی نداشت. تعداد زیادی از افراد با اینکه در صورت سوال ذکر شده بود نقطه ای با مختصات (0,0) در ورودی نیست، باز هم وجود چنین نقطه ای را سوال می کردند.

سوال B ... معترضین به این سوال سه دسته بودند. دسته ای که معنی "متوسط" را بلد نبودند، و صورت سوال را مبهم می دانستند. اولا اینکه در صورت تمایل دوستان، می توانم بیش از 10 سوال مشابه پیدا کنم که بدون تعریف معنی متوسط، مقدار متوسط را خواسته بودند. پس اینکه تعریف "متوسط" را شخصی بلد نیست، ضعف در صورت سوال محسوب نمی شود. مبهم دانستن این مساله مانند این است که عدم ذکر معنای کوتاه ترین مسیر در مساله ی گراف را دلیل مبهم دانستن آن سوال بدانیم.
دسته ای دیگر، به clarification ها با دقت کافی نگاه نکرده بودند، و با اینکه به تعداد مراتبی زیادی ذکر کردم که k بار شیر افتادن باید "پشت سر هم" باشند، باز هم با اعتماد به نفس این مساله را ندیده می گرفتند و ورودی و خروجی نمونه را اشتباه می دانستند!
دسته ای دیگر، راه حل اشتباهی را انتخاب کرده بودن و مساله را به تعداد تکرار زیادی شبیه سازی کرده بودند، و مسلما جواب اشتباه می گرفتند. جالب این بود که انصاف را رها کرده بودند، و چون از 2-3 سوال دیگر و همچنین از نتیجه ی خودشان ناراضی بودند، با اعتماد به نفس زیادی می گفتند: "سوال گیر الکی داشت". مطمئنا کسانی که راه حل درست را پیدا کرده بودند، به مشکل خاصی برنخوردند.

سوال G، تقریبا کسی به طور جدی به این سوال نپرداخت، با اینکه از لحاظ ایده ای سخت نبود، ولی شاید پیاده سازی اش کمی طول می کشید و سوال های دیگر زمانی برای این سوال باقی نگذاشته بودند.

در باره ی ایده ها:

تنها به توضیح مختصری و کدها بسنده می کنم. ممکن است در آینده توضیح بیشتری بنویسم!

سوال A: برای دیدن کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_sight مراجعه کنید. تنها نکته ای باید در نظر می گرفتید این بود که مثلا اگر دو نقطه در (1,1) و (1-,1-) قرار داشته باشند، هر دو نقطه را می بینیم، با اینکه نسبت x/y هر دو یکسان است.

سوال B: برای مشاهده کد من برای این سوال به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_kconsecutive مراجعه کنید.

کسانی که با معنای "متوسط" یا "امید ریاضی" در نظریه ی احتمال آشنا نیستند، به http://en.wikipedia.org/wiki/Expected_value مراجعه کنند.

فرض کنید [expDays[i برابر با تعداد متوسط روزهای لازم برای اینکه عمل سکه انداختن تمام شود با فرض اینکه i دفعه ی قبلی نتیجه سکه انداختن ها شیر بود، باشد. همانطور که معلوم است، expDays[k] = 0 است، چون k بار شیر پشت سر هم رخ داده است و بازی تمام شده است. در غیر اینصورت، expDays[i] = expDays[i+1] * p + expDays[0] * (1-p) + 1 است. عدد 1، برای این است که حتما یک بار سکه پرتاب می کنیم. با احتمال p، به حال [expDays[i+1 میرویم، یعنی به تعداد شیرهای پشت سرهم یکی اضافه می شود. و با احتمال q=1-p، به حالت [expDays[0 می رویم، یعنی تعداد شیرهای پشت سرهم به صفر می رسد. تابع calcDays در واقع این دنباله را محاسبه می کند. تابع calcMoney نیز از روشی مشابه ولی کمی پیچیده تر برای محاسبه متوسط پول استفاده می کند.

سوال G: برای مشاهده ی کد من برای این سوال، به http://wiki.pykello.net/doku.php?id=implementation:iaum_c3_6_grid مراجعه کنید.

راه حل مطلوب این سوال، از نوع برنامه سازی پویا بود. حالت برنامه سازی پویا نیز (شماره سطر، شماره ستون، بیت های لازم از وضعیت سطر بالا، بیت های لازم از وضعیت سطر فعلی) است. اگر این مدل را بصورت بدیهی پیاده سازی کنید، مسلما تعداد حالات خیلی زیاد خواهد بود. ولی باید دقت کنید در این مساله وضعیت سطری به طول n حداکثر می تواند (F(n) = F(n-1) + F(n-3 حالت داشته باشد، که برای n=30، کمتر از 500000 حالت می شود که زیاد نیست. با کمی طراحی خوب، می توان در بدترین حالت در زمان کمتر از 2 ثانیه به هر ورودی جواب داد.

خوب :) دوست دارم نظرتان در باره ی سوال ها را بدانم. لطفا کامنت یا ایمیل ارسال کنید!

Hava kara bulutlu ...

nospam@example.com (Hadi Moshayedi) — Wed, 15 Jul 2009 06:36:27 -0400

در آن عصر هنگام من مُردم،
ولی پس از مرگ من معجزه ای رخ داد،
و به زندگی جاودانه دست یافتم و باور کردم که مرگ پایان دنیا نیست،
و من هرگز این معجزه را فراموش نخواهم کرد.

Topcoder SRM 444

nospam@example.com (Hadi Moshayedi) — Thu, 09 Jul 2009 08:36:34 -0400

عملکرد من در این مسابقه خوب نبود، ولی بد هم نبود. البته نسبت به دو مسابقه قبل خیلی بهتر بود :)

در سوال 250 امتیازی، نسبتا خوب عمل کردم و سعی کردم با دقت بنویسم و در نتیجه نسبتا کند نوشتم. سوال نسبتا آسانی بود، ولی در مقایسه با اکثر سوال های 250 امتیازی سخت تر بود و دقت بیشتری می خواست.

در سوال 500 امتیازی، سوال برنامه سازی پویای نسبتا آسان و سرراستی بود، انتظار داشتم بتوانم بیشتر از 400 امتیاز بدست بیاورم، ولی به علت اشتباهاتی نامعلوم، در ورودی های نمونه جواب درست نگرفتم، و پس از تلف کردن زمانی برای دیباگ، بخشی از کد را دوباره نوشتم و حدود 270 امتیاز گرفتم. اشتباه من در این سوال این بود که در جاهایی که می توانستم از تابع استفاده کنم از تابع استفاده نکرده بودم و کد کثیف و غیر قابل فهم شده بود.

با توجه به اینکه این دو سوال نسبتا زیاد طول کشید و زمان زیادی برای سوال سخت باقی نمانده بود، در زمان باقیمانده هر دو سوال را با مقداری ورودی دستی تست کردم و کدشان را دوباره بررسی کردم تا مطمئن شوم مشکلی ندارند.

در مرحله ی Challenge، سعی کردم محتاط باشم، ولی 2 کدی که تشخصیص دادم اشتباه است و می توانستم Challenge کنم، قبل از اینکه من اقدام کنم Challenge شدند. اشتباه من در این مرحله این بود که تعدادی تست خوب آماده نکرده بودم تا بتوانم سریع تر Challenge کنم.

رتبه ام 103 شد، امتیاز تاپکدرم از 2221 به 2242 افزایش پیدا کرد، که تغییر زیادی نبود، و تنها از اینکه نتیجه مثل دو دفعه پیش افتضاح نشده بود راضی بودم. ولی دوست دارم به دورانی برگردم که نصف مسابقات جزو 50 تای اول بودم :)

ZOJ Monthly Contest, June 2009 Analysis

nospam@example.com (Hadi Moshayedi) — Thu, 09 Jul 2009 08:30:25 -0400

برای مشاهده ی توضیح و بررسی سوال های مسابقه ی ZOJ Monthly Contest, June 2009 به http://wiki.pykello.net/doku.php?id=zju:june09 مراجعه کنید. البته هنوز ناقص است، ولی امیدوارم کامل تر کنم :) البته از هر گونه کمکی استقبال می کنم :)

پ.ن. : توضیح سوال D کامل تر شد.

ZOJ Monthly Contest, June 2009

nospam@example.com (Hadi Moshayedi) — Mon, 29 Jun 2009 17:55:26 -0400

دیروز در این مسابقه آنلاین شرکت کردم. با توجه به اینکه با کمی دقت می توانستم جزو 4 تیم اول بشوم (به جای هشتم)، از عملکرد خودم کاملا راضی نبودم، ولی به هر حال بد هم نبود.

در این پست، به عملکرد خود و مقداری به سوال ها می پردازم، ولی بررسی کامل سوال ها را بعدا و هنگامی که همه سوال ها را حل کردم در پستی جداگانه خواهم نوشت :)

ابتدا شروع به خواندن سوال ها کردم، تا سوال های خیلی آسان را پیدا کنم. تا اینکه يکی از شرکت کنندگان سوال G را با سرعت حیرت انگیز در دقیقه 12 حل کرد. سوال سختی نبود، یک سوال احتمالاتی که با تشکیل دستگاه معادلات خطی و حل آن به راحتی حل می شد. ولی چون تعداد دفعاتی که سر مسابقه کد حل دستگاه معادلات خطی نوشته بودم کم بود، کد این مساله را با احتیاط و کند زدم و دقیقه 41 این مساله را حل کردم. یکی از کارهای مثبتی که کردم این بود که قبل از submit چند تست دستی دادم، و یکی از خطاهایی که مرتکب شده بودم را رفع کردم (سایز آرایه را کم در نظر گرفته بودم). عملکردم در این سوال نسبتا راضی کننده بود. تنها يک نکته ی منفی وجود داشت و آن این بود که کد این مساله را با تسلط کامل و سریع نزدم، و احتمالا باید مروری بر الگوریتم های استاندارد بکنم تا آن هایی را که کاملا مسلط نیستم را کاملا مسلط شوم.

سوال دومی که حل کردم، سوال B بود، که مساله ی شبیه سازی آسانی بود. نمی دانم کار درستی کردم یا نه، ولی چون اندازه ورودی مساله بزرگ بود، به جای استفاده از ساختار map زبان ++C، از ساختار داده ای استفاده کردم که عملیات مجموعه رشته ها را سریع تر انجام دهد، که برای همین کد این مساله هم کمی زیاد طول کشید (حدود 30 دقیقه). البته باز هم راضی بودم، خیلی زیاد طول نکشید، با اینکه می شد حدود 15 دقیقه صرفه جویی کرد.

سوال سومی که حل کردم، سوال I بود، که به صورت حریصانه، و با استفاده از BFS حل کردم. از عملکردم برای این مساله ناراضی بودم. اولین اشتباهی که کردم، دقت نکردم که برای تعداد پریدن ها محدودیت وجود دارد و الگوریتم و کد اولم مشکل داشت و باعث شد مدتی تلف شود. پس از اینکه برای ورودی نمونه جواب اشتباه کردم، متوجه خطایم شدم و الگوریتم صحیح را طراحی و پیاده سازی کردم که زیاد طول نکشید، ولی Wrong Answer گرفتم. پس از بررسی الگوریتم و اطمینان از صحت آن، و اطمینان از اینکه هیچ جای برنامه overflow رخ نمی دهد، و خواندن کد و نیافتن اشتباه، چند تست دستی به برنامه دادم تا تستی که برای آن جواب اشتباه می گرفتم را پیدا کنم و متوجه شوم که جایی از برنامه به جای r*r، نوشته بودم r. کمی باید بیشتر دقت کنم!

سوال چهارمی که حل کردم، سوال H بود، که یک شبیه سازی ساده بود. این مساله را نسبتا بدون خطا حل کردم، و شاید تنها نکته ی منفی این بود که حل این مساله آسان 40 دقیقه طول کشید. البته با فرض اینکه بررسی سوال های باقیمانده ی دیگر و خواندن صورت سوال احتمالا 15 دقیقه طول کشیده، خیلی هم بد نبود.

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

سوال ششمی که حل کردم، سوال F بود، که یک مساله خیلی ساده بود، ولی با این حال عجله کردم و دقت نکردم و دو اشتباه مضحک کردم که باعث شد 2 بار Wrong Answer بگیرم. البته در نتیجه ی مسابقه خیلی تاثیر نداشت، ولی اگر این 2 خطا را نمی کردم، به جای هشتم، هفتم می شدم.

سپس به سراغ سوال E رفتم، که پس از کمی بررسی روی کاغذ آن را با استفاده از برنامه سازی پویا حل کردم، و حدود 15 دقیقه به پایان مسابقه کد آن را شروع کردم که متاسفانه نتوانستم آن را بدون اشکال تمام کنم. اگر اشتباه های سوال های قبل را نکرده بودم، وقت خیلی بیشتری برای این سوال داشتم (حداقل 90 دقیقه به جای 40 دقیقه) و می توانستم 7 سواله شوم.

در مورد دو سوال باقیمانده: سوال C به نظر قابل حل با برنامه سازی پویا می آید، و سوال A احتمالا با استفاده از روش عقبگرد و حرس کردن حل می شود.

امیدوارم دفعات بعدی خطاهای کمتری مرتکب شوم :)

Topcoder SRM 443

nospam@example.com (Hadi Moshayedi) — Wed, 24 Jun 2009 18:12:26 -0400

برای مشاهده بررسی سوال ها و راه حل ها به http://wiki.pykello.net/doku.php?id=tc:srm_443 مراجعه کنید.

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

- برای سوال آسان، می توانستم با کمی بیشتر فکر کردن راه حلی آسان تر پیدا کنم، و امتیاز بیشتری بدست بیاورم. این اشتباه، خیلی بزرگ نبود و در نتیجه خیلی تاثیر نداشت.

- سوال متوسط: اشتباهی که کردم، این بود که ابتدا از کنارهای راه های الگوریتمی به سرعت گذشتم و سعی کردم راه های ریاضی و فرمولی پیدا کنم. بدیهی بود که می شد این سوال را با BFS حل کرد، ولی BFS عادی زمان زیادی لازم داشت و مناسب نبود. ولی اکثر مواقع ارزش دارد که آدم راه های درست با زمان بد را بیشتر بررسی کند، که در اکثر مواقع منجر به راه حلی خوب می شود. که این مورد هم یکی از آن موارد بود. بالاخره، پس از صرف مدت قابل توجهی بر روی راه های ریاضی و عدم موفقیت، بدون اینکه به اندازه ی کافی فکر کنم، چون زمان کمی باقی مانده بود، سعی کردم راه حل BFS ای با مقداری بهینه سازی ساده بنویسم شاید جواب دهد. ولی با اینکه بر روی خیلی از تست ها خوب جواب می داد، بر روی برخی تست های دستی بیشتر از زمان مجاز 2 ثانیه طول می کشید، و برای همین submit نکردم. یک اشتباه دیگر این بود که به شکل خاص این گراف دقت نکردم. به آسانی با کمی تامل می شد BFS را طوری طراحی کرد که در زمان خیلی خوبی اجرا شود.

- سوال سخت: با توجه به اینکه اکثر زمان را بر روی سوال متوسط صرف کردم، به این سوال تقریبا وقتی نرسید، و بنابراین برای این سوال تقریبا هیچ کار اشتباهی انجام ندادم :)

- مرحله Challenge: اصولا آدم باید طوری عمل کند که برای داشتن رتبه ی خوب و افزایش rating نیازی به امتیازهای challenge نداشته باشد، و تنها برای بیشتر شدن افزایش rating در این مرحله تلاش کند. به هر حال، چون در حل مساله ها خوب عمل نکرده بودم، به این مرحله امید داشتم که در این مرحله نیز 50 امتیاز از دست دادم و نتیجه بدتر از پیش شد. دو کد در اتاق ما بود که با توجه به ranklist احتمال زیاد اشتباه بودند (و بودند)، اشتباه اول من این بود که کد شخصی با رتبه بهتر را زودتر باز کردم (اشتباه بود، چون بقیه نیز همین کار را می کنند، و برای اینکه احتمال اینکه فرصت Challenge پیدا کنم بیشتر باشد، بهتر است کدی که توسط شخص با رتبه بدتر نوشته شده است را زودتر باز کنم، یعنی بر عکس بقیه). به هر حال، 100 امتیاز مفت را در اینجا از دست دادم، و دو challenge ناموفق هم کردم و در کل 50 امتیاز در این مرحله از دست دادم. یکی از کدهایی که با عدم موفقیت challenge کردم، به طور واضحی اشتباه بود، ولی test case من به طرز احمقانه ای آسان بود و کد طرف درست جواب داد. به هر حال، در این مرحله چند تصمیم استراتژیک بهتر دیگر می شد گرفت، ولی چون این مرحله خیلی مهم نیست، بیشتر به این مرحله نمی پردازم.

به هر حال، rating ام به اندازه 109 تا کاهش پیدا کرد، ولی کاملا امیدوارم که بتوانم در مسابقات بعدی خوب عمل کنم و دوباره به rating بالاتر دست پیدا کنم :) امیدوارم تا پایان امسال بتوانم به 2650 برسم. البته برای این کار باید 5-6 مسابقه مداوم بدون اشتباه و خوب عمل کنم.

ZOJ Monthly Contest, Feburary 2009

nospam@example.com (Hadi Moshayedi) — Tue, 23 Jun 2009 13:23:00 -0400

بررسی سوال های مسابقه ی ZOJ Monthly Contest, Feburary 2009 : به http://wiki.pykello.net/doku.php?id=zju:feburary09 مراجعه کنید.

POJ Founder Monthly Contest – 2008.07.27

nospam@example.com (Hadi Moshayedi) — Mon, 22 Jun 2009 13:07:34 -0400

بررسی سوال های مسابقه ی POJ Founder Monthly Contest 2008.07.27 : به http://wiki.pykello.net/doku.php?id=pku:2008-07-27 مراجعه کنید.

I had a nightmare last night

nospam@example.com (Hadi Moshayedi) — Sun, 10 May 2009 07:19:28 -0400

دلبندم! اجازه نده مخالفتت با شخصی باعث شود تا در تصمیم گیری ها شتاب کنی! عمیق تر بنگر!

پ.ن. : این را بعد از دیدن خوابی نوشتم، در اثر اتفاقات روزمره ننوشتم.

Russel told Moein to tell Mostafa to inform me that ...

nospam@example.com (Hadi Moshayedi) — Sun, 10 May 2009 06:58:06 -0400

شخص الف: "2 + 2 چند می شود؟"
شخص ب: "4"
شخص الف: "بی شعور، همه می دانند که 2 + 2 برابر با 5 است!"
شخص ب: "نه، حاصل تفکرات من می گوید که 4 می شود!"
شخص الف: "احمق، نادان، تو را خواهم کشت تا زمین از فساد پاک شود، و درس عبرتی برای دیگران شود که بدانند 2 + 2 برابر با 5 است!"

Ultimate sin

nospam@example.com (Hadi Moshayedi) — Sun, 26 Apr 2009 19:04:29 -0400

There is no sin except 1/csc!

Opera 14, in F, Allegro non troppo

nospam@example.com (Hadi Moshayedi) — Sun, 26 Apr 2009 01:58:25 -0400

Sergey's diaries, April 22nd: "The doors were invented to enter, but I re-invented them to leave!"

... and I learned to lie painlessly!

nospam@example.com (Hadi Moshayedi) — Wed, 15 Apr 2009 12:42:48 -0400

از دفترچه خاطرات سريوژا در 15 آوریل 2009: «اعتراف می کنم، دروغ گفتم! شاید بزرگترین دروغ زندگی ام را! (تا حالا؟)»

IAUM CCC 5 Final Analysis - Part 1

nospam@example.com (Hadi Moshayedi) — Sun, 21 Dec 2008 13:40:28 -0500

لینک سوالات

توضیح راه حل ها(فعلا توضیح سه سوال)

Independence is NP-Hard

nospam@example.com (Hadi Moshayedi) — Fri, 05 Dec 2008 13:41:25 -0500

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

Post-Fountain Era a.k.a Winter

nospam@example.com (Hadi Moshayedi) — Tue, 18 Nov 2008 06:05:23 -0500

مرگ به سراغ همه کس می آید، حتی خاطرات ...

Lux Aeterna

nospam@example.com (Hadi Moshayedi) — Wed, 05 Nov 2008 13:47:04 -0500

کاش قایقی تنها بودم در اقیانوسی بی کران.

Top of the world

nospam@example.com (Hadi Moshayedi) — Sat, 01 Nov 2008 02:57:49 -0400

اجازه ی حضور در بهشت به مدت یک دقیقه را بدست آوردم،
وارد بهشت شدم، دقیقه ای گریستم،
خارج شدم به جهنم بازگشتم، به سرعت دویدم و در دره ای از آتش فرو رفتم.

Women Mathematicians

nospam@example.com (Hadi Moshayedi) — Thu, 02 Oct 2008 14:31:09 -0400

امروز سری به صفحه لیست ریاضی دانان زن ویکی پدیا زدم. نکته ی جالب توجه برای من این بود که اسم دو ایرانی هم در آن لیست بود:
1. لیلا خاتمی
2. مریم میرزاخانی

از افراد آن لیست تنها سه نفر را می شناختم :
1. سوفیا کوالوسکایا
2. اِمی نوثر
3. ادا لاولیس
گمان کنم "امی نوثر" از دو فرد دیگر تاثیرگذارتر بود!

همین طوری! برام جالب بود!

Dancing With the Bear

nospam@example.com (Hadi Moshayedi) — Wed, 01 Oct 2008 08:58:00 -0400

لحظات دردناک حداقل این خوبی را دارد که انسان برخی شرایط نامطبوع خود را کشف می کند،
ولی ممکن است این بدی را داشته باشد که برخی از این کشفیات اشتباه باشند!

Xibalba

nospam@example.com (Hadi Moshayedi) — Fri, 26 Sep 2008 16:57:21 -0400

گاهی اوقات انسان محکوم است که زندگی شادی داشته باشد،
گاهی اوقات انسان محکوم است که احساس تنهایی نکند،
گاهی اوقات انسان خاطرات گذشته را پاک می کند،
و زمان حال بدون هیچ خاطره و ردپایی می گذرد،
و آینده ای مجهول و بی اهمیت فرا می رسد.

A quote on life

nospam@example.com (Hadi Moshayedi) — Wed, 17 Sep 2008 16:32:08 -0400

Just living is not enough. One must have sunshine, freedom, and a little flower. ~Hans Christian Anderson

Almost Here

nospam@example.com (Hadi Moshayedi) — Sun, 14 Sep 2008 12:30:01 -0400

وجود خودمان (و بازخورد رفتارمان) دلیل خوبی است برای اینکه درباره ی دیگران و معنی رفتار آن ها زود قضاوت نکنیم.

Break with your past

nospam@example.com (Hadi Moshayedi) — Fri, 12 Sep 2008 01:38:59 -0400

هنگامی که جوان تر بودم، هنگام سحر با صدای پرنده ها از خواب بیدار می شدم، و لذتی عجیب به من دست می داد.
تا آنکه مدتی پیش، در جایی سکنی گُزیدم که پرنده ی مهاجر در آن می خواند!
شنیدن صدای پرنده ی مهاجر و مشاهده ی طریقه پرواز آن از هر لذتی فراتر بود،
دوست داشتم تا آخر عمر هر روز صبح تا شب به صدای پرنده ی مهاجر گوش فرا می دادم،
ولی حیف که پرنده ی مهاجر نیاز دارد که مهاجرت کند، و من هرگز به آرزوی خود نخواهم رسید!

I hate 213.207.241.4

nospam@example.com (Hadi Moshayedi) — Wed, 10 Sep 2008 11:39:19 -0400

مردم به من افتخار خواهند کرد،
هم میهنانم، هم نژادهایم، هم کیشانم،
چون آن ها نیاز دارند، نیاز دارند به دلیلی،
به دلیلی که با آن ثابت کنند که ایرانی بودن خوب است، ترک بودن خوب است،
آن ها نیاز دارند که خوش باشند،
ولی خوشی را در چیزهایی جستجو می کنند که خودشان در ایجاد آن هیچ اختیاری ندارند،
و نخواهند اندیشید به اینکه که خوشی آن ها مصادف با ناخوشی ملتی دیگر است.

--------------------------------------------------------------------------

مردم اسطوره ها خواهند ساخت،
و فراموش خواهند کرد که اسطوره یعنی دست نیافتنی،
و نخواهند فهمید که با این کار خودشان را محدود کرده اند،
و نخواهند فهمید که بدون اسطوره می توان زندگی بهتری داشت.

How does it feel to be 87208151?

nospam@example.com (Hadi Moshayedi) — Wed, 10 Sep 2008 08:05:22 -0400

تحصیل خواهم کرد، تحصیل خواهم کرد تا فراموش کنم ...
فراموش کنم که من تنها هستم.

تحصیل خواهم کرد، و به مدارج بالاتر دست پیدا خواهم کرد ...
احساس بودن در بهشت را خواهم کرد،
ولی فراموش خواهم کرد که در بهشت واقعی نیستم،
و جایی که من هستم تنها یک باغچه است،
و پائیز و زمستانی در راه است.

تحصیل خواهم کرد، و شخصیت مهمی خواهم شد، شخصیتی بسیار مهم!
مردم مرا دوست خواهند داشت، و مرا تحسین خواهند کرد،
ولی فراموش خواهم کرد که مردم تخصص مرا دوست دارند، و نه من را،
فراموش خواهم کرد که مردم مثل من شدن را دوست دارند، و نه بودن با من را،
و فراموش خواهم کرد که تنها یک تصادف برای فراموش شدن کافی است!

تحصیل خواهم کرد، تحصیل خواهم کرد تا فراموش کنم، فراموش کنم درد واقعی وجود داشتن را! درد تنها بودن را ...

پائیز خواهد آمد، و من تنها خواهم بود، تنهاتر از گذشته،
زمستان خواهد آمد، و من سرد خواهم شد، سردتر از گذشته،
بهار خواهد آمد، و آرام از کنارم خواهد گذشت، بی آنکه وجودش را حس کنم،
تابستان خواهد آمد، ولی من به فکر رسیدن پائیز سال بعد خواهم بود!

دوباره پائیز خواهد آمد، زمستان، بهار، و تابستان نیز،
ولی دردها همه فراموش شده، و من فقط به فکر بالا رفتن هستم، به فکر بالا رفتن از قله های افتخار!

به اوج قله های افتخار خواهم رسید، نفسی خواهم کشید،
و سپس خود را پرت خواهم کرد به سوی دردهای فراموش شده،
ولی حیف که ظرفیتش را نخواهم داشت،
و چه پایان غم انگیزی خواهد داشت بودن من!

چه خوش گفت آن دوست نیک کردار:
«از فراموش شدگان هستیم و خواهیم بود»
وای به حال من،
منی که مرگ نیز فراموشم کرده است!

پ.ن. : منظورم از جملات بالا این نبود که حس می کنم دوستانم مرا به خاطر چیز دیگری ، و نه به خاطر خودم، دوست دارند. لطفا سوء تفاهم نشود! اگر با کسی رفتار دوستانه ای دارم، مطمئن باشد که از او خیلی خوشم می آید! :) و اگر نسبت به کسی احساس خوبی نداشته باشم، معمولا آشکار می سازم!

</html>

Summer of Big Decisions

nospam@example.com (Hadi Moshayedi) — Mon, 08 Sep 2008 22:40:11 -0400

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

Cyber Madness

nospam@example.com (Hadi Moshayedi) — Sat, 06 Sep 2008 22:48:38 -0400

بحثی که می خواهم مطرح کنم، احتمالا موافقان و مخالفانی خواهد داشت. نکته ی مورد بحث من اين است که: "تا چه حدی به کامپیوتر و اينترنت نیازمندیم؟"

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

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

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

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

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

تجربه ی دیگر اینکه، تا حدودی حس می کنم اینکه در مسابقات برنامه نویسی تنها یک کامپیوتر در اختیار تیم های سه نفری است، خیلی اوقات، مزیت و نه محدودیت محسوب می شود. دلیل من و خیلی از افراد با تجربه هم این خواهد بود که روی کاغذ بهتر می شود فکر کرد، و یک شخص کم تجربه تر وقتی پشت کامپیوتر است، وسوسه می شود که شروع به نوشتن کد کند، و تقریبا فرصتی برای فکر کردن پیدا نمی کند، و چنین شخصی هیچ وقت موفق نخواهد شد یک مساله ی سخت را حل کند! داشتن یک کامپیوتر حداقل این مزیت را دارد که در هر لحظه حداقل دو نفر مجبورند پشت کامپیوتر نباشند، و بهترین کاری که می توانند فکر کردن است، که به مراتب از نوشتن کد سخت تر و البته شیرین تر است.

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

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

لطفا نظرات خود را بیان کنید! فقط این نکته را در نظر داشته باشید که مورد بحث من نشستن اکثر روز پشت کامپیوتر و زل زدن به مانیتور، و نه استفاده های مفید آن (مثلا گوش دادن به موسیقی، ...) است.

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

پ.ن. 2 : برای اینکه نسبتا ثابت کنم به نظرم دانشمندتر مخالف خوشبخت تر است، گمان کافی باشد که بگویم تا لحظات آخر، یعنی تا حدود یک هفته مانده به ثبت نام ارشد (یعنی حدودا هشتم شهریور 1387) نمی خواستم ادامه تحصیل بدهم و در دوره ی ارشد ثبت نام کنم. و الان هم که ثبت نام کردم، به این دلیل نیست که خودم انگیزه پیدا کرده ام، یا آینده ی خود را روشن تر می بینم. دلیل اصلی ام برای انصراف از ادامه تحصیل این بود که می خواستم زندگی بهتر و با آرامش تری داشته باشم، هر چند مطمئنم خیلی از افراد مرا به خاطر این دلیل احمق خواهند نامید، و البته آزادند هر اعتقادی داشته باشند، ولی من هرگز دلایل آن ها را برای ادامه ی تحصیل نپذیرفتم و نپذیرفته ام، ولی چه کنم که انسان مستقل از دیگران نیست و برخی اوقات باید تن به خواسته های دیگران دهد!
یا مثال دیگر اینکه پارسال نمی خواستم در ACM ICPC شرکت کنم، ولی به دلایلی به غیر از لذت بردن از این مسابقات، در آخرین لحظات ممکن وارد معرکه شدم!

پ.ن. 3 : اینکه اعتقاد ندارم دانشمند تر شدن = خوشبخت تر بودن، چندین موضوع را می رساند : اولا اینکه شرط کافی برای احساس خوشبختی در خودم فقط علم زیاد نیست (هرچند جزئی از آن است). ثانیا، اگر اینگونه اعتقاد داشته باشم، منجر به دید بدی و طبقه بندی بدی نسبت به دیگران خواهد شد. ثالثا، اگر این دو را مساوی در نظر نگیرم، این به این معنا نیست که اشتراک مجموعه افراد خوشبخت و افراد دانشمند تهی است، و مسلما افراد دانشمند زیادی بوده اند که بسیار خوشبخت بودند. شاید داشتن کمی دید در زمینه ی ریاضیات گسسته و نظریه ی مجموعه ها در رفع ابهام کمک کند! و امیدوارم کسی از دست من ناراحت نشده باشد.

Last Judgement

nospam@example.com (Hadi Moshayedi) — Thu, 28 Aug 2008 08:31:49 -0400

ساعت دوازده و چهل و پنچ دقیقه، هنگامی که به نظر می رسید خوشبختی من در حال آغاز شدن است، دنیا به پایان رسید.

Promentory

nospam@example.com (Hadi Moshayedi) — Wed, 27 Aug 2008 16:02:55 -0400

جاودانگی نیاز به کارهای بزرگ دارد، ولی کارهای بزرگ نیازی به جاودانگی ندارند ...

Fort Battle

nospam@example.com (Hadi Moshayedi) — Mon, 25 Aug 2008 13:02:20 -0400

هنگامی که «ارواح پلید» به «رویاها» ی انسان راه پیدا می کنند، احساس عجیبی به انسان دست می دهد که در یک هنگام، هم احساس خوشبختی می کند و هم احساس بدبختی ...

IOI 2008

nospam@example.com (Hadi Moshayedi) — Sat, 23 Aug 2008 18:40:14 -0400

المپیاد کامپیوتر جهانی 2008 برگزار شد. از نکات جالب مسابقه ی امسال:

1. متاسفانه دولت مصر ابتدا از دادن ویزا به تیم ایران سر باز زد، و وقتی ویزا صادر کرد که یک روز از مسابقات گذشته بود، و دیگر دیر شده بود. واقعا جای تاسف داره!

2. موجودی بلاروسی به نام Henadzi Karatkevich که تنها 14 سال دارد، مدال طلا گرفت. البته خیلی جای تعجب نداره، چون وقتی 12 ساله بود مدال نقره گرفته بود، و هنگام 13 سالگی مدال طلا. اگر 2 سال دیگر هم مدال طلا بگيره، به پرافتخارترین شرکت کننده ی المپیاد کامپیوتر را کسب می کنه. (فعلا متعلق به Filip Wolski هست با 4 مدال طلا).

3. پس از گذشت مدت نسبتا زیادی، هنوز نتایج در وب سایت مسابقات قرار نگرفته. به هر حال، می توانید نتایج را در SnarkNews ّببینید.

4. نتیجه تیم چین خیلی خوب نبود. یکی از اعضای تیم خیلی بد عمل کرد و مدال نقره گرفت، و در نتیجه تنها موفق به اخذ 3 طلا شدند :D سال 2004 تا سال 2007 همه ی مدال های چین طلا بود.

The Fountain of Youth

nospam@example.com (Hadi Moshayedi) — Sat, 23 Aug 2008 16:56:10 -0400

مواقع زیادی در زندگی، خیلی از معانی context free نیستند، و خیلی از چیزها با توجه به context-ای که در آن وجود دارند معنا پیدا می کنند ...

موسیقی ای که ممکن است برای یکی بسیار جذاب و پر از مفاهیم عمیق باشد، ممکن است برای دیگری موسیقی ای بسیار بد و بی هیچ مفهوم سازنده ای به نظر برسد ...

موسیقی ای که زمانی یادآور پیروزی و شکست ناپذیری بود، ممکن است روزی یادآور بدبختی و فلاکت و «نابودی رویاهای شیرین» باشد ...

توانایی حرف زدن نعمتی بزرگ است، توانایی حرف نزدن نعمتی بزرگ تر.

نقد هنگام رخ دادن؟ یا نقد پس از رخ دادن؟
نقد هنگام دقت؟ یا نقد هنگام عدم دقت؟

Hadi Saei wins gold medal!

nospam@example.com (Hadi Moshayedi) — Fri, 22 Aug 2008 08:34:36 -0400

هادی ساعی مدال طلای المپیک پکن را تصاحب کرد!

ای کاش همه ی ما «ساعی» باشیم ...

IAUM CCC 5

nospam@example.com (Hadi Moshayedi) — Mon, 18 Aug 2008 10:24:00 -0400

بالاخره، مرحله نهایی مسابقه ی IAUM CCC 5 برگزار شد، و تنها چیزی که برای من به جا ماند، خاطره ای نسبتا خوش بود! هرچند از چند روز قبل از مسابقه تا اتمام مسابقه ی نهایی استرس شدیدی داشتم و آرزوی اتمام این لحظات را داشتم، ولی پس از اتمام مسابقه ی نهایی و شنیدن نظرات شرکت کنندگان، احساس رضایت کردم.

من فقط یک طراح سوال و داور بودم، و عضو هیئت اجرایی نبودم، با این حال، در این مدتی که در مشهد بودم، تلاش قابل تقدیر دانشجویان دانشگاه آزاد مشهد را مشاهده کردم، و از ته دل آرزو کردم که این مسابقات باز هم ادامه داشته باشد. احتمالا مهم ترین دلیل اینکه هر سال شرکت کنندگان این مسابقات بیشتر می شود، و افراد قوی تری هر سال جذب این مسابقات می شوند، برگزاری بسیار خوب این مسابقات است.

به نظر من، یکی از نکات مثبت حضور داشتن در این مسابقات آشنا شدن با افرادی است که علايقم با علايق آن ها همپوشانی دارد، ولی قبلا با آن ها آشنا نبودم، و این احساس خوبی در من ایجاد می کند.

نظرم در رابطه با نتیجه ی مرحله ی نهایی: گمان کنم چند نفر از افراد، احتمالا به علت عوامل جانبی (مانند استرس سر مسابقه، ...)، و نه به علت ضعف در حل مساله و توانایی علمی، ضعیف تر از توان واقعی خود عمل کردند و نتیجه نهایی کمی اعجاب انگیز بود. برنده ی نهایی مسابقه، آقای نیما احمدی پور بود، که بسیار خوب عمل کرد، و توانست همه ی مسائل را حل کند. به هر حال، تعداد زیادی از شرکت کننده ها را می شناختم و با تعدادی از آن ها دوست بودم، و از خوب عمل کردن خیلی های خوشحال شدم، و از بد عمل کردن خیلی ها ناراحت.

با این حال، عادی است که شدیدا دوست داشته باشم که کسی که دو سال هم تیمی ام بود، و یک ترم هم اتاقی، و برای باقی عمرم یک دوست بسیار خوب، یعنی محمدرضا خانی، خیلی خوب عمل کند. نتیجه نهایی او (یعنی چهارم) خوب بود، ولی با توجه به اینکه به نظر من باهوش ترین عضو تیم Dreamers United بود، گمان می کنم می توانست بهتر از این هم عمل کند. احتمالا یکی از دلایل اینکه خیلی خوب عمل نکرد، کمبود تمرین در چند ماه اخیر بود. امیدوارم هر روز موفق تر از دیروز باشد.

در ادامه به توضیح مختصر در مورد سوالاتی که من طرح کرده بودم می پردازم:

مسابقه نیمه نهایی صفر(لینک سوالات)

سوال C - کوتاه ترین زیر رشته ی نا مشترک : این سوال را با استفاده از Trie و مرتبه ی زمانی (O(n^2 حل کرده بودم، ولی راه حل های با مرتبه ی زمانی (O(n^2 log n نیز پذیرفته می شدند.

سوال D - مربع ها : هدف این بود که راه حل های (O(n^2 (برنامه نویسی پویا) و (O(n^2 log n (تبدیل به هیستوگرام و مرتب سازی و ...) پذیرفته شوند، ولی متاسفانه داده های تست ضعیف بود و راه حل (O(n^3 نیز پذیرفته می شد.

سوال E - تطبیق الگو : این سوال قرار بود سخت ترین سوال مسابقه باشد، ولی به علت عدم دقت در تنظیم محدودیت ها، آسان ترین سوال مسابقه بود! (مثلا باید اگر طول الگو 20000 بود و تعداد علامت سوال ها حداکثر 100، در آن صورت، بازهم راه حل خوبی برای حل مساله وجود داشت، ولی راه حل بدیهی خوب عمل نمی کرد.) با همین محدودیت ها، راه حل بدیهی به خوبی جواب می دهد. ولی اگر محدودیت ها خیلی سخت تر از این بودند، نسخه ی تغییر یافته ای از KMP، یا استفاده از Aho-Corasick می توانست مساله را به خوبی حل کند.

سوال F - شمارش جفت ها : قرار بود راه حل (O(n log n پذیرفته شود، ولی ظاهرا برخی از شرکت کننده ها با راه حل (O(n^2 محدود شده نیز توانسته بودند این سوال را حل کنند.

جمع بندی :در مجموع، از این مسابقه چندان راضی نبودم! چون زیاد اشتباه کرده بودیم! در انتها نیز دو نفر (نیما احمدی پور، و حامد احمدی) توانستند تمام سوالات را حل کنند، و حامد احمدی عنوان اول این مسابقه را کسب کرد.

مسابقه نیمه نهایی یک(لینک سوالات)

سوال B - علی کوچولو و کلمات متقارن : راه حل داور دارای مرتبه ی زمانی متناسب با مجموع طول کلمات بود.

سوال C - تجزیه ی گراف ها : تبدیل می شود به مساله ی 2SAT . تنها یک نفر موفق شد این مساله را سر مسابقه حل کند (مهدی صفرنژاد) ولی حداقل دو نفر دیگر به ایده ی این سوال رسیده بودند ولی از آن جایی که بلد نبودند کد 2SAT را بنویسند، موفق به حل آن نشدند. ظاهرا محمدرضا خانی راه حل دیگری برای این سوال داشت، که به علت خستگی، از او خواستم بعدا توضیح دهد!

سوال F - یافتن زیر درخت : بیش از یک راه حل با مرتبه ی زمانی خطی برای حل این مساله وجود دارد.

جمع بندی : این مسابقه راضی کننده تر از مسابقه ی قبلی بود، و تقریبا هیچ مشکل خاصی پیش نیامد. در انتها مهدی صفر نژاد با حل 5 سوال نفر اول این مسابقه شد.

مسابقه ی نهایی(لینک سوالات)

سوال A - شمارش درخت های پوشا : این مساله را می توان با استفاده از قضیه ی Matrix-Tree حل کرد. ولی از آن جایی که اصولا نباید انتظار داشته باشیم شرکت کننده ها چنین قضایایی را بلد باشند، من خودم این مساله را با استفاده از یک الگوریتم برنامه سازی پویای (O(n^2 3^n حل کرده بودم. سر مسابقه سه نفر این مساله را حل کردند که دو نفر از قضیه ی مذکور استفاده کردند، و یک نفر از راه حل برنامه سازی پویا (نمی دانم راه حلش شبیه مال من بود یا نه).

سوال B - کوچک ترین مثلث : با راه حل (O(n^3 ای که خوب پیاده سازی شده باشد حل می شود، ولی احتمالا راه حل های بهتری نیز وجود دارند!

سوال C - رشته های امن : برنامه سازی پویا با استفاده از آرایه ی overlap الگوریتم KMP!

سوال D - مسافرت های تصادفی : راه حل من یک DFS بود، ولی ظاهرا اکثر شرکت کنندگان از راه حل دیگری استفاده کردند.

سوال E - انتخاب پروژه ها : تبدیل می شود به مساله ی مشهور Minimum Cut در گراف. تنها یک نفر (نیما احمدی پور) موفق به حل این مساله شد، ولی حداقل یک نفر دیگر ایده ی درست برای حل این مساله را داشت (مهدی صفرنژاد)، که متاسفانه راه حلش جواب درست را نمی داد.

سوال F - پارادوکس : راه حل این مساله ترکیبی است از پیدا کردن مولفه های همبند، Brute Force، و برنامه سازی پویا. باز هم تنها یک نفر موفق به حل این مساله شد (نیما احمدی پور) ولی راه حل مهدی صفرنژاد هم اکثر تست ها را درست جواب می داد و تنها در چندین تست با پاسخ داور تفاوت داشت.

سوال G - طولانی ترین زیردنباله ی مشترک : برنامه سازی پویا. نکته ی اساسی این مساله این بود که هر عدد حداکثر یک بار در هر دنباله وجود دارد. چندین نفر تلاش کردند که از چندین LCS دو به دو استفاده کنند که مسلما راه حل درستی نیست و با کمی تامل می توان مثال نقضی برای آن پیدا کرد.

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

I run

nospam@example.com (Hadi Moshayedi) — Mon, 18 Aug 2008 00:37:00 -0400

می دوم در کوچه های پر از بن بست، و خیابان های پر از وحشت ...
فرار می کنم از حال، فرار می کنم از گذشته ...
چرا دیگر از کوه های زیبا بالا نمی روم؟

Minilek Boycotts Google Codejam

nospam@example.com (Hadi Moshayedi) — Sun, 17 Aug 2008 12:15:31 -0400

احتمالا بعضی از شما می دانید که قوانین امسال Google CodeJam اجازه ی شرکت در مسابقات نیمه نهایی و نهایی را به ساکنان ایران و ساکنان سایر کشورهای مورد تحریم آمریکا نمی دهد. شاید برایتان جالب باشد که بدانید حداقل یک آمریکایی (Jelani Nelson یا Minilek) به همین دلیل این مسابقات را تحریم کرده است. (لینک اول، لینک دوم).

به عنوان یک ایرانی، از او تشکر می کنم!

شاید جالب باشید بدانید که این شخص آدم خفنی می باشد. (صفحه شخصی وی)

The Sky is the Limit

nospam@example.com (Hadi Moshayedi) — Sun, 17 Aug 2008 09:47:08 -0400

اساطیر باعث محدودیت و عدم موفقیت می شوند.

The Art

nospam@example.com (Hadi Moshayedi) — Sun, 17 Aug 2008 08:17:53 -0400

هُنَریست «لبخند زدن و خوش برخورد بودن» در هنگام استرس و نگرانی بسیار شدید.

Importance of "Possibly", U+2203, ...

nospam@example.com (Hadi Moshayedi) — Tue, 29 Jul 2008 11:17:03 -0400

یکی از تفاوت های نوشته های پولیا و دیگران در نحوه ی به کار بردن adverb ها و quantifier هاست.

برنده ی بازی کیست؟
این تنها یک ارجاع است!

... were always there ...

nospam@example.com (Hadi Moshayedi) — Tue, 29 Jul 2008 11:04:47 -0400

رابطه ی حالت کنونی من و حالت کنونی دنیا چیست؟

حالت کنونی من عضو ی از حالت کنونی دنیا است، یا حالت کنونی دنیا عضوی از حالت کنونی من؟

We got a winner!

nospam@example.com (Hadi Moshayedi) — Sun, 27 Jul 2008 15:07:58 -0400

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

اگر خدا Feedback را نمی آفرید، احتمالا بدبخت می شدیم! یا لا اقل، خوشبخت نمی شدیم.

All the Sad People

nospam@example.com (Hadi Moshayedi) — Tue, 15 Jul 2008 16:22:33 -0400

مگه فرقی می کنه چطوری خوشبخت باشم؟ با گذشته یا بی گذشته؟ با دوستان قدیمی یا با دوستان جدید؟ با قد بلند یا با قد کوتاه؟

چه چیزی هویت منو تشکیل می ده؟ چند تا خط کج و کوله یا چند تا کلمه؟

Travelling Salesman Problem

nospam@example.com (Hadi Moshayedi) — Wed, 25 Jun 2008 08:50:14 -0400

Brainy Quotes

nospam@example.com (Hadi Moshayedi) — Fri, 20 Jun 2008 13:52:48 -0400

"Live as if you were to die tomorrow. Learn as if you were to live forever."

- Mohandas Karamchand “Mahatma” Gandhi

"A diamond is a piece of coal that stuck to the job."

- Thomas A. Edison

"Programming is not a zero-sum game. Teaching something to a fellow programmer doesn't take it away from you. I'm happy to share what I can, because I'm in it for the love of programming."

- John Carmack

"Low-level programming is good for the programmer's soul."

- John Carmack

"Do what you think is interesting, do something that you think is fun and worthwhile, because otherwise you won't do it well anyway."

- Brian Kernighan

"Software has to be designed by hackers who understand design, not designers who know a little about software. If you can't design software as well as implement it, don't start a startup."

- Paul Graham

404

nospam@example.com (Hadi Moshayedi) — Fri, 06 Jun 2008 00:25:48 -0400

روزی که کارخانه ها داده ها را پردازش می کنند و بی نهایت داده داریم، آن قدر زياد که عددها سرريز می کنند، باید به فکر به چالش کشیده شدن و مغلوب شدن هم بود.

An Enumeration Theorem

nospam@example.com (Hadi Moshayedi) — Wed, 04 Jun 2008 15:37:00 -0400

شهر بردارهای n-بعدی که فقط همین یک در را ندارد. همه ی اهالی آن که به دنبال خریدن بردارهای مستقل خطی نیستند.

اما حيف؛ حيف که برخی شهرها هيچ دری ندارند و برای ورود به آن ها تله پورت نياز است!

Fire Effect

nospam@example.com (Hadi Moshayedi) — Sun, 23 Mar 2008 16:25:15 -0400

چند روز پیش الگوریتم مشهور و قدیمی اثر آتش را با استفاده از SDL پیاده سازی کردم. البته قبلا با استفاده از pygame نیز این روش را پیاده سازی کرده بودم، ولی سرعت آن خیلی کمتر از این پیاده سازی بود.

فایل اجرایی: fire.exe

احتمالا نیاز داشته باشید SDL.dll را هم دانلود کنید.

کد منبع: http://wiki.pykello.net/doku.php?id=implementation:fire_effect

توضیح الگوریتم: http://www.gamedev.net/reference/list.asp?categoryid=72#251

BigInt / BigNum / Huge Numbers Implementation

nospam@example.com (Hadi Moshayedi) — Sun, 03 Feb 2008 10:17:17 -0500

پیاده سازی کلاس BigInt در ++C

Links of the Week

nospam@example.com (Hadi Moshayedi) — Sat, 26 Jan 2008 08:57:48 -0500

1. توابع داخلی GCC که بعضی وقت ها (مثلا در مسابقات برنامه نویسی) ممکن است به کار بیاید.

2. CSS Gradient Text Effect

3. آموزش TurboGears

4. نرم افزار wxFormBuilder 3.0 RC5 عرضه شد.

AVL Tree

nospam@example.com (Hadi Moshayedi) — Sat, 26 Jan 2008 04:46:22 -0500

پیاده سازی درخت جستجوی دودوئی متوازن AVL

Yungom

nospam@example.com (Hadi Moshayedi) — Mon, 14 Jan 2008 14:04:00 -0500

توضیح سوال D مسابقه ی منطقه ای تهران 2007 توسط تیزترین عضو تیم Tiz Boys: ارسلان موسویان.

به غیر از ارسلان، دو نفر دیگر هم قول همکاری داده اند، و احتمالا یک نفر دیگر هم همکاری کند.
پ.ن: یک تغییر کوچولو تو متن مقاله انجام شد.

Some nice links

nospam@example.com (Hadi Moshayedi) — Thu, 10 Jan 2008 11:02:49 -0500

53 تکنیک CSS که زندگی بدون آن ها امکان پذیر نیست!

وبلاگ David Eppstein

programming.reddit.com

Faster Input

nospam@example.com (Hadi Moshayedi) — Mon, 07 Jan 2008 21:15:06 -0500

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

November Rain

nospam@example.com (Hadi Moshayedi) — Mon, 07 Jan 2008 18:55:59 -0500

سلام،

اگر دوست داشتید، سری به http://wiki.pykello.net/doku.php?id=november_rain بزنید.

Some nice online textbooks

nospam@example.com (Hadi Moshayedi) — Sun, 06 Jan 2008 19:04:38 -0500

چند کتاب مجانی خیلی خوب برای خواندن و لذت بردن از زندگی:
1. کتاب نظریه ی بازی
2. جبر مجرد کاربردی
3. هندسه ی محاسباتی

A Love Story

nospam@example.com (Hadi Moshayedi) — Thu, 20 Dec 2007 14:44:08 -0500

لینک

Misconception

nospam@example.com (Hadi Moshayedi) — Sun, 25 Nov 2007 08:14:37 -0500

"Experience is the name everybody gives to his mistakes!" Oscar Wilde

Consistency

nospam@example.com (Hadi Moshayedi) — Sun, 18 Nov 2007 17:36:22 -0500

در مسابقه ی تمرینی هفته ی پیش هنگامی که هنوز 20 دقیقه به پایان مسابقه باقی مانده بود، کار را تمام شده حساب کردم و از تلاش دست کشیدم! بعدا از خودم بدم اومد

Arash est moitié moins grand que la Tour Eiffel!

nospam@example.com (Hadi Moshayedi) — Wed, 14 Nov 2007 07:02:42 -0500

آقای دکتر علی زاده در پاریس:

Einstein Quote of the Day

nospam@example.com (Hadi Moshayedi) — Thu, 08 Nov 2007 03:09:27 -0500

A clever person solves a problem. A wise person avoids it.

Words of Wisdom IV

nospam@example.com (Hadi Moshayedi) — Fri, 02 Nov 2007 11:11:38 -0400

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

Words of Wisdom III

nospam@example.com (Hadi Moshayedi) — Fri, 26 Oct 2007 19:34:26 -0400

رسول خدا صلی الله عليه و آله فرمودند:

«عبادت هفتاد جزء است و بالاترين و بزرگترین آن کسب حلال است.» (ثواب الاعمال و عقاب الاعمال)

«آنچه بیش از هر چیز بر امتم بعد از خود می ترسم، درآمدهای حرام، هواپرستی پنهانی، و رباست.» (بحارالانوار)

Longing ...

nospam@example.com (Hadi Moshayedi) — Tue, 23 Oct 2007 01:46:00 -0400

"مدت زيادی به انتظار آمدن تو نشستم،

آن قدر زياد که به نبودن تو عادت کردم،

تو پس از مدت زيادی آمدی،

ولی من اکنون انتظار برای تو را بيش از خودت دوست دارم ..."

(شعری از عزيز نسين)

---------------------------------------------------

کسانی که نمی دانند بدانند، موفق کاتب نيز صاحب وبلاگ شد!

Checking for overflow

nospam@example.com (Hadi Moshayedi) — Mon, 22 Oct 2007 05:19:26 -0400

فرض کنيد می خواهيد تابعی بنويسيد که عبارت a * b^p را محاسبه کند، در صورتيکه حاصل از 10¹⁸ کمتر بود، حاصل را برگرداند، و در غير اين صورت عدد 1- را برگرداند. از چه راه حلی استفاده می کنيد؟ (با فرض اينکه a و b و p از 10¹⁸ کوچکتر هستند.)

راه حل 1: از کلاس Big Integer استفاده کنيد. حاصل را حساب کنيد، و سپس حاصل را با 10¹⁸ مقايسه کنيد. در ++C و C اين روش احمقانه ترين روش است (چون احتمالا بايد اين نوع داده را خودتان پياده سازی کنيد) ولی اگر از Java يا Python استفاده می کنيد، اين روش، روش خوب و ساده ايست.
توجه: در راه حل های بعدی از اين نکته که نوع داده ی عدد صحيح 64 بيتی (long long در ++C) می تواند اعدادی تا بزرگی 9x10¹⁸ را نگهداری کند استفاده کرده ايم.

راه حل 2: چون 2x10¹⁸ از محدوده ی long long بيرون نمی زند، به راحتی می توانيم دو عدد کوچکتر از 10¹⁸ را با هم جمع کنيم، و سپس با 10¹⁸ مقايسه کنيم تا بفهميم که حاصل از 1- بزرگتر است يا نه. همان طور که احتمالا می دانيد، عمل ضرب را می توان با استفاده از عمل جمع پياده سازی کرد. کد اين تابع را در زير مشاهده می کنيد:

longlong multiply(longlong a, longlong b)
{
if(b == 0)return0;
longlong result = multiply(a, b / 2);
if(result == -1)return-1;
result += result;
if(b % 2) result += a;
if(result > 1000000000000000000ll)return-1;
return result;
}

و عمل توان را با استفاده از عمل عمل ضرب می توان پياده سازی کرد:

longlong power(longlong a, longlong b)
{
if(b == 0)return1;
longlong result = power(a, b / 2);
if(result == -1)return-1;
result = multiply(result, result);
if(result == -1)return-1;
if(b % 2) multiply(result, a);
if(result == -1)return-1;
return result;
}

اين روش نسبت به روش قبل ساده تر و عاقلانه تر (در صورت عدم وجود امکانات) می باشد، ولی ساده ترين روش نيست!

راه حل 3: با استفاده از عمل تقسيم می توان حداکثر مقداری که می توانيم در يک عدد ضرب کنيم تا حاصل کوچکتر از 10¹⁸ شود را پيدا کرد. با استفاده از اين نکته، کارمان کمی ساده تر می شود و می توانيم به صورت زير عمل کنيم:

longlong multiply(longlong a, longlong b)
{
if(b == 0)return0;
longlong maxp = 1000000000000000000ll / b;
if(a > maxp)return-1;
return a * b;
}

راه حل 4: استفاده از لگاريتم در مبنای 10. فرض کنيد می خواهيم a*b^p را محاسبه کنيم. اگر به صورت زير عمل کنيم:

longlong power(longlong a, longlong b)
{
if(b == 0)return1;
longlong result = power(a, b / 2);
result *= result;
if(b % 2) result *= a;
return result;
}
longlong calc(longlong a, longlong b, longlong p)
{
double L = log10(a) + p * log10(b);
if(L > 18)return-1 ;
return a * power(b, p) ;
}

ممکن است بعضی اوقات نتيجه گيری اشتباهی کنيم، چون اختلاف لگاريتم 10¹⁸ و 1+10¹⁸ کمتر از ^18-10 می باشد و با اين مقايسه ها اين اختلاف ها مشخص نمی شوند.
چون 10^18.5 عمرا از محدوده ی long long خارج نیست و تمام اعداد کوچکتر يا مساوی 10¹⁸ دارای لگاريتمی کمتر از 18.5 هستند، حتی با در نظر گرفتن خطاهای محاسباتی، می توان به روش زير عمل کرد:

longlong power(longlong a, longlong b)
{
if(b == 0)return1;
longlong result = power(a, b / 2);
result *= result;
if(b % 2) result *= a;
return result;
}
longlong calc(longlong a, longlong b, longlong p)
{
double L = log10(a) + p * log10(b);
if(L > 18.5)return-1 ;
longlong result = a * power(b, p);
if(result > 1000000000000000000ll)return-1;
return result ;
}

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

Sleeping late: Practical guide for the psycho

nospam@example.com (Hadi Moshayedi) — Mon, 22 Oct 2007 02:40:00 -0400

توجه: محتويات نوشته پايه ی علمی ندارد و صرفا بر اساس تجربيات خودم نوشته شده است.

ساعت 12 شب است. در حال ياد گرفتن يک موضوع بسيار جالب هستيد، و يا می خواهيد يک مساله ی بسيار سخت را حل کنيد، و آنقدر مشتاق هستيد که تصميم گرفته ايد بسيار دير بخوابيد. در اين حالت، بهترين دوست شما نوشيدنی ای به نام "قهوه" است. البته برای اينکه بتوانيد 3 ساعت ديرتر از معمول بخوابيد، برای استفاده از قهوه بايد نکاتی را در نظر بگيريد.

اول اينکه زياد به فکر خوشمزه کردن قهوه ی خود نباشيد. به هيچ وجه از کافی ميت استفاده نکنيد، و شکر را به اندازه ای اضافه کنيد که قهوه بدمزه نباشد. قهوه ی خوشمزه اثری بسيار کمتر بر روی سيستم هوشياری شما دارد. دوم اينکه قهوه را داغ صرف ننماييد! حداقل در مورد خودم، قهوه ی داغ باعث خواب آلودگی می شود، ولی قهوه ی ولرم، يا سرد باعث هوشياری بسيار بالا می شود. سوم اينکه فکر نکنيد با يک فنجان قهوه می توانيد مدت زيادی بيدار بمانيد. برای اينکه همچنان هوشيار بمانيد، بايد حدودا هر 20 دقيقه يکبار يک ليوان قهوه بخوريد. چهارم اينکه کسانی که ناراحتی قلبی دارند از قهوه استفاده نکنند، چون ظاهرا به صورت کوتاه مدت باعث افزايش ضربان قلب می شود.

راهبرد ديگر برای دير خوابيدن اين است که تمرين کنيد تا بتوانيد به اين موضوع که "ممکن است خوابتان بيايد" فکر نکنيد! حداقل اين چنين افکاری بر روی من اثر دارد و باعث می شود زودتر خوابم بيايد.

البته روش های بالا برای افراد پستی که می خواهند برای امتحان فردا يا پس فردا آماده شوند و نگاهی مادی به علم دارند توصيه نمی شود.

Copyright © Ella Elviana

Probability and Quizes

nospam@example.com (Hadi Moshayedi) — Sat, 20 Oct 2007 15:48:13 -0400

فرض کنيد می خواهيد در يک امتحان چهار گزينه ای شرکت کنيد (که به ازای هر غلط 1/3 نمره ی منفی دارد)، و هيچ مطالعه ای راجع به موضوع اين امتحان نداريد و قصد داريد شانس خود را امتحان کنيد و گزينه هايي را به صورت تصادفی انتخاب کنيد. چند درصد احتمال دارد که امتياز شما منفی نباشد؟ (البته با این فرض ها که احتمال درست پاسخ دادن به سوال 25% و احتمال شير آمدن سکه 50% می باشد.)

برای امتحان 1 سواله: 25%

برای امتحان 5 سواله: 36%

برای امتحان 6 سواله: 46%

برای امتحان 7 سواله: 55%

برای امتحان 8 سواله: 63%

برای امتحان 9 سواله: 39%

برای امتحان 10 سواله: 47%

برای امتحان 20 سواله: 58.51%

برای امتحان 30 سواله: 48.57%

...

پس اگر می خواهيد در امتحانی 9 سواله شانس خود را امتحان کنيد، تنها به 8 سوال اول پاسخ دهيد! به اين ترتيب شانس ضايع نشدن شما 24% افزايش می يابد.

حال فرض کنيد همراه خود سکه ای سر جلسه ی امتحان برده ايد و به اين شيوه عمل می کنيد: قبل از پاسخ به هر سوال سکه می اندازيد، اگر شير آمد يکی از گزينه ها را به صورت تصادفی انتخاب می کنيد، و گرنه هيچ گزينه ای را انتخاب نمی کنيد و به سراغ سوال بعدی می رويد.

در اين صورت احتمال اينکه امتياز شما منفی نشود:

برای امتحان 1 سواله: 62 %

برای امتحان 5 سواله: 50.6 %

برای امتحان 6 سواله: 52.41 %

برای امتحان 7 سواله: 52.83 %

برای امتحان 8 سواله: 52.41 %

برای امتحان 9 سواله: 51.79 %

برای امتحان 10 سواله: 51.37 %

برای امتحان 20 سواله: 51.13 %

برای امتحان 30 سواله: 50.95 %

...

Reinventing the wheel

nospam@example.com (Hadi Moshayedi) — Sat, 20 Oct 2007 13:37:56 -0400

احتمالا اختراع دوباره ی چرخ کار درستی نيست،

ولی احتمالا برای ساختن يک چرخ بهتر، بايد با چگونگی اختراع چرخ آشنا شويم،

و برای به دست آوردن درک بهتر، يک چرخ بسازيم.

Paratroopers

nospam@example.com (Hadi Moshayedi) — Wed, 10 Oct 2007 04:13:56 -0400

مساله:جدولی mxn داريم که در برخی از خانه های آن درختی قرار گرفته است. در بالای هر ستون و در سمت چپ هر سطر تفنگی قرار گرفته است که با شليک کردن آن تفنگ تمام درختان موجود در آن سطر يا ستون نابود می شوند. شليک کردن هر کدام از تفنگ ها هزينه ای دارد. می خواهيم زيرمجموعه ای از اين تفنگ ها را شليک کنيم به طوری که تمام درختان قطع شوند و حاصل ضرب هزينه ها کمينه شود. (این مساله، یکی از مسائل مسابقه ی انتخابی دانشگاه امیرکبیر در سال 1385 بود. لینک مساله در سایت acm.zju.edu.cn)

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

و در انتها جواب مساله ی اصلی برابر خواهد بود با:

خوب، برای حل کردن اين مساله، گرافی به شکل زير می سازيم:

که در گراف بالا r1 … r6 متناظر با سطرها می باشند و c1 … c9 متناظر با ستون ها می باشند. از s به هر کدام از سطرها يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن سطر می باشد، و از هر کدام از ستون به t يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن ستون می باشد. همچنين بين ri و cj يالی به وزن بی نهايت متصل می کنيم در صورتيکه در مکان [i,j] جدول درختی موجود باشد.

همچنين عمل انتخاب تفنگ يک سطر را متناظر با حذف کردن يال بين s و آن سطر در نظر می گيريم و عمل انتخاب تفنگ يک ستون را متناظر با حذف کردن يال بين آن ستون و t در نظر می گيريم.

حالا انتخابی از تفنگ ها را در نظر بگيريد که تمام درخت ها را قطع کند. خاصيت اين انتخاب چيست؟ خاصيت اين انتخاب اين است که به ازای هر يال ri به cj (که متناظر با يک درخت می باشد) بايد حداقل يکی از يال های s به ri (که متناظر با تفنگ سطر می باشد) و cj به t (که متناظر با تفنگ ستون می باشد) حذف شده باشد (که متناظر با انتخاب شدن آن تفنگ می باشد). نتيجه ی اين عمل چيست؟ نتيجه ی اين عمل اين است که هيچ مسيری از s به t وجود نخواهد داشت که از اين يال ri به cj عبور کند (چون فقط يک مسير اين چنين داشتيم، و حال با حذف حداقل يک يال از آن، اين تنها مسير را هم از بين می بريم.)

پس اگر بخواهيم تمام درخت ها را از بين ببريم، نبايد هيچ مسيری بين s و t باشد.

بنابراين مساله ی ما تبديل شد به حذف کردن تعدادی از يال های گراف مذکور به طريقی که هيچ مسيری بين s و t نباشد و مجموع وزن های اين يال های انتخاب شده کمينه باشد. اين جمله شما را به ياد چه مساله ی مشهوری می اندازد؟

احتمالا اکثر شما با مساله ی مشهور Minimum Cut آشنا هستيد. اگر آشنا نيستيد:

مساله ی Minimum Cut: می خواهيم تعدادی از يال های يک گراف را حذف کنيم به طوری که هيچ مسيری بين مبدا و مقصد نباشد و مجموع هزينه های يال های حذف شده می نيمم باشد.

و اگر با روش حل اين مسال آشنا نيستيد، بايد عرض کنم که جواب اين مساله (کمترين هزينه) با جواب مساله ی Maximum Flow يکی می باشد. اگر با اين مساله و طريقه ی حل آن آشنا نيستيد، به لينک 1 و لينک 2 مراجعه کنيد.

بنابراين برای حل کردن مساله، پس از ساختن گراف مذکور، با يکی از الگوريتم های معروف Maximum Flow، جواب مساله را بدست می آوريم! به همين سادگی و زيبايي!

Tanenbaum-Torvalds debate

nospam@example.com (Hadi Moshayedi) — Fri, 07 Sep 2007 20:04:00 -0400

29 ژانويه ی سال 1992، آندرو اس. تتنباوم: "لینوکس منسوخ شده است" (لینک بحث در گروه کاربران minix)

توضيح: نظر آندرو تننباوم این بود که سیستم های مدرن به سمت معماری ريزهسته (Micro-Kernel Architecture) حرکت می کنند، در حالیکه لینوکس دارای معماری یکپارچه (Monolothic Architecture) بود (و هست.)

برخی بخش های جالب و بامزه از این بحث:

Andy Tanenbaum says:

At most of you know, MINIX is a hobby

Linus Benedict Torvalds answers:

Re 1: you doing minix as a hobby - look at who makes money off minix, and who gives linux out for free. Then talk about hobbies. Make minix freely available, and one of my biggest gripes with it will disappear. Linuxhas very much been a hobby (but a serious one: the best type) for me: I get no money for it, and it's not even part of any of my studies in the university. I've done it all on my own time, and on my own machine.

Andy Tanenbaum says:

My real job is a professor and researcher in the area of operating systems.

Linus Benedict Torvalds answers:

your job is being a professor and researcher: That's one hell of a good excuse for some of the brain-damages of minix. I can only hope (and assume) that Amoeba doesn't suck like minix does.

Andrew S. Tanenbaum says:

MINIX is a microkernel-based system. ... Linux is a monolithic style system.

Linus Benedict Torvalds answers:

If this was the only criterion for the "goodness" of a kernel, you'd be right. What you don't mention is that minix doesn't do the micro-kernel thing very well, and has problems with real multitasking (in the kernel). If I had made an OS that had problems with a multithreading filesystem, I wouldn't be so fast to condemn others: in fact, I'd do my
damndest to make others forget about the fiasco.

Linus Benedict Torvalds says:

PS. I apologise for sometimes sounding too harsh: minix is nice enough if you have nothing else. Amoeba might be nice if you have 5-10 spare 386's lying around, but I certainly don't. I don't usually get into flames, but I'm touchy when it comes to linux

Andy Tanenbaum says:

I still maintain the point that designing a monolithic kernel in 1991 is a fundamental error. Be thankful you are not my student. You would not get a high grade for such a design

Linus Benedict Torvalds answers:

Well, I probably won't get too good grades even without you: I had an argument (completely unrelated - not even pertaining to OS's) with the person here at the university that teaches OS design. I wonder when I'll learn

Stencil Shadow Volumes Using OpenGL

nospam@example.com (Hadi Moshayedi) — Mon, 03 Sep 2007 13:48:13 -0400

اگر می خواهید با استفاده از OpenGL بتوانيد سايه های نسبتا واقعی ايجاد کنید:

1. ابتدا مفهوم و چگونگی کار با Stencil Buffer را یاد بگیرید. برای این کار، به مطلب آموزشی Clipping & Reflections Using the Stencil Buffer مراجعه کنید. اگر همچنان مشکل داشتید، می توانید به OpenGL SuperBible مراجعه کنید.

2. مقاله ی The Theory of Stencil Shadow Volumes را مطالعه کنید تا دیدی کلی از چگونگی ایجاد سایه با استفاده از Stencil Buffer پیدا کنید.

3. مقاله ی Volume Shadows Tutorial را مطالعه کنید تا هم مروری بر مطالبی که تا حالا خوانده اید باشد و هم کمی با جزئیات پیاده سازی آشنا شوید.

4. اکنون مطب آموزشی NeHe OpenGL Tutorials #27: Shadows را مطالعه کنید و حتما سعی کنید تمام جزئیات مربوط به ایجاد سایه را درک کنید. اگر لازم شد، به OpenGL Reference Manual مراجعه کنید تا با توابع نا آشنا آشنا شوید.

5. حتما سعی کنید خودتان یک سیستم سایه پیاده سازی کنید. و گرنه خوب یاد نخواهید گرفت!

توضيحات:

1. بسیاری از بازی های کامپیوتری سه بعدی با کیفیت بالا، مثل Doom III، از این تکنیک برای ایجاد سایه ها استفاده می کنند. (چند تصویر از سایه ها در Doom 3)

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

3. مهم: علاوه بر این تکنیک، تکنیک های دیگری برای ایجاد سایه وجود دارد. مثل: Shadow Texture Mapping و Shadow Projection.

چند تصویر از نتایج برنامه ی من که بالاخره پس از چند ساعت موفق شدم به یک نتیجه ی قابل قبول برسم:

Stencil Buffer and Glut

nospam@example.com (Hadi Moshayedi) — Fri, 31 Aug 2007 15:48:31 -0400

Don't forget to enable the Stencil Buffer when initializing or you will be سر کار for many hours!

glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH | GLUT_STENCIL);

Comment: Stencil Buffer is used in computer graphics to create some realistic cool effects like Shadows and Mirrors.

Words of Wisdom II

nospam@example.com (Hadi Moshayedi) — Wed, 29 Aug 2007 07:55:59 -0400

از صحیفه ی سجادیه - دعای بیستم - در خوی های نيکو و کردار پسندیده :

بارخدايا، بر محمّد و خاندانش درود فرست و توفيقم ده تا با کسی که به من ناراستی کرده راستی کنم، به کسی که از من دوری گزيده نيکی کنم، کسی را که محرومم ساخته به احسان بنوازم، با کسی که رشته ی دوستی بريده بپيوندم، کسی را که از من به بدی ياد کرده به نيکی ياد کنم و همواره خوبی را سپاس گويم و از بدی چشم فرو پوشم.
...

بارخدايا، آن آرزو و بدگمانی و رشک را که شيطان در دلم اَفکند، به يادِ عظمتت، تفکر در قدرتت، و تدبير بر دشمنت، دگرگون ساز؛ و آنچه از سخنِ زشت و بيهوده، يا دشنام، يا ريختن آبرو، يا گواهیِ نادرست، يا غيبت مومن غايب، يا ناسزا گفتن به حاضر و همانند اينها، که شيطان بر زبانم روان می سازد، تو آن را به حمد و سپاست، افزونی در ثنايت، بيان مجد و عظمتت، سپاس نعمتت، اقرار به احسانت و شمارشِ نعمت هايت بدل فرما.

از صحیفه ی سجادیه - دعای چهلم - یاد مرگ :

بارخدايا، بر محمّد و خاندانش درود فرست و ما را از آرزوهای دور و دراز در امان بدار، و با کردار درست عمر آرزوها را به کوتاهی آر، آن سان که آرزو نکنيم ساعتی به ساعتی ديگر رسانيم، روزی را به روزی، نَفَسی را به نَفَسی، يا گامی را به گامی بپيونديم.

بارخدايا، ما را از فريب آرزوها به سلامت دار، از شرّ آن در پناه خود آر، مرگ را در برابرمان دار، و لحظه ای غفلت از آن را بر ما روا مدار.

از کردار شايسته، آن چنان بهره مندمان ساز، که از دير شدن بازگشت به سوی تو انديشناک شويم، و برای ديدارت لحظه بشماريم، چنانکه مرگ سرای آرامش ما باشد، که دل بدان بنديم، و آشيانِ آسايش ما باشد، که به سويش بال بگشاييم، و پناهگاه ما باشد، که نزديک شدنش را دوست بداريم.

Automatic Switching

nospam@example.com (Hadi Moshayedi) — Mon, 13 Aug 2007 23:08:25 -0400

داستان عجيب و غريب اختراع دستگاه سوئيچينگ خودکار تلفن از کتاب "شبکه های کامپيوتری" نوشته ی "اندرو اس. تَنن بام":
اختراع دستگاه سوئيچينگ خودکار تلفن داستان جالبی دارد: اين دستگاه در قرن نوزدهم در ايالت ميسوری توسط فردی به نام آلمون ب. استراوگر، که شغل وی کفن و دفن بود، اختراع شد. در آن روزها وقتی کسی می مُرد، يکی از بازماندگان وی با اپراتور تلفن شهر تماس می گرفت و می گفت: «لطفا مرا به يک موسسه کفن و دفن وصل کنيد.» در شهر آقای استراوگر دو موسسهء کفن و دفن وجود داشت، و از شانس بد اين آقا، اپراتور تلفن همسر رقيب بود. آقای استراوگر خيلی زود دريافت که اگر می خواهد ورشکست نشود، بايد يک دستگاه سوئيچينگ خودکار تلفن اختراع کند – و اين کار را کرد. همه ی آنهايي که در سراسر دنيا با دستگاههای سوئيچينگ خودکار تلفن سروکار دارند، آنها را با نام «دستگاه استراوگر» می شناسند. (تاريخ نمی گويد آيا اين خانم بعد از بيکار شدن توانست شغلی مانند اپراتور اطلاعات تلفن – که بايد به سوالاتی از قبيل «لطفا شماره يک موسسهء کفن و دفن را بدهيد» پاسخ دهد – بدست آورد يا خير؟)

Introducing TurboGears - Part 2

nospam@example.com (Hadi Moshayedi) — Sat, 11 Aug 2007 06:17:06 -0400

در قسمت اول، اندکی با امکاناتی که TurboGears در رابطه با مدل داده ای، کنترلرها، لايه ی نمايش در اختيار می گذارد آشنا شديم. در اين بخش می خواهم مثال های بيشتری در رابطه با مدل داده ای مطرح کنم تا بيشتر با امکانات TurboGears آشنا شويد.
قبل از شروع، لازم به يادآوری است که هدف از اين سری نوشته ها آشنا کردن شما با TurboGears و امکانات آن با استفاده از تعدادی مثال کوچک است. يعنی اينکه هدف من آموزش TurboGears نيست. اگر مايل به ياد گرفتن TurboGears هستيد، به لينک های زير مراجعه کنيد:
+ TurboGears Tutorial
+ مستندات TurboGears
+ ويدئوی The 20 Minutes Wiki: اين ويدئو که توسط ابداع کننده ی TurboGears یعنی Kevin Dangoor ايجاد شده، نشان می دهد که چگونه می توان با استفاده از TurboGears در مدت 20 دقيقه يک سيستم Wiki ساخت.

آشنايي بيشتر با مدل داده در TurboGears
در قسمت قبل چندين مثال ساده در رابطه با مدل داده ای مطرح کرديم. در اين قسمت مثال های بيشتری مطرح می کنم.
همان طور که قبلا گفتم، برای مشخص کردن نوع و مشخصات پايگاه داده ی مورد استفاده در برنامه ی تحت وبمان، بايد فايل dev.cfg را تغيير دهيم و سطری مشابه سطر زير در آن ايجاد کنيم:

sqlobject.dburi = "sqlite:///home/brian/tutorial/tutorial.sqlite"

در مثال بالا، نوع پايگاه داده ی مورد استفاده (sqlite) و مسيری که فايل پايگاه داده در آن ذخيره می شود ذکر شده است. در زير چند مثال ديگر مشاهده می کنيد که پايگاه داده هايي از نوع MySQL و PostgreSQL را مشخص می کنند:

mysql://user:password@host/database
mysql://host/database?debug=1
postgres://user@host/database?debug=&cache=
postgres:///full/path/to/socket/database
postgres://host:5432/database

برای ايجاد کردن ارتباط يک به چند:

class Address(SQLObject):
Country = StringCol()
City = StringCol()
StreetAddress = StringCol()
Owner = ForeignKey("Person")

class Person(SQLObject):
name = StringCol()
addresses = MultipleJoin('Address')

در مثال بالا، هر آدرس متعلق به تنها يک شخص است، ولی يک شخص می تواند دارای چندين آدرس باشد.
مثال ديگر در ارتباط با تعريف جداول همراه با توضيحات:

class Person(SQLObject):
email = StringCol(alternateID = True)# email is an index column for the table
name = StringCol(unique = True)# no duplicate values for name
birthdate = DateCol(notNone = True)# birthdate cannot be without value
maritalStatus = EnumCol(enumValues=['Single', 'Married'], default='Single')# maritalStatus can be either 'Single' or 'Married', and its default value is 'Single'

لازم به ذکر است که هر کدام از جداول به طور پيش فرض دارای فيلدی به نام id هستند که به عنوان Primary Key به کار می رود.برای انتخاب رکوردها با استفاده از مقادير فيلد ها:

result = Person.selectBy(name = "Hadi", maritalStatus = 'Single')

برای انتخاب رکوردها با استفاده از فيلدهای ايندکس:

result = Person.byEmail('hadi@pykello.net')

برای مشخص کردن Query با استفاده از زبان SQL:

result = Person._connection.queryAll('Select * from Person')

برای بدست آوردن تعداد رکوردها موجود در نتيجه:

count = result.count()

برای بدست آوردن رکورد اول موجود در نتيجه و تغيير يکی از فيلدهای آن:

firstPerson = result[0]
firstPerson.name = "Hadi Moshayedi"

TurboGears برای ارتباط با پايگاه داده از SQLObject استفاده می کند. برای آشنايي بيشتر با امکانات SQLObject به مستندات SQLObject مراجعه کنيد.

Introducing TurboGears - Part 1

nospam@example.com (Hadi Moshayedi) — Fri, 10 Aug 2007 13:54:27 -0400

در اين بخش و بخش های بعدی به معرفی TurboGears، فريم ورکی برای توليد برنامه های تحت وب خواهم پرداخت. هدف من از اين سری مطالب آموزش TurboGears نيست، بلکه می خواهم شما حسی نسبت به چگونگی توليد برنامه های کاربردی تحت وب با استفاده از TurboGears و امکاناتی که در اختيار شما قرار می دهد پيدا کنيد، و بتوانيد تصميم بگيريد که آيا TurboGears برای نيازهای شما مناسب است يا نه.

TurboGears چيست؟
TurboGears يک زبان جديد نيست، بلکه يک سری ابزار و کتابخانه ی برنامه نويسی است که با استفاده از آن می توانيد برنامه های تحت وب ايجاد کنيد. زبان برنامه نويسی که TurboGears از آن استفاده می کند Python است.
TurboGears مبتنی بر معماری Model-View-Controller می باشد و برنامه نويس را هدايت به جدا کردن اين سه لايه از يکديگر می کند.

مدل داده ای
ديگر در TurboGears نيازی به نوشتن دستورات پيچيده ی SQL نيست. مثلا اگر بخواهيم يک جدول به نام User داشته باشيم که دارای فيلدهای name و email باشد، کافی است کلاسی به اسم User که از کلاس SQLObject مشتق می شود ايجاد کنيم:

class User(SQLObject):
name = StringCol()
email = StringCol()

و اگر بخواهيم هر User دارای چندين دوست باشد (ارتباط چند-به-چند):

class User(SQLObject):
name = StringCol()
email = StringCol()
friends = MultipleJoin('User')

و البته اين کلاس ها می توانند دارای تابع هم باشند:

class User(SQLObject):
…
def FriendCount():
return friends.count()

اکنون اگر بخواهيم يک سطر به جدول User اضافه کنيم، کافی است يک شیء از نوع User ايجاد کنيم:

hadi = User(name = "Hadi", email = "hadi@pykello.net")

اگر بخواهيم اين سطر را در پايگاه داده تغيير دهيم، کافی است که دستور زير را اجرا کنيم:

hadi.email = "irancoldfusion@yahoo.com"

و برای حذف اين سطر از جدول:

hadi.destroySelf()

و اگر بخواهيم يک User که فيلد name آن برابر با Hadi است را از جدول پيدا کنيم:

result = User.selectBy(name = "Hadi")

در TurboGears، جداول را در فايل model.py تعريف می شوند، و برای مشخص کردن نوع پايگاه داده ی مورد استفاده (MySQL، PostgreSQL، SQLite، ...) و مشخصات آن، سطری مانند سطر زير در فايل dev.cfg استفاده می کنيم:

sqlobject.dburi = "sqlite:///home/brian/tutorial/tutorial.sqlite"

همان طور که مشاهده می کنيد، در TurboGears کاری به جزئياتی مانند ايجاد ارتباط با پايگاه داده، نوشتن دستورات SQL، ... نداريم. و همچنين با رکوردهای موجود در پايگاه داده مانند اشياء رفتار می کنيم.البته در صورت نياز، می توان با اين جزئيات کار داشت، و سطح پائين تر کار کرد، ولی اين نيازها کمتر به وجود می آيند.
خيلی خوبه، مگه نه؟
در قسمت های بعدی بيشتر به بحث امکاناتی که TurboGears در رابطه با مدل داده ای در اختيار ما می گذارد خواهم پرداخت.

کنترلرها
رفتار برنامه ی شما در فايل controllers.py توصيف می شود.
توجه: در ادامه فرض می کنم که URL برنامه ی ما http://localhost/ است.
مثلا اگر می خواهيد صفحه ی http://localhost/ (و همچنين http://localhost/index) عبارت Hello World! را نمايش دهد:

class Root(controllers.RootController):
@expose()
def index(self):
return"Hello World!"

در واقع کلاس Root متناظر با مسير اصلی (يعنی http://localhost/ ) متناظر است، و توابع کلاس Root متناظر با صفحات شما.
حال اگر بخواهيم پارامترهايي را به يک صفحه پاس کنيم:

class Root(controllers.RootController):
…
@expose()
def showmessage(self, name = "Hadi"):
return"Hello " + name

حال اگر با استفاده از مرورگر وب مسير http://localhost/showmessage را مشاهده کنيد، عبارت Hello Hadi را مشاهده می کنيد، و مسير http://localhost/showmessage?name=pykello عبارت Hello pykello را نمايش می دهد.

اکنون اگر بخواهيم آدرس ايميل کاربری را از پايگاه داده استخراج کنيم و نمايش دهيم:

class Root(controllers.RootController):
…
@expose()
def showemail(self, name="hadi"):
result = User.selectBy(name = name)
if result.count() == 0:
return"No such user!"
else:
return"The email address is " + result[0].email

در صورتی که هيچ تابعی برای مديريت صفحه ی مورد نظر موجود نباشد، تابع default فراخوانی می شود:

class Root(controllers.RootController):
…
@expose()
def default(self, methodname):
return methodname + " not found"

اگر بخواهيم آدرس هايي با فرمت http://localhost/~username آدرس ايميل متناظر با username را نشان دهد:

class Root(controllers.RootController):
…
@expose()
def default(self, methodname):
ifre.match("^~[\w\d]+$", methodname): # a regular expression matching
return showemail(methodname[1:])# i.e. suffix starting from second character
else:
return"Page not found!"

لايه ی نمايش
مثال هايي که در بخش قبلی نشان داديم، تنها متن ساده به عنوان خروجی ايجاد می کردند. اگر بخواهيم صفحات خوشگل ايجاد کنيم، روش بخش قبل کثيف و پردردسر است.
TurboGears اين امکان را در اختيار ما می گذارد که لايه ی نمايش را با استفاده از template ها توصيف کنيم.مثلا، اگر مسيری که پروژه ی ما در آن ذخيره شده باشد c:\tutorial باشد، برای اينکه يک تابع در لايه ی کنترلر از template موجود در c:\tutorial\tutorial\templates\user.kid استفاده کند:

class Root(controllers.RootController):
…
@expose(template="tutorial.templates.user")
def showemail(self, name = "hadi"):
result = User.selectBy(name = name)
returndict(name = name, email = result[0].email)

و فايل user.kid:

<html>
<head><title>Welcome to TurboGears!</title></head>
<body>The email address for user $name is $email .</body>
</html>

در قسمت های بعدی بيشتر به ايجاد template ها و امکانات خواهم پرداخت.

Where is the Sun-day?

nospam@example.com (Hadi Moshayedi) — Sun, 05 Aug 2007 00:53:48 -0400

Life is going into reverse ...

Daily Comment

nospam@example.com (Hadi Moshayedi) — Sun, 20 May 2007 10:04:33 -0400

می توان برای مدتی به یک نقطه زُل زد و از این زُل زدن لذت هم برد، مگر این که اجباری در کار باشد.

These words he writes ...

nospam@example.com (Hadi Moshayedi) — Sat, 19 May 2007 04:42:20 -0400

بهشت سبز به خانه ام می آید،

و من خاکستری می گریم،

خاکستری، خاکستری، خاکستری، ...

------------------------------

میز مواخذه و جایگاه محاکمه و روز بازخواست

آشوب در پس جبینم

به نابخشوده ترین راه

آه، به نابخشوده ترین راه

من میان روشنی و تاریکی تاب می خورم ...

Ivan and the bugs

nospam@example.com (Hadi Moshayedi) — Tue, 15 May 2007 12:58:52 -0400

امروز به بررسی مساله Collecting Bugs که یکی از سوالات ACM/ICPC 2004 NEERC Northern Subregional و همچنین یکی از سوالات آخرین مسابقه هفتگی ما بود می پرازم.

صورت سوال: n نوع شیء آبی و از هر کدام به اندازه ی بی نهایت و s نوع شیء زرد و از هر کدام به اندازه ی بی نهایت داریم. هر روز یک شیء آبی و یک شیء قرمز را به تصادف انتخاب می کنیم. هنگامی که از هر نوع شیء آبی حداقل یکی و هر نوع شیء قرمز حداقل یکی انتخاب کرده باشیم دیگر ادامه نمی دهیم. می خواهیم امید ریاضی تعداد روزهایی که به آخر کار می رسیم را پیدا کنیم.

طبق تجربه، در چنین مواردی که حداکثر تعداد روزها معلوم نیست، نباید به راه حلی که به ازای هر مقداری احتمال رخداد آن را حساب کرد و جمع حاصل ضرب مقادیر در احتمالات نتیجه را حساب کرد. و باز هم طبق چندین سوال احتمالاتی که تا حالا دیده ام، این گونه مسائل اکثر با برنامه سازی پویا قابل حل شدن می باشند. برای آشنایی و یادگیری بیشتر در باره ی مسائل احتمالاتی در مسابقات برنامه نویسی و دیدن چندین مثال دیگر به مقاله ی Understanding Probabilities سایت Topcoder مراجعه کنید.

فرض کنید F_i,j امید ریاضی حالتی باشد که در آن تعداد اشیاء آبی که تا به حال هیچ وقت انتخاب نشده اند i و تعداد اشیاء قرمز که تا به حال هیچ وقت انتخاب نشده اند برابر j باشد. چندین حال برای جفت i و j داریم:

1- i = 0 و j = 0: در این صورت دیگر لازم نیست هیچ روزی ادامه دهیم و جواب برابر با 0 خواهد بود.

2- i = 0 و j != 0: به هر حال باید یک روز انتخاب را انجام دهیم. در این روز به احتمال j/s شیء زردی که قبلا هیچ وقت انتخاب نکردیم را انتخاب می کنیم و در روز های بعد باید با j-1 شی انتخاب نشده ی زرد ادامه دهیم، و با احتمال s-j)/s) یکی از اشیاء زردی را که قبلا انتخاب کردیم را انتخاب می کنیم و در روز های بعد باید با j شی انتخاب نشده ی زرد ادامه دهیم. بنابراین F_i,j در این حالت برابر خواهد بود با:

که با ساده کردن معادله ی بالا برای F_0,j بدست می آوریم:

3- حالت سوم وقتی i != 0 و j = 0. با استدلالی مشابه حالت قبلی برای این حالت بدست خواهیم آورد:

4- حالتی که i != 0 و j != 0: در این صورت با احتمال i/n \* j/s شیء آبی جدید و شیء زرد جدیدی انتخاب خواهیم کرد، با احتمال n-i)/n \* j/s) شیء زرد جدید انتخاب خواهیم کرد ولی شیء آبی جدیدی انتخاب نمی کنیم، ... که در این صورت F_i,jبرابر خواهد بود با:

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

و کد من برای حل این مساله:

#include <iostream>
#include <string>
#include <iomanip>
usingnamespace std;
int n, s;
double mat[1002][1002];
int main()
{
cin>> n >> s;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= s; j++)
if(i == 0&& j == 0)
mat[i][j] = 0;
elseif(i == 0)
mat[i][j] = mat[i][j-1] + (double)s / j;
elseif(j == 0)
mat[i][j] = mat[i-1][j] + (double)n / i;
else
{
mat[i][j] = 1 + (mat[i-1][j-1] \* (double)(i \* j) +
mat[i-1][j] \* i \* (double)(s - j) +
mat[i][j-1] \* (double)(n - i) \* j) / (double)(s \* n);
mat[i][j] /= 1 - (double)(n - i) \* (double)(s - j) / (s \* n);
}
cout.precision(4);
cout.setf(ios::fixed | ios::showpoint);
cout<< mat[n][s]<< endl;
return0;
}

At the data-structure department of Macrohard!

nospam@example.com (Hadi Moshayedi) — Tue, 15 May 2007 01:45:29 -0400

امروز به بررسی مساله ی K-th Number که یکی از سوالات ACM/ICPC 2004 NEERC Northern Subregional و همچنین آخرین مسابقه ی هفتگی ما بوده می پردازم.

صورت مساله این است که n تا عدد داریم و می خواهیم پرسش هایی از نوع: "k-امین کوچکترین عدد در بین اعداد i-ام تا j-ام چیست؟"

مثلا اگر n عدد ما عبارت باشند از: {1,5,2,6,3,7,4} ، سومین کوچکترین عدد بین اعداد 2-ام تا 5-ام (یعنی {5,2,6,3} ) برابر 5 می باشد و اولین کوچکترین عدد بین اعداد 4-ام تا 4-ام برابر 6 می باشد.

بدیهی ترین راه این است که برای هر پرسش اعداد i-ام تا j-ام را مرتب کنیم و k-امین کوچکترین را به عنوان خروجی چاپ کنیم. ولی در این صورت برای پاسخ به هر پرسش زمانی از مرتبه ی (O(n*log n صرف خواهیم کرد که با توجه به اینکه حداکثر 5000 پرسش از این نوع را می خواهیم پاسخ دهیم این راه حل چندان مناسب نمی باشد.

کلید اصلی حل این سوال این است که می توانیم به پرسش "چند عدد کوچکتر یا مساوی عدد m در بین اعداد a-ام تا b-ام وجود دارد؟" در زمان (O(log² n پاسخ داد. در نتیجه با استفاده از پاسخ این پرسش و جستجوی دودوئی می توان هر پرسش را در زمان (O(log³ n پاسخ داد. در زیر شبه-کد مربوط به این قسمت را مشاهده می کنید:

# arr[0..n-1] is the sorted version of input array
# We want to answer: Find k-th smallest number among a-th to b-th numbers
Left = 0
Right = n-1
Result = arr[Right]
while Left <= Right:
Mid = (Left + Right) / 2
if Count(a, b, arr[Mid])< k:
Left = Mid + 1
else
Result = arr[Mid]
Right = Mid - 1

حال، به بررسی اینکه چگونه می توان تعداد اعداد کوچکتر یا مساوی یک عدد را بین اعداد a-ام تا b-ام به دست آورد می پردازیم. برای این کار، از درختی دودوئی استفاده می کنیم. مثلا برای مثال بالا این درخت به شکل زیر خواهد بود:

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

بدیهی است که می توان هر بازه را معادل با یک سری گره در این درخت در نظر گرفت که تعداد آن گره ها از مرتبه (O(log n می باشد. مثلا برای بازه ی 2 تا 7، گره های 3-2 و 7-4، برای بازه ی 3 تا 5 گره های 3-3 و 5-4 و ...

با استفاده از جستجوی دودوئی می توان مشخص کرد که در یک آرایه ی مرتب چند عدد کوچکتر یا مساوی یک عدد خاص وجود دارد. پس برای مشخص کردن تعداد اعداد کوچکتر مساوی یک عدد در بازه ای خاص، گره های مربوط به آن بازه را در درخت پیدا می کنیم و با استفاده از جستجوی دودوئی در آرایه ی مربوط به هر گره تعداد اعداد کوچکتر مساوی در کل بازه را بدست می آوریم. پیچیدگی زمانی این مرحله از مرتبه ی (O(log² n می باشد.

حالا توضیح می دهیم که درخت بالا را چگونه می سازیم. برای ساختن درخت بالا از یک آرایه استفاده می کنیم که عنصر با اندیس یک ریشه ی درخت می باشد و فرزندان گره با اندیس i گره هایی با اندیس های 2i و 2i+1 می باشند. در این آرایه، برای هر گره نگه می داریم که آرایه ی مرتب شده مربوط به آن گره در کجا قرار دارد. من در راه حل خودم آرایه های مرتب شده را در یک آرایه ی دیگر ذخیره کرده ام و در آرایه ی اصلی برای هر گره اندیس شروع و طول مکانی که آرایه ی مرتب شده مربوط به آن گره در آن قرار دارد را نگهداری می کنیم.

در زیر تابع مربوط به ایجاد این درخت را مشاهده می کنید:

int arr[100000]; // Contains the original information
int mem[2000000]; // Container for node sorted-arrays
int heap[250000][2]; // The Actual Tree
int cnt = 0; // Shows how many items has been inserted into Len till now
void Create(int idx, int Len, int root)
{
if(Len == 0)
return;
for(int i = 0; i < Len; i++)
mem[cnt+i] = arr[idx+i];
sort(mem+cnt, mem+cnt+Len);
heap[root][0] = cnt;
heap[root][1] = Len;
cnt += Len;
if(Len == 1)
return;
Create(idx, Len / 2, root \* 2);
Create(idx + Len / 2, Len - Len / 2, root \* 2 + 1);
}

این تابع اندیس شروع و طول قسمتی از آرایه را که می خواهیم به درخت اضافه کنیم و همچنین اندیس گرهی از درخت که این قسمت از آرایه به آن اضافه خواهد شد را می گیرد. برای درست کردن کل درخت، آن را با پارامترهای (Create(0,n,1 صدا می کنیم.

و بالاخره، به بررسی روش انتخاب گره های مناسب برای بدست آوردن جواب مساله می پردازیم. فرض کنید می خواهیم گره هایی از زیردرخت با ریشه ی root را انتخاب کنیم که بازه ی مربوط به هر کدام از این گره ها کاملا زیر مجموعه ای از بازه ی مورد نظر باشند و هیچ دو گرهی وجود نداشته باشد که پدرشان یکی باشد و بازه ی مربوط به پدرشان نیز زیر مجموعه ی بازه ی مورد نظر باشد. برای این کار، چند حالت وجود دارد:

1- بازه ی مربوط به root هیچ اشتراکی با بازه ی مورد نظر ندارد. در این صورت هیچ کدام از فرزندان root عضو مجموعه گره های مورد نظر نیست. و نیازی نیست فرزندانش را بررسی کنیم.

2- بازه ی مربوط به root زیرمجموعه ی بازه ی مورد نظر می باشد. در این صورت خود گره root داخل مجموعه گره های مورد نظر می باشد. و نیازی نیست فرزندانش را بررسی کنیم.

3- بازه ی مربوط به root زیر مجموعه ی بازه ی مورد نظر نمی باشد، ولی با بازه ی مورد نظر اشتراک دارد. در این صورت خود گره root داخل مجموعه ی گره های مورد نظر نمی باشد ولی تعدادی از گره های موجود در زیر درخت آن متعلق به این مجموعه می باشد. در این صورت فرزندان root را باید بررسی کنیم.

شبه کد تابع مربوط به انتخاب گره ها به شکل زیر خواهد بود:

function Select(root, Left, Right):
if[Left, Right]is subset of [a, b]:
# A new node has been found
# which is useful for us
elseif[Left, Right] intersects [a, b]:
Length = Right - Left + 1
Select(2 \* root, Left + Length / 2 - 1, Right)
Select(2 \* root + 1, Left + Length / 2, Right)

گمان کنم توضیحات بالا برای حل مساله ی مورد نظر کافی باشد. ولی اگر همچنان مشکلی داشتید یا پیشنهادی داشتید comment بگذارید!

این مساله مثال خوبی بود برای یادگیری کار کردن با درخت های دودوئی برای پاسخ دادن به query های مربوط به یک آرایه. برای تمرین بیشتر توصیه می کنم مسائل ساده تر زیر را نیز حل کنید:

- Potentiometers

- Unreal Story : که البته این سوال یک راه حل خیلی ساده تر و تمیزتر هم دارد. ولی به هر حال آن را می توان با این روش نیز حل کرد.

- Cryptography

TopCoder Exchange

nospam@example.com (Hadi Moshayedi) — Sat, 12 May 2007 06:12:37 -0400

قابل توجه مشترکان بازار بورس Topcoder! قیمت irancoldfusion در روزهای اخیر به شدت با کاهش روبرو بوده است و زمان خوبی برای خریدن سهام این handle می باشد. کارشناسان پیش بینی می کنند که قیمت سهام irancoldfusion افزایش چشم گیری در دو هفته ی آینده خواهد داشت.

هفته ی گذشته قیمت Chmel_Tolstiy افزایش چشم گیری داشت. ولی این handle برای خرید پیشنهاد نمی شود. چون احتمالا دفعات بعد سقوط خواهد کرد.

گزینه های مناسب دیگر که پیشنهاد می کنم: AdrianKuegel و PMH و HiltonLange و ltdtl.

------------------------------

پی نوشت: برای اطمینان از کم ریسک بودن سرمایه گذاری بر روی irancoldfusion در وضعیت فعلی، به پروفایل وی در سایت TJU مراجعه کنید!

Love, Life, and Contests!

nospam@example.com (Hadi Moshayedi) — Fri, 11 May 2007 12:38:42 -0400

سلام دوستان،

چند هفته است با وجود تلاش و تمرین فراوان، بدتر از قبل عمل می کنم، و نتایجم ظاهرا "شکستی" بیش نیست! به چند نمونه توجه کنید:

- پنج شنبه صبح، در مسابقه ی هفتگی Topcoder با وجود داشتن ایده ی درست برای هر دو سوال 250 امتیازی و 500 امتیازی، هیچ کدام را درست پیاده سازی نکردم و یکی Challenge و دیگری Failed System Test شد! و Rating ام 150 تا پایین آمد!

- پنج شنبه در مسابقه ی هفتگی دانشکده، با وجود داشتن اعتماد به نفس کافی و ایده ی درست برای سوال آخر، آن را درست پیاده سازی نکردم و چندین جواب Time Limit Exceeded ناراحت کننده دریافت کردم! گمان کنم اگر به راه حلم ایمان کافی می داشتم، حتما پس از گرفتن Time Limit Exceeded آن را درست می کردم و سرافکنده و شکست خورده به خوابگاه برنمی گشتم!

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

-----------------------------------------------------

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

Sabr, Copyrighted © 2007, Koodakanehaye man!

nospam@example.com (Hadi Moshayedi) — Fri, 11 May 2007 10:28:38 -0400

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

توزندگی هم اگه لکه ای روی یک صفحه اش افتاد برای پوشوندنش سریع شروعبه ورق زدن نکنید چون ممکنه صفحه های بعدی زندگی هم لکه دار شه!

صبر کنید...صبر!

فقط کاش..کاش..

کاش لکه اون قدر بزرگ نباشه که صبر هم راه حلش نباشه!

Welcome back!

nospam@example.com (Hadi Moshayedi) — Fri, 11 May 2007 10:25:11 -0400

به درود، دنیای زیبای آرزوهای من. فعلا، تا دیدار بعدی.

Art of life

nospam@example.com (Hadi Moshayedi) — Mon, 07 May 2007 11:08:17 -0400

از دفترچه خاطرات سریوژا در ششم می 2007:

"به این فکر بودم که در صفحه ی ششم دفترچه ی نقاشی ام چه بکشم ... ولی آن را دست نخورده و سفید رد کردم ..."

D'amour ou d'amitié

nospam@example.com (Hadi Moshayedi) — Mon, 30 Apr 2007 03:51:27 -0400

در مکان های خیلی خیلی دور، سیاره ای وجود دارد به نام لیمپاندایینین. جمعیت فعلی این سیاره کمتر از 20 نفر و شعاع آن متغیر است.

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

در این سیاره، هر اظهار نظری از روی محبت انجام می گیرد.

در این سیاره، زبان های برنامه نویسی به جای "Goto"، از "Please come with me to" و به جای while X do از while X let's do استفاده می کنند.

دیروز، پتیا، يکی از ساکنان این سیاره تصمیم به ترک سیاره گرفت. "اُ پتیای عزیز، لطفا پیش ما بمان"

اکثر گاوهای خال خالی دوست دارند بزغاله های بی خال لاغر را اذیت کنند. ولی، بتسی، گاو خال خالی سیاره ی ما، این طور نیست. او حتی به بزغاله های بی خال لاغر کمک هم می کند. حتی یک بار عاشق یکی از آن ها شده بود!

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

دیروز داشتم در این سیاره قدم می زدم و همراه با بقیه ی ساکنان این سیاره زمزمه می کردم:

"مانند جزیره ای هستم در یک اقیانوس بی انتها

چیزی برای گفتن ندارم،

ولی حاضرم زندگی ام را وقف تو کنم

..."

چه کسی می گوید بتسی آواز قناری ها را درک نمی کند؟!!

Virginia Tech Tragedy ...

nospam@example.com (Hadi Moshayedi) — Mon, 23 Apr 2007 04:57:13 -0400

تراژدی ويرجينيا تک که یادتون هست؟

The Change

nospam@example.com (Hadi Moshayedi) — Fri, 20 Apr 2007 07:40:40 -0400

نرم افزار وبلاگم را از Wordpress به Serendipity تغییر دادم. علت این کار هم این بود که Wordpress خیلی زور می گفت و بعضی از تغییرات دستی من در کد HTML مربوط به پست ها را تغییر می داد.

علاوه بر آن، Serendipity به طور پیش فرض تقویم شمسی و زبان فارسی را پیش فرض پشتیبانی می کند، دارای ویرایشگر بهتری است، و قابلیت انعطاف آن بیشتر است.

احتمالا دلیل اینکه Wordpress بیشتر به کار می رود این است که: 1. قدیمیتر است 2. استفاده کننده های آن زیاد است و کلی Plug-in برای آن ایجاد شده است.

چون تا یکی-دو هفته دیگر هاستینگ وب سایتم را عوض خواهم کرد، فعلا همه ی مطالب وب لاگ وردپرسم را به اینجا نیاوردم. می توانید مطالب وبلاگ قبلی را در آدرس blog.pykello.net/wp-index.php مشاهده کنید.

قالب فعلی وبلاگم تغییر یافته ی قالب Idea است. لطفا نظرات و پیشنهادات خودتان را درباره ی این قالب بیان کنید.

Sad News ...

nospam@example.com (Hadi Moshayedi) — Thu, 05 Apr 2007 07:16:00 -0400

از دفترچه خاطرات سریوژا در روز سوم آوریل 2007:

«... وای بر من! کوهی که به قله ی آن صعود کرده بودم از یخ بود و با طلوع آفتاب آب شد! ...»

Einstein's Chauffer

nospam@example.com (Hadi Moshayedi) — Thu, 05 Apr 2007 07:12:00 -0400

حکايتی واقعی درباره ی آلبرت اينشتين و نظريه ی نسبت او وجود دارد.

اينشتين پس از اينکه نظريه ی نسبيت مشهور خود را ارائه داد، به دانشگاه های مختلف ايالات متحده ی آمريکا می رفت و درباره ی نظريه ی خود سخنرانی می کرد. در طی اين سفرها، راننده ی باوفايش، هری، هميشه همراه او بود و در همه ی سخنرانی های او حضور داشت و در رديف عقب می نشست.

يک روز پس از يکی از سخنرانی ها، وقتی که اينشتين از سالن خارج شده بود و می خواست سوار اتومبيلش بشود، هری به او گفت: "پروفسور اينشتين، من سخنرانی شما را درباره ی نظريه ی نسبيت آن قدر شنيده ام که اگر به من فرصتی داده شود می توانم آن را کامل و بدون نقص ارائه دهم!"
اينشتين جواب داد: "خيلی خوب! من هفته ی بعد به دارتموث می روم. مرا آنجا نمی شناسند. تو آن جا به عنوان اينشتين سخنرانی کن، و من جای تو هری می شوم!"

و اين اتفاق افتاد ... هری سخنرانی را بدون عيب و نقص ارائه داد، بدون اينکه هيچ سخنی را اشتباه بگويد، و اينشتين در رديف عقب به عنوان "راننده" نشست و کمی چرت زد.

هنگامی که سخنرانی تمام شده بود و هری در حال پائين آمدن از جايگاه مخصوص بود، يکی از محققان جلوی او را گرفت و پرسشی درباره ی نظريه ی نسبيت از او پرسيد ... هری به محقق جواب داد: "پاسخ اين پرسش بسيار آسان است! در واقع، اين پرسش آنقدر ساده است که از راننده ام می خواهم تا پاسخ شما را بدهد!"

منبع: http://www.short-funny-stories.com/funny-stories/story-81.html

Words of Wisdom

nospam@example.com (Hadi Moshayedi) — Wed, 04 Apr 2007 07:06:00 -0400

حضرت علی(ع) می فرمایند: "هر کس اختیار خود را به دست آرزوهایش سپارد، ناگهان مرگ فرا رسد و او را از پای در آرد."

Base -1 + i

nospam@example.com (Hadi Moshayedi) — Tue, 03 Apr 2007 03:36:20 -0400

با استفاده از 1- + i به عنوان مبنای دستگاه اعداد، که در آن i برابر با می باشد، تمام اعداد صحيح مختلط (اعدادی که دارای يک قسمت حقيقی و يک قسمت موهومی می باشند) را می توان به صورت اعداد بدون علامت متشکل از دنباله ای از يک و صفر نمايش داد. و اين نمايش برای هر عددی يکتا می باشد. در ادامه به اثبات اين قضايا نخواهيم پرداخت، بلکه به توضيح مختصری درباره ی اين مبنا و روش بدست آوردن نمايش معادل يک عدد در اين دستگاه اعداد خواهيم پرداخت.

فرض کنيد می خواهيم نمايش عدد 2 در اين مبنا را بدست بياوريم. اين کار را می توانيم با استفاده از روش معمول تبديل مبنا انجام دهيم: يعنی 2 را بر 1- + i تقسيم کنيم، سپس خارج قسمت آن را بر 1- + i تقسيم کنيم، و اين کار را تا جايي انجام دهيم که خارج قسمت بدست آمده صفر شود. سپس با پشت سر هم گذاشتن باقيمانده های تقسيم ها نتيجه ی مورد نظر را بدست آوريم. می خواهيم باقيمانده های بدست آمده صفر يا يک باشند. برای اينکه ببينيم اين کار همواره ممکن است، فرض کنيد می خواهيم يک عدد صحيح دلخواه به فرم a + bi را بر 1- + i تقسيم کنيم. می خواهيم q و r را چنان پيدا کنيم که q يک عدد مختلط و r برابر 1 يا 0 باشد و رابطه ی زير برقرار باشد:

a + bi = (q_r + q_ii)(-1 + i) + r

که در آن q_r نشانگر قسمت حقيقی q و q_i نشانگر قسمت موهومی q می باشد. با برابر قرار دادن قسمت های موهومی و حقيقی و حل دو معادله ی دو مجهولی روابط زير برای q_r و q_i بدست می آيد:

q_r = (b - a + r) / 2
q_i = (-a - b + r) / 2

واضح است که اگر a و b هر دو زوج يا هر دو فرد باشند، با قرار دادن r = 0 ، q يک عدد صحيح مختلط خواهد بود و در صورتی که يکی از a و b فرد و ديگری زوج باشد، می توانيم r را برابر با 1 انتخاب کنيم تا q يک عدد صحيح مختلط شود.

در ادامه از روش بالا برای پيدا کردن نمايش عدد 2 در اين مبنا استفاده می کنيم:

مرحله ی اول: a = 2 و b = 0. در نتيجه q_r = -1 و q_i = -1 و r = 0.
مرحله ی دوم: a = -1 و b = -1. در نتيجه q_r = 0 و q_i = 1 و r = 0.
مرحله ی سوم: a = 0 و b = 1. در نتيجه q_r = 1 و q_i = 0 و r = 1.
مرحله ی چهارم: a = 1 و b = 0. در نتيجه q_r = 0 و q_i = 0 و r = 1.
مرحله ی پنجم: a = 0 و b = 0. پايان!
اگر باقيمانده ها را پشت سر هم بگذاريم، نتيجه را که برابر 1100 می باشد را بدست می آوريم.

يادداشت: منبع مطالبی که خوانديد، کتاب Hacker’s Delight از انتشارات Addison Wesley می باشد. علت اينکه اين بخش از کتاب توجه مرا جلب کرد اين بود که اين مطلب مرتبط با سوال UVa #11180 می باشد که قبلا با همکاری هم تيمی های عزيز با استفاده از يک راه حل ديگر حل کرده بوديم، ولی روش ما به سادگی اين روش نبود. البته اين نشان گر اين است که اگر روابط مربوط به مساله را با دقت بررسی کنيم، معمولا به راحتی به راه حل های ساده تر و تميز تر می رسيم.
روشی که ما استفاده کرده بوديم، حاصل از بررسی توان های مختلف 1- + i و Pattern هايي بود که در آن وجود داشت.

Histograms - Part 2

nospam@example.com (Hadi Moshayedi) — Mon, 02 Apr 2007 04:45:13 -0400

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

در اين قسمت روش ديگری برای حل اين مساله ارائه می کنيم:

روش دوم (Iterative): ايده ی اين روش اين است که عريض ترين مستطيلی که هم ارتفاع با يکی از مستطيل ها باشد بازه ای شامل مستطيل هايي با ارتفاع های بزرگتر مساوی اين ارتفاع می باشد.

مستطيل ها را به ترتيب ارتفاع بررسی می کنيم. در هر مرحله يک سری بازه داريم (که در ابتدا خالی است) و در هر مرحله بازه ی مستطيلی که بررسی می شود را به اين بازه های اضافه می کنيم. (منظورم از بازه، بازه ای از محور x ها است که هر مستطيل اشغال می کند. مثلا برای سمت چپ ترين مستطيل، اين بازه [0,1]، برای بعدی [1,2] و … می باشد.)
پس از اضافه کردن بازه ی مستطيل جاری، ممکن است اين بازه از سمت چپ يا از سمت راست به يک بازه ای که قبلا اضافه شده بچسبد، يا اينکه دو بازه را به هم بچسباند، يا اينکه يک بازه ی جديد ايجاد کند. به هر حال بازه ای که پس از اضافه کردن بازه ی مستطيل جاری شامل بازه ی مستطيل جاری می باشد، عريض ترين بازه ای است که هم ارتفاع با اين مستطيل می تواند باشد.
(البته استثنا در مورد مستطيل های هم ارتفاعی که عريض ترين بازه يشان يکسان است وجود دارد، ولی چون بالاخره چنين بازه ای بعد از اضافه کردن آخرين مستطيل بوجود می آيد، خللی در درستی الگوريتم ما ايجاد نمی کند.)

اميدوارم توانسته باشم ايده ی اين روش را خوب توضيح بدهم.

برای نگهداری بازه ها، از دو آرايه با نام های Left و Right که طول آن ها N (که N تعداد مستطيل ها می باشد) استفاده می کنيم که مقدار اوليه ی عناصر آن ها 1- می باشد. برای يک بازه عضو متناظر با سمت راست ترين عضو آن بازه در آرايه ی Right انديس سمت چپ ترين عضو آن بازه را نگه داری می کند و عضو متناظر با سمت چپ ترين عضو آن بازه در آرايه ی Left انديس سمت راست ترين عضو آن بازه را نگه داری می کند. چون هميشه ما فقط با دو سر بازه کار داريم، مقاديری که در اعضای متناظر با ساير اعضای آرايه نگه داری می شود برای ما اهميتی ندارد.

در اين صورت، pseudo-code الگوريتم فوق به صورت زير خواهد بود:

Heights = [3, 6, 9, 7, 11, 8, 14, 4, 6, 3, 5]
Left = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
Right = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

function FindLargestRectangle():
Result = 0
SortedArray = [0, 1, … , N-1]
SortedArray.SortUsingHeights() # This can be done in O(N*log(N))
for i in 0 .. N-1:
   CurrentLeft = SortedArray[i]
   CurrentRight = SortedArray[i]
   if CurrentRight < N-1 and Right[CurrentRight + 1] != -1:
      # if there is another range in the right side of current range,
      # then extend current range
      CurrentRight = Right[CurrentRight + 1]
   if CurrentLeft > 0 and Left[CurrentLeft - 1] != -1:
      # if there is another range in the left side of current range,
      # then extend current range
      CurrentLeft = Left[CurrentLeft - 1]
   # Update Result
   Result = Max(Result, (CurrentRight - CurrentLeft + 1) * Heights[SortedArray[i]])
   # Update Range Arrays
   Right[CurrentLeft] = CurrentRight
   Left[CurrentRight] = CurrentLeft
end for
return Result
end function

print FindLargestRectangle()

پيچيدگی زمانی اين الگوريتم از مرتبه ی ((O(n*log(n می باشد.

منتظر قسمت های بعدی باشيد!

Petrozavodsk Wins Bronze Medals!

nospam@example.com (Hadi Moshayedi) — Wed, 28 Mar 2007 03:32:15 -0400

آخرین خبر از مسابقات ACM ICPC World Finals 2007: تيم دانشگاه Petrozavodsk که تنها تیمی بود که 6 سوال حل کرده بود و سیزدهم شده بود و مدال نگرفته بود، مدال برنز گرفت! برای دیدن نتیجه ی نهایی و رنگ مدال ها به رتبه بندی نهایی مسابقات مراجعه کنید.

برای دیدن توضیحات Bill Poucher به فروم Topcoder مراجعه کنید.

واقعا برای اعضای تیم Petrozavodsk خوشحالم!

Histograms - Part 1

nospam@example.com (Hadi Moshayedi) — Wed, 28 Mar 2007 02:06:21 -0400

به مساله ی زير توجه کنيد:
"يک سری مستطيل با عرض واحد و ارتفاع های مختلف داريم که کنار هم قرار گرفته اند. الگوريتمی پيشنهاد دهديد که مساحت بزرگترين مستطيلی که درون اين مستطيل ها جا می شود را پيدا کند."

(برای امتحان کردن روش های مختلف حل اين مساله، سعی کنيد مساله ی ZJU #1985 را حل کنید.)

مثلا در شکل زير، مستطيلی که مساحت آن جواب مساله است با رنگ سبز مشخص شده است.

ساده ترين راه حلی که به ذهن می رسد اين است که به ازای هر مستطيل فرض کنيم که مستطيل نتيجه هم ارتفاع با آن است و ببينيم با اين ارتفاع چقدر می توانيم به سمت راست و چپ برويم. ولی پيچيدگی زمانی اين راه حال در بدترين حالت (O(n^2 می باشد که چندان مطلوب نيست.

چيزی که اين مساله را برای من جالب کرده اين است که اين مساله چندين راه حل جالب و متنوع دارد و بسيار آموزنده و سرگرم کننده می باشد. در اين قسمت و قسمت های بعدی به بررسی برخی از اين الگوريتم ها که بلدم می پردازم.

روش اول (Divide and Conquer): دفعه ی اولی که اين مساله را سر امتحان ميان ترم درس طراحی الگوريتم ها ديدم، اين راه حل به ذهنم رسيد:

فرض کنيد می خواهيم جواب را برای مستطيل a-ام تا b-ام پيدا کنيم. اين مستطيل ها را از وسط به دو قسمت تقسيم می کنيم. جواب يا کاملا در قسمت سمت چپ است يا کاملا در قسمت سمت راست يا اينکه قسمتی از آن در سمت راست است و قسمتی از آن در سمت چپ. دو حالت اول را به صورت بازگشتی پيدا می کنيم و برای پيدا کردن بهترين جواب در حالت سوم، به روش زير عمل می کنيم:

در هر مرحله مستطيل را با ارتفاع جاری گسترش می دهيم. حالا، از سمت چپ و راست به دو مستطيل مختلف مماس می شود. ارتفاع جاری را به ماکزيمم ارتفاع اين دو مستطيل تغيير می دهيم و ادامه می دهيم. در هر مرحله مساحت مستطيل جاری را پيدا کرده و جواب را بروز می کنيم. اين کارها را تا زمانی انجام می دهيم که از سمت چپ به مستطيل a-ام و از سمت راست به مستطيل b-ام برسيم.

برای اينکه منظور من را دقيق تر بفهميد، به pseudo-code زير توجه کنيد:

Heights = [3, 6, 9, 7, 11, 8, 14, 4, 6, 3, 5]

function FindLargestRectangle(a, b):
if a == b:
   return Heights[a]
mid = (a+b) / 2
Result = max(FindLargestRectangle(a, mid), FindLargestRectangle(mid+1, b))
Left = mid
Right = mid+1
CurrentHeight = min(Heights[Left], Heights[Right])
while Left != a or Right != b do:
   if Left == a:
      # We cannot go to left anymore
      Right += 1
      CurrentHeight = min(CurrentHeight, Heights[Right])
   elif Right == b:
      # We cannot go to right anymore
      Left -= 1
      CurrentHeight = min(CurrentHeight, Heights[Left])
   elif Heights[Left-1] >= CurrentHeight:
      # We can go to Left with CurrentHeight
      Left -= 1
   elif Heights[Right+1] >= CurrentHeight:
      # We can go to right with CurrentHeight
      Right += 1
   else:
      # Choose the next CurrentHeight
      CurrentHeight = max(Heights[Left-1], Heights[Right+1])
   Result = max(Result, (Right - Left + 1) * CurrentHeight)
end
return Result

print FindLargestRectangle(0, len(Heights)-1)

رابطه ی بازگشتی زمان اين الگوريتم:

T(n) = 2*T(n/2) + O(n)

که اگر آن را حل کنيم، بدست می آوريم که پيچيدگی زمانی اين الگوريتم از مرتبه ی ((O(n*log(n می باشد.

در قسمت های بعدی راه های ديگری برای حل اين مساله را بررسی می کنم.

Barometer & the Skyscraper

nospam@example.com (Hadi Moshayedi) — Tue, 27 Mar 2007 07:04:00 -0400

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

يکی از دانشجويان چنين پاسخ داد: "انتهای فشارسنج را به ريسمانی بلند می بنديم. سپس فشارسنج را از بالا آسمان خراش طوری آويزان می کنيم که سرش به زمين بخورد. ارتفاع ساختمان مورد نظر برابر با طول طناب به اضافه ی طول فشارسنج خواهد بود."

پاسخ بالا چنان مسخره به نظر می آمد که مصحح بدون تامل دانشجو را مردود اعلام کرد. ولی دانشجو اصرار داشت که پاسخ او کاملا درست است و درخواست تجديد نظر در نمره ی خود کرد. يکی از اساتيد دانشگاه به عنوان قاضی تعيين شد و قرار شد که تصميم نهايي را او بگيرد.

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

دانشجو در پنج دقيقه ی اول ساکت نشسته بود و فکر می کرد. قاضی به او يادآوری کرد که زمان تعيين شده در حال اتمام است. دانشجو گفت که چندين روش به ذهنش رسيده است ولی نمی تواند تصميم گيری کند که کدام يک بهترين می باشد.

قاضی به او گفت که عجله کند، و دانشجو پاسخ داد: "روش اول اين است که فشارسنج را از بالای آسمان خراش رها کنيم و مدت زمانی که طول می کشد به زمين برسد را اندازه گيری کنيم. ارتفاع ساختمان را می توان با استفاده از اين مدت زمان و فرمولی که روی کاغذ نوشته ام محاسبه کرد."

دانشجو بلافاصله افزود: "ولی من اين روش را پيشنهاد نمی کنم، چون ممکن است فشارسنج خراب شود!"

"روش ديگر اين است که اگر خورشيد می تابد، طول فشارسنج را اندازه بگيريم، سپس طول سايه ی فشارسنج را اندازه بگيريم، و آنگاه طول سايه ی ساختمان را اندازه بگيريم. با استفاده از نتايج و يک نسبت هندسی ساده می توان ارتفاع ساختمان را اندازه گيری کرد. رابطه ی اين روش را نيز روی کاغذ نوشته ام."

"ولی اگر بخواهيم با روشی علمی تر ارتفاع ساختمان را اندازه بگيريم، می توانيم يک ريسمان کوتاه را به انتهای فشارسنج ببنديم و آن را مانند آونگ ابتدا در سطح زمين و سپس در پشت بام أسمان خراش به نوسان درآوريم. سپس ارتفاع ساختمان را با استفاده از تفاضل نيروی گرانش دو سطح بدست آوريم. من رابطه های مربوط به اين روش را که بسيار طولانی و پيچيده می باشند در اين کاغذ نوشته ام."

"آها! يک روش ديگر که چندان هم بد نيست: اگر آسمان خراش پله ی اضطراری داشته باشد، می توانيم با استفاده از فشارسنج سطح بيرونی آن را علامت گذاری کرده و بالا برويم و سپس با استفاده از تعداد نشان ها و طول فشارسنج ارتفاع ساختمان را بدست بياوريم."

"ولی اگر شما خيلی سرسختانه دوست داشته باشيد که از خواص مخصوص فشارسنج برای اندازه گيری ارتفاع استفاده کنيد، می توانيد فشار هوا در بالای ساختمان اندازه گيری کند، و سپس فشار هوا در سطح زمين را اندازه گيری کنيد، سپس با استفاده از تفاضل فشارهای حاصل ارتفاع ساختمان را بدست بياوريد."

"ولی بدون شک بهترين راه اين می باشد که در خانه ی سرايدار آسمان خراش را بزنيم و به او بگوييم که اگر دوست دارد صاحب اين فشارسنج خوشگل بشود، می تواند ارتفاع آسمان خراش را به ما بگويد تا فشارسنج را به او بدهيم!"

دانشجويي که داستان او را خوانديد، نيلس بوهر، تنها دانمارکی که موفق به دریافت جايزه ی نوبل شده است، بود.

منبع: http://www.mentors.ca/bohr.html

Random Thoughts

nospam@example.com (Hadi Moshayedi) — Tue, 27 Mar 2007 05:34:35 -0400

سلام دوستان!

سال 1385 با خوشی آغاز شد و با خوشی پایان یافت. امیدوارم اتفاقی مشابه در مورد سال 1386 بیافتد.

———————

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

1. از فضای وب هاستینگم چیز زیادی نمونده و جا برای نصب سیستم ویکی ندارم.

2. می خواهم هاستینگم را عوض کنم، چون این یکی انتظارات من را بر آورده نکرد!

ولی، در طی این مدت سعی می کنم چند مساله ی جالب را در وبلاگم توضیح بدهم، باشد که خشنود شوید! منتظر باشید!

———————

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

- اگر به نظرتان مطلبی را به اندازه ی کافی توضیح نداده ام و مبهم است یا توضیح بیشتری نیاز دارید، comment بگذارید و بگویید!

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

باشد که رستگار شوم!

Counting Connected Subgraphs - Part 3

nospam@example.com (Hadi Moshayedi) — Tue, 27 Mar 2007 05:20:25 -0400

برای مشاهده ی قسمت های پيشين این مطلب به لينکهای زير مراجعه کنيد:

قسمت اول

قسمت دوم

در اين قسمت، ابتدا روش بدست آوردن زيرمجموعه های يک مجموعه که در قسمت قبلی استفاده کرديم را توضيح می دهم و سپس به بررسی پيچيدگی الگوريتم ارائه شده می پردازم.

همان طور که گفتيم، هر مجموعه را با يک عدد 15 بيتی نمايش می دهيم که اگر بيت i-ام يک باشد يعنی چيز i-ام عضو مجموعه ی مورد نظر است، و گرنه نيست. حال می خواهيم روشی را ارائه کنيم که زير مجموعه بعدی يک مجموعه را که از لحاظ ارزش عددی کمتر از زير مجموعه ی جاری است را پيدا کند.
از اين به بعد فقط با نمايش دودوئی اعداد سر و کار داريم.
کم کردن يک از يک عدد را در نظر بگيريد. چه اتفاقی می افتد؟ سمت راست ترين 1 تبديل به صفر می شود و تمام صفر های سمت راست آن به 1 تبديل می شوند.
مثلا 100 تبديل به 11 می شود و 100110 تبديل به 100101 می شود.
حال هنگامی که می خواهيم زير مجموعه ی بعدی يک مجموعه (P) را پيدا کنيم، بايد اتفاقی مشابه بيافتد: سمت راست ترين 1 تبديل به صفر شود و تمام صفر های سمت راست آن که عضو مجموعه ی P هستند تبديل به يک شوند. اگر زير مجموعه ی جاری را منهای يک کنيم، سمت راست ترين 1 تبديل به صفر می شود و تمام صفر های سمت راست آن تبديل به يک می شوند. چون ما می خواهيم فقط بيت های عضو مجموعه ی P تبديل به يک شوند، حاصل تفريق را با مجموعه ی P "و" منطقی می کنيم. در نتيجه زير مجموعه ی از لحاظ عددی کوچکتر به دست می آيد.

حال به بررسی پيچيدگی زمانی الگوريتم می پردازيم.

پيچيدگی زمانی تابع CalculateEdges همان طور که آشکار است از مرتبه ی (O(n^2*2^n می باشد.برای بررسی تابع CountConnectedSubgraphs، جفت V و Y را در نظر بگيريد. پيچيدگی زمانی اين تابع متناظر با تعداد حالت های اين جفت می باشد. اگر بيت های متناظر V و Y را در نظر بگيريم، می فهميم که حالت هايی که ممکن است پيش بيايد عبارت است از: (1 و 0) – (1 و 1) – (0 و 0) . حالت (0 و 1) ممکن نيست، چون عضوی که عضو مجموعه ای نيست نمی تواند عضو زيرمجموعه ی آن بشود. پس، تعداد حالت ها 3 به توان n خواهد بود و پيچيدگی زمانی اين تابع از مرتبه ی (O(3^n.

Counting Connected Subgraphs - Part 2

nospam@example.com (Hadi Moshayedi) — Sun, 25 Mar 2007 05:36:46 -0400

سلام،
در قسمت قبل، به ايده ی اوليه ی مساله ی زير پرداختيم:
يک گراف ساده ی بدون جهت با حداکثر 15 راس داريم. الگوريتمی پيشنهاد دهيد که تعداد زيرگراف های همبند آن را پيدا کند.

در اين قسمت می خواهيم کمی به جزئيات پياده سازی راه حل ارائه شده برای اين مساله بپردازيم. فرض کنيد تعداد راس های گراف N باشد.

ابتدا يک pseudo-code برای اين راه حل ارائه می دهيم:

function CountConnectedSubgraphs(V, E):
Result = 2 ^ |E|
for each subset V' of V such that (V' contains V[0]) and (V' != V) do:
Result -= CountConnectedSubgraphs(V', E') * 2 ^ E(V-V')
return Result

برای اين مساله، فرض می کنيم که گراف را در يک ماتريس مجاورت ذخيره می کنيم:

int graph[15][15];

برای پياده سازی pseudo-code فوق، نياز داريم که:
1. ساختمان داده ای برای نمايش زير مجموعه ای از راس های گراف داشته باشيم. هر زير مجموعه را با استفاده از يک عدد 15 بيتی که يک يا صفر بودن بيت i-ام آن نشانگر اين است که آيا راس i-ام عضوی از زير مجموعه ی مورد نظر است يا نه.
2. تعداد يال های هر کدام از زيرگراف ها (که با يک زير مجموعه از راس ها مشخص می شوند) را داشته باشيم. اين کار را با يک حلقه ی 2 به توان N تايي انجام می دهيم. هر عضو از آرايه ی نتيجه نشانگر تعداد يال های زير گراف مربوطه می باشد:

int E[1<<15];

for(int i = 0; i < (1 << N); i++)
{
E[i] = 0;
for(int j = 0; j < N; j++)
   for(int k = 0; k < N; k++)
      // Check if j-th and k-th vertices are member of i
      if(((1 << j) & i) && ((1 << k) & i))
         // Check if there is an edge from j to k
         if(graph[j][k])
            E[i] += 1;
}

3. روشی نياز داريم که توسط آن بتوانيم زيرمجموعه های يک مجموعه را بدست بياوريم. در واقع، چون هر مجموعه را با يک عدد 15 بيتی نمايش می دهيم، می خواهيم اعدادی را به دست بياوريم که يک های آنها زير مجموعه ای از عدد متناظر با مجموعه ی مورد نظر باشند. فرض کنيد مجموعه ی مورد نظر را با X نمايش دهيم. می خواهيم اعداد Y ای را بدست بياوريم که X & Y برابر با Y باشد. (& = bitwise and). ساده ترين روش برای انجام دادن اين کار:

for(int i = 0; i < (1 << N); i++)
if((X & i) == i)
{
// do calculations here
}

ولی روش بهتری برای انجام دادن عمل بالا وجود دارد:

int Y = X;
do{
// do calculations here
…
// Move to next subset
Y = (Y - 1) & X;
}while(Y);

در قسمت بعدی به طرز کار اين روش و چند نکته ی جالب ديگر خواهم پرداخت.

4. اگر راه حل بالا را به صورت بازگشتی ساده بنويسيم، چون حالات تکراری زيادی بوجود می آيد، زمان اجرای برنامه خيلی زياد خواهد بود. برای جلوگيری از محاسبه ی دوباره ی حالات تکراری، از يک آرايه استفاده می کنيم که مقدار اوليه ی همه ی عناصر آن 1- می باشد و پس از محاسبه ی جواب برای هر زير گراف، نتيجه را در آن قرار می دهيم تا در دفعات بعدی از آن استفاده کنيم:

int arr[1<<15];

و در نهايت، از کنار هم قرار دادن قطعات بالا، سورس کد زير به دست می آيد:

int graph[1 << 15];
int arr[1 << 15];
int N;

void CalculateEdges()
{
for(int i = 0; i < (1 << N); i++)
{
   E[i] = 0;
   for(int j = 0; j < N; j++)
      for(int k = 0; k < N; k++)
         // Check if j-th and k-th vertices are member of i
         if(((1 << j) & i) && ((1 << k) & i))
            // Check if there is an edge from j to k
            if(graph[j][k])
               E[i] += 1;
}
}

int CountConnectedSubgraphs(int V)
{
if(arr[V] != -1)
   return arr[V];
int FirstBit = 1;
while((FirstBit & V) == 0)
   FirstBit *= 2;
int Result = (1 << E[V]);
int Y = V;
do
{
   if((Y & FirstBit) && Y != V)
   {
      int X = ~Y & V; // X = V - Y
      Result -= CountConnectedSubgraphs(Y) * (1 << E[X]);
   }
   Y = (Y - 1) & V;
}while(Y);

return arr[V] = Result;
}

int main()
{
// Read N and Graph here
…
memset(arr, -1, sizeof arr);
CalculateEdges();
cout << CountConnectedSubgraphs((1 << N) - 1) << endl;
return 0;
}

ِDilemma!

nospam@example.com (Hadi Moshayedi) — Sun, 18 Mar 2007 00:44:13 -0400

آینده نگر باشیم. [+]

At Tokyo for ICPC Finals - Part 6

nospam@example.com (Hadi Moshayedi) — Sat, 17 Mar 2007 04:24:00 -0400

مراسم Celebration:

مراسم طبل زنی ژاپنی جالب بود:

یکی بود که خفن جیب و ساعت و … می زد. حتی پیراهن یکی را به صورت خفن و یکباره ای در آورد. خیلی خفن بود:

بچه های تیم Shanghai JiaoTong با حال بودند:

At Tokyo for ICPC Finals - Part 5

nospam@example.com (Hadi Moshayedi) — Sat, 17 Mar 2007 04:23:00 -0400

دیروز رفتیم Tokyo Disney Land:

چند تا از شخصیت های کارتونی را دیدیم:

بچه های ژاپنی بامزه اند:

At Tokyo for ICPC Finals - Part 4

nospam@example.com (Hadi Moshayedi) — Sat, 17 Mar 2007 04:21:00 -0400

بدعمل کردیم زیرا: اگر سر سوال G بد عمل نمی کردیم و یک ساعته تمامش میکردیم، می توانستیم حداقل یکی از دو سوال F که سوال متوسط به پائینی بود وسوال D که نیاز به دانستن قضیه ی Pick داشت و ما دانش کافی برای حل آن را داشتیم را حل کنیم و وضع مان از این خیلی بهتر باشد.

می توان راضی بود زیرا: در 20 دقیقه ی آخر دو سوال گرفتیم و از وضعیت افتضاح به وضعیت متوسط رسیدیم. و چون یک سال دیگر وقت داریم.

در قدم اول برای سال بعد، فعلا تصمیم دارمدر تعطیلات سال نو topcode rating ام را (در سه مسابقه) به بالای 2200(فعلا 2040 هستم) برسانم.

At Tokyo for ICPC Finals - Part 3

nospam@example.com (Hadi Moshayedi) — Fri, 16 Mar 2007 04:16:00 -0400

و بالاخره روز مسابقه:

قبل از مسابقه همه خندان بودیم. (من عینکیه هستم):

صبح زود بیدار شدیم، صبحانه خوردیم، و آمادهشدیم که به محل مسابقه وارد شویم. رضا badge اش را درست نبسته بود، برایهمین Bill Poucher مجبورش کرد چند حرکت شنا انجام بدهد و کلی خندیدیم.

و بالاخره مسابقه آغاز شد:

دقیقه ی 1:حسین سوال A، من سوال B، و رضا سوال C را خواند. سوال A آسان بود، ولی منهنوز سوال B را درست نفهمیده بودم. حسین سوال A را به ما توضیح داد وتصمیم گرفتیم که به عنوان اولین سوال، سوال A را بنویسیم.

دقیقه ی 20: تیم های زیادی سوال B را گرفته اند، رضا سوال B را دوباره خوانده و برای من توضیح داده. هنوز هیچ ایده ای نداریم.

دقیقه ی 50:حسین کد سوال A را تمام کرد و پس از کمی تست Submit می کنیم. هنوز هیچایده ای برای سوال B نداریم. سوال B را برای حسین نیز توضیح می دهیم.

دقیقه ی 51: جواب Submit مون Wrong Answer شد. کمی کد را می خوانیم و به مشکل پی می بریم.

دقیقه ی 67: سوال A را دوباره Submit می کنیم. این دفعه جواب Submit مون Yes شد.

دقیقه ی 70: هر سه روی B فکر می کنیم. ایده های زیادی مطرح می شود ولی چون مطمئن نیستیم بیشتر فکر می کنیم.

دقیقه ی 90: بالاخره بر سر ایده ی سوال B توافق می کنیم. شروع می کنم به نوشتن کدش.

دقیقه ی 100:سوال B را Submit می کنیم و جوابش Yes می شود. حسین سوال G را می خواند وتوضیح می دهد. به نظر آسان می آید. بر سر پیاده سازی اش توافق می کنیم وشروع می کنم به پیاده سازی جواب.

دقیقه ی 130: اولین Wrong Answer برای سوال G را می گیریم. کد را می خوانیم و دو باگ در می آوریم، درستش می کنیم و دوباره Submit می کنیم.

دقیقه ی 145: دومینWrong Answer را می گیریم. کد را n بار می خوانیم. هیچ مشکلی پیدا نمیکنیم … صورت سوال را چند بار می خوانیم … یک قسمتش برای مان مبهماست. با یک فرض دیگر یک کد دیگر می نویسیم و Submit می کنیم.

دقیقه ی 160:سومین Wrong Answer را می گیریم. رضا صورت سوال را دوباره می خواند و سریک جمله گیر می دهد. بالاخره نظر رضا را قبول می کنیم و آن برداشت یک کددیگر می زنیم.

دقیقه ی 200: این دفعه Runtime Error می گیریم. نمی دانیم چه کار کنیم.

دقیقه ی 243: من شروع می کنم به زدن کد سوال C. بابک به ساز بسیار نگران به ما نگاه می کند.

دقیقه ی 260: حسین صورت سوال را دوباره می خواند، یک نکته ی دیگر پیدا می کند … شروع می کند و درست کردن کد.

دقیقه ی 280: بالاخره سوال G را Submit می کنیم و Yes می گیریم. من بقیه ی کد C را می زنم.

دقیقه ی 290: سوال C را Submit می کنیم و Wrong Answer می گیریم. رضا یک حالت خاص را توضیح می دهد و من شروع می کنم به درست کردن کد.

دقیقه ی 296: سوال C را Submit می کنیم و Yes می گیریم. بابک به ساز از حالت نگرانی شدید به وضع عادی بر می گردد. 4 دقیقه ی آخر را حرف می زنیم.

دقیقه ی 300: مسابقه تمام شد.

و بالاخره در Awards Ceremony معلوم می شود که تیم دانشگاه Warsaw قهرمان امسال شده.

At Tokyo for ICPC Finals - Part 2

nospam@example.com (Hadi Moshayedi) — Wed, 14 Mar 2007 04:15:00 -0400

روز Practice Contest:

و Team Photo:

At Tokyo for ICPC Finals - Part 1

nospam@example.com (Hadi Moshayedi) — Tue, 13 Mar 2007 04:11:00 -0400

سلام دوستان،

توکیو خوش می گذره. جاتون خالی.

امروز تو خیابان های دیزنی سی توکیو گوفی را دیدیم.

با بچه ها دو سه تا عکس گرفتیم.

دیزنی سی قشنگ بود. حال کردم.

یکی از هیجان انگیزترین مراسم عمرم را دیدم.

توکیو مسجد هم داشت، ولی مال افسانه های سندباد بود.

بازی Dance Dance Revolution خیلی هیجان انگیز بود.

Counting Connected Subgraphs - Part 1

nospam@example.com (Hadi Moshayedi) — Wed, 07 Mar 2007 11:21:58 -0500

سلام،به این مساله توجه کنید: یک گراف ساده ی بدون جهت با حداکثر 15 راس داریم. الگوریتمی پیشنهاد بدهید که تعداد زیر گراف های همبند آن را پیدا کند. بیشتر افراد، از جمله من، وقتی عدد 15 را می بینند، سعی می کنند مساله را با استفاده از برنامه سازی پویا (Dynamic Programming) مدل سازی کنند [...]

سلام،

به این مساله توجه کنید: یک گراف ساده ی بدون جهت با حداکثر 15 راس داریم. الگوریتمی پیشنهاد بدهید که تعداد زیر گراف های همبند آن را پیدا کند.

بیشتر افراد، از جمله من، وقتی عدد 15 را می بینند، سعی می کنند مساله را با استفاده از برنامه سازی پویا (Dynamic Programming) مدل سازی کنند و رابطه ای بازگشتی برای پیدا کردن جواب مساله برای مجموعه راس های S را مستقیما با استفاده از حل زیر مساله های کوچکتر برای زیر مجموعه های مجموعه ی S پیدا کنند. که احتمالا به جواب هم نمی رسند.

ولی یک حل کننده ی مساله ی خوب زیاد به یک راه حل گیر نمی دهد و سعی می کند راه های دیگری را نیز امتحان کند.

یکی از کارهای خوبی که می توان هنگام حل کردن مساله انجام داد این است که تعیین کرد که با داشتن چه چیز هایی می توانیم جواب مساله را پیدا کنیم. مثلا در این مساله می توان از رابطه ی تعداد زیر گراف های همبند + تعداد زیر گراف های ناهمبند = تعداد کل زیرگراف ها استفاده کرد و برای پیدا کردن جواب مساله به دنبال پیدا کردن تعداد کل زیرگراف ها و تعداد زیرگراف های ناهمبند بود:

1. تعداد کل زیر گراف ها 2 به توان |E| می باشد که در آن |E| تعداد یال ها ی گراف می باشد. این قسمت از مساله که یک مساله شمارش ساده بود.

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

پس برای پیدا کردن تعداد زیرگراف های ناهمبند یک مجموعه راس S کافی است تمام زیر مجموعه های 'S ای از این مجموعه را که S مخالف 'S باشد و 'S شامل اولین راس S باشد را در نظر بگیریم و تعداد زیر مجموعه های همبند گراف 'S ضرب در 2 به توان تعداد یال های گراف با مجموعه راس 'S-S را به جوابمان اضافه کنیم. پس این قسمت را نیز می توان با استفاده از رابطه ای بازگشتی و برنامه سازی پویا حل کرد.

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

Undo Closed Tab in Firefox 2.0

nospam@example.com (Hadi Moshayedi) — Tue, 13 Feb 2007 11:37:49 -0500

با استفاده از Ctrl+Shift+T

Dijkstra with STL priority_queue

nospam@example.com (Hadi Moshayedi) — Sun, 11 Feb 2007 04:00:12 -0500

Some days ago, I was trying to solve a problem, I used so called technique "Priority First Search" (PFS). With not much thought, I realized that "PFS with marking visited states" isSomehowEqualTo "Dijkstra's Shortest Path Algorithm".

I used to implement Dijkstra using STL set, but I realized that I can use priority_queue instead, and with some analysis, I realized that the time complexity remains O(e*log(v)) (Where "v" is number of vertices and "e" is number of edges of graph). The pseduocode for this would be something like this:

int Distance[N] = {inf} * N;
bool Visited[N] = {false} * N;
priority_queue<pair> Q;
Distance[source] = 0;
Q.push([0, source]);

while(!Q.empty()):
   P = Q.top();
   Q.pop();
   u = P[1];
if(u == target)
   return -P[0];
   if(Visited[u] == true)
      continue;
   Visited[u] = true;
   for (u,v,weight) in edges:
      if(Distance[u] + weight < Distance[v]):
         Q.push([-(Distance[u] + weight), v]);
         Distance[v] = Distance[u] + weight;

The time complexity analysis: We will have at most "e" pushes (Since every vertex is visited at most once) in the Q, then we will have at most "e" pushes in the Q. this will lead to O(e * log(e)) time complexity which is equal to O(e * log(v)) (Since e <= v^2 and log(v^2) = 2*log(v)).

Of course some improvements can be made.

With some experiments, I realized that this method is faster than implementing Dijkstra's algorithm using STL set in most cases.

To practice this method, try to solve UVA #10986 .

I Fear

nospam@example.com (Hadi Moshayedi) — Sun, 11 Feb 2007 02:50:00 -0500

از دفترچه خاطرات سريوژا در 20 دسامبر 2006:

« می ترسم … می ترسم به او نزديک تر شوم …می ترسم تلاش کنم او را بیشتر بشناسم … می ترسم از آنکه تقدسش را در ذهنمن از دست بدهد … می ترسم همه ی احساس های شیرین یاد او را از دست بدهم …می ترسم … »

Beauty of Numbers

nospam@example.com (Hadi Moshayedi) — Mon, 22 Jan 2007 02:42:00 -0500

«چرا اعداد زيباهستند؟ به آن می ماند که بپرسيد چرا سمفونی نهم بتهون زيباست … اگر نمیتوانيد زيبايی اعداد را ببنيد، کسی نمی تواند علت زيبايی آن ها را به شمابگويد … من می دانم که اعداد زيبا هستند. اگر آن ها زيبا نيستند، پس هيچچيز زيبا نيست …»

پال اردوس

Holidays

nospam@example.com (Hadi Moshayedi) — Fri, 12 Jan 2007 02:41:00 -0500

فرداامتحانات پایان ترم شروع می شود، و من می توانم کمی استراحت کنم، کتاب(غیر درسی) بخوانم، چند تا فیلم ببینم، با هم اتاقی ها بیشتر صحبت کنم، …

—————————

انسان موجودی است پر از رازهایپیچیده، و غیر قابل شناسایی … نمی دانم چطور می شود در باره ی این موجودبا اطمینان حرف زد و درباره ی او تنها با یک نگاه و چند شنیده قضاوت کرد.

—————————

از دفترچه خاطرات سريوژا در روز 6 ژانويه 2007:

" … نیکالای بهترین دوست من بود، همیشه بامن خوب بود، دوستش می داشتم. مدتی رفتارش با من بد شد، حرف هایش دل من رامی آزرد. گمان کردم که ديگر همه چیز تمام شده است، … گذشته را فراموش کردهبودم، فراموش کرده بودم که چند سال بهترین مونس تنهایی های من بود، … کمیفکر کردم، گذشته را به ياد آوردم، و حدث زدم که احتمالا مشکلی براینیکالای پیش آمده است. به او محبت کردم، از مشکلاتش پرسیدم، او لبخند زد،و من شاد شدم. دوستت دارم نیکالای."

—————————

فردا امتحانات شروع می شود، و احتمالا برای مدتی چیزی در این وبلاگ ننویسم.

—————————

احتمالا در تعطیلات اول سال بعد یک ویکی الگوریتمی درست کنم، چنان ویکی ای که تا به حال نظیرش را ندیده باشید! منتظر باشید!

—————————

Logic will get you from A to B. Imagination will take you everywhere!"Albert Einstein"

Life

nospam@example.com (Hadi Moshayedi) — Tue, 09 Jan 2007 06:21:00 -0500

ترنس تائو تنها 13 سال داشت که برنده ی مدال طلا در المپياد رياضی جهانی شد. او درجه ی PHD خود را در 1996 از پرينستون گرفته و هم اکنون استاد تمام دانشگاه کاليفرنيا در لس آنجلس است ... کارهای او در موضوعاتی نظير آناليز هارمونيک، معادلات ديفرانسيل با مشتق های جزئی غير خطی، اثر داشته و مدال فيلدز را برای خدماتش در اين زمينه ها دريافت کرده.

... و اما هادی ... مهم ترين کاری که در دوران قبل از دانشگاه خود کرد اين بود که در امتحان سمپاد قبول شد و ديگر هيچ ... او مدال المپياد ندارد، هيچ اختراعی نکرده، هيچ وقت (حتی در ابتدايي) معدلش خوب نبوده، کتاب زياد دارد ولی اکثر آن ها را نخونده، از اونهايي هم که خونده هيچی يادش نيست، و همين.
اما ...
اما همچنان کسانی هستند که هادی برای آن ها بسيار مهم تر، با ارزش تر، و دوست داشتنی تر از ترنس تائو می باشد. برای آن ها هيچ مهم نيست که هادی برنده ی مدال های کشوری و جهانی نيست، معدلش خوب نيست، يا اينکه يک مساله "بيشترين جريان" ساده را نمی تواند درک کند. برای آن ها مهم نيست که هادی در يک مسابقه ی برنامه نويسی 138 ام می شود و اول نمی شود، ...
هادی زندگی می کند؛ همواره می داند که هميشه کسانی هستند که دوستش دارند و به او اميد دارند. او می تواند به خيلی ها کمک کند، و آن ها را به زندگی بهتری اميدوار کند؛ آن ها به هادی محبت کنند، دل او را تسخير کنند، و او را به زندگی اميدوارتر کنند. هادی عاشق آن ها شود، بی منت به آن ها کمک کند، به حرف های آن ها گوش بدهد، به خاطر آن ها غمگين شود، اشک بريزد؛ به خاطر آن ها خوشحال باشد، به آن ها شادی هديه کند ...

همين. با تمام غم های ممکن، زندگی زيباست!

Hinfunchip

nospam@example.com (Hadi Moshayedi) — Sun, 07 Jan 2007 02:40:00 -0500

زندگی سخت شده است …

—————–

هر روز حدودا 15 دقیقه به آزادی مطلق می رسم، و احساس خوشبختی می کنم …

—————–

آهنگ غم ناک می گذارم، سعی می کنم غمگین باشم، ولی همچنان می خندم.

—————–

من: زندگی سخت است، مشکلات زياد است …

نیکالای: چه مشکلی؟

من: (سکوت)

چشمانم را کمی بازتر می کنم، در زندگی دیگران دقیق می شوم، و به این نتیجه می رسم که من مشکلی ندارم!