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

مقدمه

چند مدت پیش تصمیم گرفتم که جدا از معرفی و آموزش مربوط به برنامه نویسی رقابتی مطالب دیگری در رابطه با برنامه نویسی یا کارهای سیستمی در وبلاگ منتشر کنم و بعد از مشورت با دوستان در این کار مصمم تر شدم. این مقاله مربوط به مهندسی معکوس کردن 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 مقایسه کاهش میدهد.

ادامه مطلب

مقدمه
 بعد از اینکه Dynamic Programming را به صورت کلی مورد بازبینی قرار دادیم. طبق قراری که گذاشته شد در این مطلب و مطالب بعدی به توضیح بیشتر در این زمینه میپردازیم.
بد نیست بدانید که برنامه نویسی پویا دارای یک سری مسئله کلیشه مانند:

• کولپشتی صفر و یک 01 Knapsack
• کوله پشتی Knapsack
• طولانی ترین زیر آرایه همسان Longest Common Sequence
• طولانی ترین زیر آرایه صعودی Longest Increasing Sequence

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

ادامه مطلب

در مطالب گذشته سوال کارت های برابر را حل کردیم حل اول کارت های برابر

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

دوم اینکه دارای پیچیدگی زمانی O(N²M⁴) بود که با توجه به N کمتر از 100 و M=5 این کد Accept شد اما برای مسئله مشابه با M های بزرگتر ، برای مثال M=100 برنامه ما در محدوده زمانی مورد نظر به جواب نمیرسید و نتیجه ارسال کد Time Limit Executed میشد.

برای حل این سوال اینبار از یکی از Data Structure های C++ Standard Library به نام Bitset استفاده میکنیم که میتوان از این Solution به عنوان مثالی برای یادگیری Bitset نیز استفاده کرد.

میشود Bitset را به عنوان یک آرایه ای از متغیر Boolean تعریف کرد، اما این تعریف بسیار ناقص میباشد زیرا برای یک آرایه Boolean توابعی مانند شیفت به چپ ، شیفت به راست ، نقیض ، مساوی بودن ، OR , AND , XOR با یک آرایه Boolean دیگر وجود ندارد و برای پیاده سازی هریک نیاز به تابع نویسی داریم. اما در Bitset تمام این امکانات گنجانده شده است.

ادامه مطلب

مقدمه

بسیاری از مسائل برنامه نویسی تنها با استفاده از Dynamic Programming حل میشوند در این نوشتار سعی شده که طرح کلی برنامه نویسی پویا و دلیل و مزایای استفاده از آن با چندین پیاده سازی برای تابع Fibonacci بیان شود. در مطالب آینده مثال های مهم تر و به نسبت پیچیده تری قرار میگیرد.

برنامه نویسی پویا یا Dynamic Programming چیست ؟

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

در استفاده از تکنیک برنامه نویسی پویا ما حل مسئله را توسط حل مسئله های کوچکتر بیان میکنیم با این تفاوت که با ذخیره سازی از محاسبه دوباره اجتناب میکنیم.

ادامه مطلب

ادامه مطلب