معرفی مسابقات ACM

[سارا-افشار 36,437]

مسابقات ACM-ICPC يکي از معتبرترين مسابقات علمي در حوزه ي کامپيوتر است. اين مسابقات بصورت تيمي و با هدف طراحي الگوريتم براي مسائل مطرح شده و پياده سازي الگوريتم طراحي شده به صورت بهينه در زمان مشخصي است. در اين مسابقات هر تيم از سه عضو تشکيل شده است که بايد تسلط کافي بر طراحي الگوريتم، برنامه نويسي و زبان انگليسي داشته باشند.

 

تاريخچه ACM:

 

ACM مخفف عبارت Association for Computing Machinery است و نام اولين انجمن علوم کامپيوتر مي باشد که در سال 1947 تاسيس شده است. ICPC مخفف International Collegiate Programming Contest است و به نوع خاصي از مسابقات برنامه نويسي گفته مي شود . اولين مسابقه رسمي ICPC توسط انجمن ACM در سال 1976 برگزار شد و از سال 1980 به بعد نظارت بر اين مسابقات به دانشگاه Baylor واگذار شد. از اين مسابقات استقبال گسترده اي به عمل آمد و به سرعت گسترش يافت تا جايي که در سال 1997، IBM به عنوان sponsor (حامي) اصلي اين مسابقات معرفي شد و تعداد تيم هاي شرکت کننده به بيش از 3000 تيم از بهترين دانشجويان 67 کشور دنيا رسيد.

قاره آسيا از سال 1995 به مسابقات ACM پيوست و بعد از 4 سال تهران نيز به عنوان يکي از سايتهاي قاره آسيا پذيرفته شد. دانشگاه شريف به عنوان يکي از 10 سايت آسيا تا کنون 7 دوره مسابقه ,همه ساله در اواخر پاييز برگزار مي کند. در اين مسابقات تيمهايي از دانشگاههاي سرتاسر آسيا از جمله دانشگاههاي داخل کشور در رقابتي تنگاتنگ براي حضور در مرحله نهايي و مسابقات جهاني پا به ميدان مي گذارند.

هدف و چگونگي اجرا مسابقه:

 

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

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

 

خوش بينانه ترين حالت ها براي جواب ها:

 

صحيح : برنامه تمامي( test case هاي) تعيين شده را با موفقيت و بدون باگ گذرانده و جواب درست است.

نادرست: برنامه به ازاي يکي يا تمامي test case ها جواب نادرست داده و يا شکل خروجي شما ايده آل نيست.

خطاي زمان اجرا: برنامه با Run_Time Error مواجه گرديده است.

خطاي زمان کامپايل: برنامه با Compilation Error مواجه گرديده است.

زمان غيرمجاز: زماني که برنامه شما صرف يافتن جواب مي کند از حد مجاز بيشتر است. برنامه بايد سريع تر داده ها راپردازش نمايد.

 

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

1- بايد به يکي از زبانهاي برنامه نويسي متداول و اعلام شده توسط کميته اجرايي مسابقات تسلط کامل داشته باشند. اين زبانها عموما C++ ، C و يا جاوا مي باشند.

2- اعضاي تيم بايد تسلط کافي بر مفاهيم طراحي الگوريتم ، بهينه سازي الگوريتم ، پيچيدگي الگوريتم ، ساختمان داده ها , ریاضیات گسسته و … داشته باشند.

3- حداقل يکي از اعضاي تيم بايد تسلط کامل بر زبان انگليسي داشته باشد تا بتواند سوالات را به زبان مادري ترجمه و در اختيار ساير اعضاي گروه قرار دهد. ( سوالات اين مسابقات در تمامي مراحل به زبان انگليسي طرح مي شود.)

4- حداقل يکي از اعضا بايد دست به تايپ خوبي داشته باشد تا بتواند الگوريتمهاي طراحي شده را سريعا به کد تبديل کند. (تمامي مراحل اين مسابقات به صورت عملي و در پشت کامپيوتر برگزار مي شود.)

