حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

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

ادامه مطلب

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

ادامه مطلب

مقدمه

برخی مسائل در کامپیوتر هستند که تاکنون الگوریتم دقیق چندجمله‌ای برای حل آنان معرفی نشده است. برخلاف مسائلی که راه حل چندجمله‌ای دارند و همگی در کلاس P یا Polynomial قرار می‌گیرند، این مسائل در کلاس NP یا Nondeterministic Polynomial time قرار می‌گیرند. بحث پیرامون این مسائل زیاد هست شاید بپرسید اصلا چه اهمیتی دارند؟ خیلی از مسائل مهم مثل پیشبینی ساختار پروتئین الگوریتم از جنس NP هستند[منبع]. مساله پیشبینی ساختار پروتئین الگوریتم در ساخت دارو و بیوانفورماتیک اهمیت فراوانی دارد. برای دیدن مثال‌ها و توضیحات بیشتر می‌تونید این ویدیو از Youtube رو ببینید. اثباتهای زیادی در زمینه اینکه کلاس P همان کلاس NP هست و نیست از طرف محققین برجسته دنیا انجام شده. تا زمان نوشتن این مطلب ۱۱۶ عدد اثبات در زمینه برابر بودن یا نبودن در این صفحه ثبت شده که قابل توجه است.

در کلاس NP، یک زیرمجموعه به نام NP-Complete که به آن NPC نیز می‌گویند وجود دارد و وقتی می‌گوییم یک مساله مطعلق به کلاس NPC است یعنی تمامی مسائل NP به آن قابل کاهش هستند. یا به عبارت دیگر بین مسائل NP سخت‌ترین مسائل هستند. بقول مولوی که می‌گوید «چونک صد آمد نود هم پیش ماست» این مسائل اگر حل شوند بقیه مسائل هم با توجه به اینکه به این مسائل قابل تبدیل هستند و ساده‌تر هستند، توسط حل شدن اینها حل می‌شوند. دقت کنید که این یک رابطه یک طرفه است.

برای اثبات NPC بودن یک مساله باید دو مرحله را اثبات کنیم. ابتدا اینکه با داشتن جواب می‌توان در زمان چند جمله‌ای درست بودن جواب را بررسی کرد و همچنین باید ثابت کنیم که این مساله حداقل به اندازه یک مساله NPC دیگر سخت است. در نتیجه می‌توان آن مساله NPC دیگر را به مساله مورد نظر ما کاهش داد یا reduce کزد. شاید بپرسید پس اولین مساله NPC چطور ثابت شده است که NPC هست، وقتی که هیچ مساله NPC دیگری وجود ندارد؟ اثبات اولین مساله NPC که Circuit satisfiability problem است به شکلی دیگری انجام می‌شود که توصیه می‌کنم اثباتش رو حتما چک کنید به نوعی اثبات ترکیبی از سخت‌افزار و نرم‌افزار را باهم دارد. بعد از این اثبات می‌کنند مساله 3SAT نیز به اندازه این مساله سخت است و در ادامه بقیه الگوریتم‌ها از طریق یکدیگر و یا از طریق 3SAT اثبات می‌شوند.

مساله رنگ آمیزی

کمترین تعداد رنگی که با آن بتوان تمامی راس‌های گراف را رنگ‌آمیزی کرد، طوری که دو راس مجاور همرنگ نباشند چیست؟ مساله رنگ آمیزی در واقع همین سوال است. این مساله به ازای دو رنگ در زمان چند جمله‌ای قابل حل کردن می‌باشد. در ادامه ثابت می‌کنیم به ازای سه رنگ و بالاتر از آن NPC می‌باشد. این مساله یک نوع مساله بهینه‌سازی یا optimization problem است اما برای اثبات نیاز داریم به نوعی این مساله را به یک مساله تصمیم‌گیری یا decision problem تبدیل کنیم که جواب بله یا خیر داشته باشد. نسخه تصمیم‌گیری مساله رنگ آمیزی به این صورت است: با داشتن یک گراف و یک K آیا می‌توان این گراق را با K رنگ رنگ آمیزی کرد؟ در ادامه ما ابتدا به ازای K=3 این مساله را اثبات می‌کنیم و سپس به ازای Kهای بالاتر اثبات می‌کنیم.

ادامه مطلب

