حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

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

آخرین نظرات
  • ۱۸ آبان ۹۵، ۱۲:۵۱ - سامان
    ای ول
مقدمه
سوال «چگونه کار کنیم تا در مسابقات برنامه نویسی موفق شویم؟» به تعداد افراد شرکت کننده در این مسابقات جواب مختلف دارد ولی تعدادی ضدالگو وجود دارد که همه با مشکل ساز بودن این ضدالگو ها موافق هستند. یک مثال ساده این است که مثلا تشخیص روشهای افزایش ده سال طول عمر، سخت تر از تشخیص روشهای کاهش ده سال طول عمر هست و اگر شما از این ضد الگوها یا کارهای اشتباه دوری کنید میتوان امیدوار بود که در کل نتیجه بهتری بگیرید. بد نیست از کتاب «چگونه در C++ برنامه ننویسیم؟» نام ببرم که در انتخاب عنوان از این کتاب الگو گرفتم.
  • حسام حداد

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

  • حسام حداد

مقدمه مترجم

مطالب زیر از نسخه اصلی کتاب Refactoring: Improving the Design of Existing Code  نوشته Martin Fowler دستچین شده و با ترجمه همراه با تالیف برای درک بهتر مطلب آمده است. Code Refactoring به شما یک سری عادت مفید در برنامه نویسی می آموزد که بسیار میتواند باعث کیفیت بخشیدن به نرم افزارتان شود. مطالب در این رابطه به مرور روی وبلاگ قرار می گیرند و به امید خدا این مطالب را در ویکی پدیا فارسی هم در بخش Code Refactoring اضافه خواهم کرد.

Refactoring یا بازآرایی چیست؟

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

  • حسام حداد

مقدمه مترجم

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


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


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

  • حسام حداد

مقدمه

چند مدت پیش تصمیم گرفتم که جدا از معرفی و آموزش مربوط به برنامه نویسی رقابتی مطالب دیگری در رابطه با برنامه نویسی یا کارهای سیستمی در وبلاگ منتشر کنم و بعد از مشورت با دوستان در این کار مصمم تر شدم. این مقاله مربوط به مهندسی معکوس کردن APK یا خروجی نهایی برنامه آندروید به Source Code جاوا هست.
البته این روش روی استفاده از NDK برای ساخت APK که اغلب توسط Engine های بازی سازی استفاده می شود جوابگو نیست. برای مهندسی معکوس دو مرحله استخراج فایل Jar و مهندسی معکوس فایل Jar رو باید پشت سر بگذاریم.

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

مهندسی معکوس چیست؟

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

  • حسام حداد
مقدمه
پیش از این برنامه نویسی پویا را مطرح کرده بودیم، امروز یک سبک از برنامه نویسی پویا به اسم 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 مقایسه کاهش میدهد.

  • حسام حداد