ACM

مقدمه

مسابقه ی برنامه نویسی دانشجویی ای.سی.ام (ACM-ICPC) بزرگترین مسابقه ی سالیانه برنامه نویسی است که از سال ۱۹۷۷ برگزار می‌شود و تأکید آن بر تقویت کار گروهی، مهارت‌ های برنامه نویسی و توان حل مسئله در بین دانشجویان رشته های مرتبط با علوم و مهندسی کامپیوتر است. این رقابت علمی بین‌المللی که در نوع خود معتبرترین محسوب می‌شود، دانسته‌های علمی، مهارت‌ های برنامه نویسی و توان کار گروهی دانشجویان دانشگاه های جهان را در ۶ قاره به رقابت می گذارد. در این مطلب به بررسی تاریخچه، نحوه برگزاری و قوانین این مسابقات و همچنین اهداف و مزایای شرکت در این مسابقات پرداخته و در پایان در مورد نحوه عضویت در تیم ACM دانشگاه توضیحاتی ارائه می کنیم.

تاریخچه ACM

ACM مخفف عبارت Association for Computing Machinery است که اولین انجمن علوم کامپیوتر با نام انجمن ماشین‌‏ های کامپیوتری در دنیا می باشد و در سال ۱۹۴۷ تاسیس شده است.

ICPC مخفف International Collegiate Programming Contest است و به نوع خاصی از مسابقات برنامه نویسی گفته می شود که در سطح دانشگاهی برگزار می گردند. لوگوی این مسابقات به صورت زیر است:

که ابر نماد Think، چراغ نماد Create و بادکنک نماد Solve می باشد.

اولین مسابقات رسمی ICPC توسط انجمن ACM در سال ۱۹۷۶ برگزار و از سال ۱۹۸۰ به بعد نظارت بر این مسابقات به دانشگاه Baylor واگذار شد. از این مسابقات استقبال گسترده ای به عمل آمد و به سرعت گسترش یافت تا جایی که در سال ۱۹۹۷، IBM به عنوان حامی اصلی این مسابقات معرفی شد و تعداد تیم های شرکت کننده به بیش از ۳۰۰۰ تیم از بهترین دانشجویان ۶۷ کشور دنیا رسید. این مسابقه هر سال در چند مرحله در سطح جهان برگزار میشود.

قاره آسیا از سال ۱۹۹۵ به مسابقات ACM پیوست و بعد از ۴ سال تهران نیز به عنوان یکی از سایت های قاره آسیا پذیرفته شد. این مسابقات هر ساله در اواخر پاییز بر گزار می شود. در این مسابقات تیم هایی از دانشگاه های سرتاسر آسیا از جمله دانشگاه های داخل کشور در رقابتی تنگاتنگ برای حضور در مرحله نهایی و مسابقات جهانی پا به میدان می گذارند.

مراحل مسابقه

مراحل ابتدایی توسط دانشگاه ها و به طور داخلی برگزار می شود که معمولا دانشگاه ها برای تعیین شرکت کنندگان مرحله منطقه ای، مسابقات محلی برگزار می کنند. مرحله‌ی بعد توسط سایت های منطقه‌ای برگزار می شود و دانشگاه ها در مسابقه منطقه ای رقابت کرده و سپس تیم های برتر به مرحله ی نهایی (World-Final) که توسط مؤسسه ی ACM برگزار می شود، راه پیدا می کنند. در مسابقه منطقه ای امکان حضور بیش از یک تیم از هر دانشگاه وجود دارد، اما در مرحله فینال فقط یک تیم از هر دانشگاه رقابت خواهد کرد. از هر منطقه حداقل یک تیم به مرحله نهایی راه پیدا می کند.

مسابقات ACM در ایران

ایران از سال ١٩٩٩ تاکنون به عنوان سایت غرب آسیا، مسابقات منطقه ای غرب آسیا را برگزار می کند. این مسابقات هر ساله به جز یک سال (۲۰۱۱) به میزبانی دانشگاه صنعتی شریف و به مدیریت دکتر محمد قدسی در آذر ماه برگزار می شود. سال ٢٠١١، دانشگاه تهران میزبانی این مسابقات را بر عهده داشت. در این مسابقات ۲ یا ۳ دانشگاه برتر (از هر دانشگاه یک تیم) جواز حضور در مسابقات جهانی (World-Final) را کسب می کنند. بهترین نتیجه ای که تا به حال ایران در مسابقات جهانی کسب کرده است، مقام نهم در سال ۲۰۰۱ بوده است.