مقدمه
سوال «چگونه کار کنیم تا در مسابقات برنامه نویسی موفق شویم؟» به تعداد افراد شرکت کننده در این مسابقات جواب مختلف دارد ولی تعدادی ضدالگو وجود دارد که همه با مشکل ساز بودن این ضدالگو ها موافق هستند. یک مثال ساده این است که مثلا تشخیص روشهای افزایش ده سال طول عمر، سخت تر از تشخیص روشهای کاهش ده سال طول عمر هست و اگر شما از این ضد الگوها یا کارهای اشتباه دوری کنید میتوان امیدوار بود که در کل نتیجه بهتری بگیرید. بد نیست از کتاب «چگونه در C++ برنامه ننویسیم؟» نام ببرم که در انتخاب عنوان از این کتاب الگو گرفتم.
ادامه مطلب

مقدمه
یکی از الگوریتم های ساده که معمولا در درس ساختمان گسسته، طراحی الگوریتم و ساختمان داده به صورت پایه مطرح می شود الگوریتم فلوید وارشال می باشد. این الگوریتم با مرتبه O(N³) شاید یکی از بدترین انتخاب ها برای حل مسئله به علت کندی بیش از حد باشد. اما وقتی تعداد نود به اندازه کوچکتر از 200 باشد تفاوت قابل توجه ای با الگوریتم های خوب جایگزین ندارد و به علت پیاده سازی ساده و سریع این الگوریتم همیشه اگر در محدودیت های مساله قابل استفاده باشد جایگزین بقیه کاندید ها می شود.
رابرت فلوید و استفان وارشال همزمان باهم در مقالات مختلف در سال 1962 این الگوریتم را منتشر کردند، و به افتخارشان الگوریتم فلوید-وارشال نام گرفت که به اختصار به آن فلوید نیز گفته می شود، رابرت فلوید دارای یک الگوریتم خوب دیگر برای پیدا کردن دور در لیست پیوندی یا روابط بازگشتی بر اساس مقدار قبلی می باشد که باز با اسم الگوریتم فلوید مشهور است اما به اندازه این الگوریتم اعمال تعدی معروف نیست.
دلیل من برای انتخاب این الگوریتم برای بخش درسنامه الگوریتم ها، روزمره و ساده بودن الگوریتم فلوید بود که با توجه به بازدید های وبلاگ بنظر می رسد دانشجو های زیادی در طول ترم نیاز به مطالعه و استفاده از این الگوریتم دارند.

ادامه مطلب

مقدمه مترجم

الگوریتم Maximoum Flow Minimoum Cut یکی از الگوریتم های کاربردی است که معمولا در چالش های متوسط و سطح بالا برنامه نویسی ظاهر میشود از کاربرد های این الگوریتم میتوان به برنامه ریزی خطوط هوایی برای عدم تداخل اشاره کرد و همچنین مسائلی که میتوان با چند مدل سازی از ورودی مسئله را با یک مسئله بیشینه جریان تبدیل کرد در سوالات  مسابقات داخلی از جمله مسابقات منطقه ای غرب‌ آسیا (‌صنعتی شریف)‌ و مسابقه داخلی دانشگاه امیرکبیر دیده شده است. این مقاله از بخش الگوریتم های TopCoder ترجمه شده  و اولین مقاله غیر تالیفی منتشر شده در این وبلاگ محسوب میشود. قسمت پیشرفته تر این الگوریتم نیز در اسرع وقت ترجمه شده و منتشر میشود.  لینک مقاله انگلیسی

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

مسئله استاندارد بیشینه جریان Maximum Flow Problem
وقتی به یک مسئله بیشینه جریان بر میخوریم ساده ترین حالت صورت مسئله میتواند به این شکل باشد: " با داشتن لیستی از لوله ها با شدت جریان متفاوت که از انتها به هم وصل شده اند. مقدار بیشینه ای از آب که میتوان از یک نقطه شروع به یک نقطه پایان منتقل کرد چقدر است؟" یا به صورت "شرکتی دارای خط تولیدی در شهر X میباشد که نیاز است محصولاتش به شهر Y منتقل شود. به شما راه های یک طرفه ای داده شده است که هر یک دو شهر از کشور را با یک بیشینه تعداد کامیون عبوری به هم متصل میکند. بیشترین تعداد کامیونی که شرکت میتواند از آنها برای انتقال محصولات استفاده کند چقدر است؟"