تبديل الگوريتم به کد خود يک مهارت بزرگ است که در واقع عامل اصلي طبقه بندي تيمها در مسابقات اين چنيني محسوب مي شود. در زمان مسابقه يک سيستم در اختيار هر تيم قرار مي گيرد که اين سه دانشجو به طور مشترک با اين سيستم شروع به حل مسائل مي کنند. مدت زمان هر مسابقه 5 ساعت است و حداقل 8 سوال در اختيار شرکت کنندگان قرار مي گيرد.

پاسخ دادن به هر سوال در حقيقت نوشتن يک برنامه است. به عبارت ديگر در صورت مسئله از شرکت کنندگان خواسته مي شود تا برنامه اي بنويسند که اطلاعات مشخصي را از فايل ورودي معيني، (مثلا A.in) بخوانند و پس از انجام پردازش هاي خاصي که در متن سوال آمده، نتيجه را در يک فايل خروجي (مثلا A.out) يا خروجي استاندارد (مانيتور) چاپ کنند.

هر دانشگاه تعدادي دانشجو با توجه به ظرفيتي که دانشگاه شريف مشخص مي کند براي شرکت در مسابقات به تهران اعزام مي کند؛ که اين ظرفيت با توجه به تعداد سوالهاي حل شده توسط تيمهاي دانشگاه در دوره هاي قبل مشخص مي شود. معمولا دانشگاه ها براي انتخاب تيم هاي اعزامي خود، يا مسابقاتي محلي در سطح دانشگاه خود برگزار مي کنند و يا اينکه از دانشجويان مي خواهند که در مسابقه Online شريف که معمولا در مهر ماه برگزار مي شود، شرکت کنند و از نتيجه آن به عنوان ملاکي براي تعيين تيمهاي اعزامي به شريف استفاده مي کنند. تيم¬هاي منتخب (سه تيم برتر) مسابقه ي منطقه اي شريف، به مرحله جهاني راه مي¬يابند و از هر دانشگاه حداکثر يک تيم مي¬تواند به اين مرحله صعود کند. در سال 1385 تيم¬هاي دانشگاه¬هاي شريف، شهيد بهشتي و تيمي از دانشگاه ويتنام به مرحله جهاني صعود کردند.

 

قوانين زير براي مسابقات تدارکاتي Acm در دانشگاه علم وصنعت از سوي کميته acm اين دانشگاه منتشر شده که تقريباً شبيه مسابقات اصلي است:

- در زمان مسابقه تعدادي سوال در اختيار شرکت کنندگان قرار خواهد گرفت که موظفند در زمان معين به آنها پاسخ دهند.

- سوالات مسابقه تماما به زبان انگليسي است و ترجمه نمي شوند.

- به همراه داشتن هر گونه کتاب جزوه راهنما يا فرهنگ لغات در روز مسابقه آزاد است.

- به همراه داشتن ديسکت يا هرگونه فايل برنامه اي از پيش نوشته شده غير مجاز است.

-پاسخ سوالات در زمان مسابقه به داور مسابقه ارسال خواهد شد وپاسخ سوالات در همان زمان از طرف داور اعلام خواهد شد.

- نحوه رده بندي تيم ها بر اساس تعداد سوالات حل شده خواهد بود. در صورت مساوي بودن تعداد سوالات حل شده زمان ارسال پاسخ به داور، مد نظر خواهد بود.

- به ازاي هر پاسخ نادرست ارسال شده به داور 20 دقيقه جريمه براي آن سوال در نظر گرفته مي شود.

 

مراجع کتاب برای مطالعه:

۱- استراتژي هاي حل مسئله (نوشته ي :آرش اميني - داود وکيلي)

۲- مسائل الگوريتمي و برنامه نويسي( نوشته ي :دکتر قدسي – محمد مهديان)

۳- سؤالات المپياد کامپيوتر در ايران(نوشته ي :رسول حاجي زاده)

۴- چگونه مسئله حل کنيم (نوشته ي :جرج پوليا / احمد)

۵- کارگاه اعداد کنيم (نوشته ي :جرج پوليا / پرويز شهرياري)

6- the Art of Programming Contest )Compiled by: Ahmed Shamsul A(