شرح مسابقه

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

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

پاسخ دادن به هر سوال در حقیقت نوشتن یک برنامه است. به عبارت دیگر در صورت مسئله از شرکت کنندگان خواسته می شود تا برنامه ای بنویسند که اطلاعات مشخصی را از فایل ورودی خوانده و پس از انجام پردازش های خاصی که در متن سوال آمده، نتیجه را در فایل خروجی یا خروجی استاندارد (مانیتور) چاپ کنند. سپس برنامه نوشته شده توسط شرکت کنندگان به داور فرستاده می شود (ُSubmit) تا عمل قضاوت (Judge) روی آن انجام گیرد. در این مرحله برنامه فرستاده شده به داوران توسط نرم افزاری به نام PC2 اجرا شده و تست های آزمون (Test-Case) به برنامه داده می شود. اگر برنامه قادر به ارائه پاسخ صحیح نباشد، ٢٠ دقیقه جریمه برای تیم ارسال کننده جواب منظور و به آن تیم اطلاع داده می شود تا به تصحیح آن بپردازد، و اگر برنامه پاسخ صحیح را تولید نماید، زمان حل آن سوال (که برابر است زمان صرف شده تا ارائه پاسخ صحیح بعلاوه جریمه های منظور شده به ازای هر تلاش ناموفق) محاسبه شده و یک بادکنک دریافت می کند.

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

آشنایی با برخی از قوانین مسابقات ACM

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

1. باید به یکی از زبان های برنامه نویسی متداول و اعلام شده توسط کمیته اجرایی مسابقات نظیر Pascal، C++، C و یا Java تسلط کامل داشته باشند.
2. اعضای تیم باید تسلط کافی بر مفاهیم طراحی الگوریتم ها، بهینه سازی الگوریتم ها، پیچیدگی الگوریتم ها، ساختمان داده ها و ... داشته باشند.
3. حداقل یکی از اعضای تیم باید به زبان انگلیسی مسلط باشد تا بتوانند سوالات را به زبان مادری ترجمه و در اختیار دیگر اعضای گروه قرار دهد. (سوالات این مسابقات به زبان انگلیسی طرح می شود)
4. حداقل یکی از اعضا باید دست به تایپ خوبی داشته باشد تا بتواند الگوریتم های طراحی شده را سریعا به کد تبدیل کند. (تمامی مراحل این مسابقات به صورت عملی و در پشت کامپیوتر برگزار می شود)

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

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

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

• سوالات مسابقه تماما به زبان انگلیسی است و ترجمه نمی شوند.
• هر تیم مجاز به آوردن حداکثر ۳۰ صفحه (یا ١٥ صفحه دو رو) از پیش آماده شده در روزه مسابقه می باشد.
• ورود هر گونه وسیله‌ی ارتباطی از قبیل موبایل، کول دیسک و ابزار مشابه ممنوع است و در صورت کشف موجب محرومیت تیم‌ها خواهد شد. امکان اتصال کول دیسک یا استفاده از CD به کامپیوترهای مسابقه نیست.
• پاسخ سوالات در زمان مسابقه به داور مسابقه ارسال و نتیجه داوری در همان زمان، معمولا به یکی از پیام های زیر از طرف داور اعلام خواهد شد:

• AC-Accepted: برنامه شما خروجی مناسب و کاملا صحیحی را برای ورودی داور تولید می کند.
• PE-Presentation Error: برنامه شما خروجی را صحیح تولید می کند اما در نمایش خروجی دچار مشکل است.
• CE-Compile Error: برنامه شما مشکل کامپایلی دارد.
• RE-Runtime Error: برنامه شما مشکلاتی از قبیل عدم دسترسی به نقاطی از حافظه (Segmentation Fault) و استثناهای ممیز شناور (Floating Point Exception) دارد.
• TL-Time Limit Exceeded: برنامه شما محدودیت زمانی سوال را رد کرده است.
• ME-Memory Limit Exceeded: برنامه شما محدودیت فضایی در نظر گرفته شده برای سوال را رد کرده است.
• OL-Output Limit Exceeded: برنامه شما بیش از محدودیت در نظر گرفته شده برای چاپ کردن در سوال، خروجی چاپ می کند.
• WA-Wrong Answer: برنامه شما خروجی کاملا غلطی را تولید می کند. همچنین ممکن است به جای WA، PE داده شود!

• نحوه رده بندی تیم ها بر اساس تعداد سوالات حل شده خواهد بود. در صورت مساوی بودن تعداد سوالات حل شده، زمان ارسال پاسخ به داور مدنظر خواهد بود.
• به ازای هر پاسخ نادرست ارسال شده به داور، ۲۰ دقیقه جریمه برای آن سوال در نظر گرفته می شود.

اهداف و مزایای شرکت در مسابقات ACM

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

اگرچه ACM مزیت های قراردادی زیادی دارد، ولی هدف اصلی آن این مزیت فلسفی و ذاتی آن است.

• فواید ذاتی ACM: این ها همان فوایدی هستند که شما چه در صورت پیروزی و چه در صورت شکست از آن ها بهره مند می شویدکه عبارتند از:

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

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

• برنامه نویسی و کد زدن (سریع)
• الگوریتم

• کار گروهی (Team Work): از جمله مزیت های دیگر این مسابقات در برابر مسابقات دیگر مثل المپیاد، کار گروهی در این مسابقات است. شما در ACM باید در گروه های ۳ نفری مسابقه دهید و همچنین ۱ کامپیوتر نیز بیشتر ندارید. پس مدیریت گروه در این مواقع بسیار حائز اهمیت می شود و تیم باید به خوبی به تقسیم کار بپردازد. همچنین به هیچ عنوان نباید درگیری یا جدلی ایجاد شود وگرنه ممکن است همه چیز از دست برود. در نتیجه ACM تمرین خوبی برای کار گروهی خواهد بود.

• فواید قراردادی ACM: این مزیت ها، تنها در صورت پیروزی در مراحل مختلف ACM از جمله مسابقات جهانی به دست می آیند که عبارتند از:

• یک پوئن مثبت در رزومه ی علمی: همانند هر مسابقه ی جهانی دیگری (همچون المپیاد) مسابقات ACM هم مزیت بسیار خوبی در رزومه فرد می تواند داشته باشد؛ علی الخصوص اگر فرد (به عنوان نماینده ای از کشورش) در مسابقات جهانی شرکت کرده باشد. داشتن رتبه در مسابقات جهانی ACM شانس فرد را برای ادامه تحصیل در دانشگاه های معتبر جهانی به صورت چشمگیری افزایش می دهد و حتی دانشگاه های معتبر دنیا هم ممکن است از افراد تیم های برتر در مسابقات جهانی ACM دعوت به عمل آورند. عموما هر سال در مسابقات منطقه ای و جهانی به ١٠ الی ١٥ تیم ابتدایی لوح افتخاری با تایید شرکت IBM به شرکت کنندگان اهدا می گردد که تاثیر بسیار خوبی در رزومه علمی شما و عملا ادامه تحصیلات عالیه خواهد داشت. این مسابقه علاوه بر اعتبار دانشگاهی، مورد توجه شرکتهای بزرگی مثل IBM و Google نیز قرار گرفته است. شرکت IBM، حامی برگزاری این مسابقات، در هر دوره با برگزاری سخنرانی‌ها و نمایشهای فنی سعی می کند دانشجویان شرکت کننده در مرحله ی نهایی را به کار در این شرکت جذب کند. شرکت Google نیز چند بار در سال‌های گذشته تمام اعضای مرحله‌ی نهایی (بیش از هشتاد تیم) را به محل مرکزی این شرکت دعوت کرده است. از این لحاظ این مسابقات از جایگاه مهمی در سطح جهان (و نه فقط ایران) برخوردار است.

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

عضویت در تیم ACM دانشگاه

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