ادامه مطلب

مقدمه
پیش از این برنامه نویسی پویا را مطرح کرده بودیم، امروز یک سبک از برنامه نویسی پویا به اسم Bitmask را به همراه حل مسئله شماره 10911 از UVA مطرح میکنیم، که به نسبت مسئله ساده ای هست. وقتی که بحث پیاده سازی مجموعه ها در میان باشد Bit Mask ها مطرح میشوند.

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

مقدمه

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

یک راه حل خیلی بهتر و کم دردسر تری نیز مثل استفاده از کلاس های Generic کتابخانه استاندارد C++ مثل std::map و std::unordered_map و یا در جاوا مثل java.util.HashMap  و java.util.TreeMap میباشند که بسیار پر کاربرد هم هستند.

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

ادامه مطلب

مقدمه
قبل از این داده ساختار Segment Tree را به صورت تئوری مورد بحث قرار دادیم ، امروز مسئله UVA 12086 - Potentiometers یا مقاومت متغییر که با استفاده از این ساختمان داده قابل حل میباشد را پیاده سازی میکنیم.

متن مسئله
PDF مسئله از اینجا قابل دریافت است ، خلاصه متن این است که N مقاومت متغییر روی یک خط قرار گرفتند ، و مقدار اولیه هریک را داریم ، باید به تعداد M دستور پاسخ بدهیم دو نوع دستور داریم
نوع اول : مقدار مقاومت x را به r تغییر بده
نوع دوم : مقاومت معادل r تا l را چاپ کن ، که معادل با جمع تک تک مقاومت های این بازه میباشد.

راه حل
ابتدا راه حل ساده یعنی پیاده سازی همین کار با دو حلقه تو در تو به نظر درست می آید اما مرتبه این الگوریتم O(NM) میباشد که با توجه اینکه N میتواند تا 200000 باشد ، و M نیز میتواند تا 200000 باشد بطور تقریبی میتوان حدس زد که این الگوریتم نیاز به زمان اجرای 400 ثانیه ای تنها برای یک تست دارد و نتیجه این ارسال بدون شک Time Limit Executed میباشد ، برنامه میبایست زیر 3 ثانیه تمامی دستورات تمام تست ها را پاسخ گو باشد. 

ادامه مطلب

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

Segment Tree چیست؟
به بیان ساده میتوان گفت Segment Tree خلاصه کردن دو دویی یک بازه میباشد.
فرض کنید یک آرایه از 10000 ساختمان به ترتیب نامشخص که در یک ردیف قرار گرفته اند را داریم. میخواهیم در یک بازه از a تا b بلند ترین ساختمان را پیدا کنیم، ما از قبل میدانیم که بلند ترین ساختمان در 5000 ساختمان اول کدام است.  به عبارت دیگر بیشینه  بازه 1 تا 5000 را داریم ، چه استفاده ای میتوانیم از بیشینه این بازه کنیم؟ جواب ساده است اگر 1 تا 5000 زیر بازه بازه انتخابی بود میتوانیم از جستجو در این بخش صرف نظر کنیم و از مقدار ذخیره شده استفاده کنیم.
برای مثال بازه 1 تا 7000 را در نظر بگیرید. کافیست بیشینه ذخیره شده را با بیشینه بازه 5001 تا 7000 مقایسه کنیم. در این مثال نسبت به الگوریتم اولیه ( جستجو از a تا b برای پیدا کردن بیشینه ) 5000 مقایسه را صرف نظر کرده ایم زیرا بلند ترین ساختمان 5000 خانه اول را میدانیم و کافیست این مقدار را با 2000 ساختمان بعدی مقایسه کنیم.
این یک مثال ساده بود در عمل در Segment Tree بازه های خیلی بیشتری با یک نظم دو دویی ذخیره میشود و در بدترین حالت ممکن تعداد مقایسه ها به Log(N) میرسد که بسیار در مقایسه با N قابل توجه میباشد.
در مثال بالا الگوریتم اولیه در بدترین حالت مقدار 10000 مقایسه را انجام می دهد اما استفاده از Segment Tree این مقدار را در بدترین حالت به 14 مقایسه کاهش میدهد.

ادامه مطلب