Програмчлалын олимпиад

Чөлөөт нэвтэрхий толь — Википедиагаас
Jump to navigation Jump to search

Спортын програмчлал (програмчлалын олимпиад, англ. programming contests, орос. спортивное программирование) — компьютерт суурилсан янз бүрийн бодлогыг бодох оюун ухааны тэмцээн, бодолтыг төрөл бүрийн алгоритмуудын тусламжтай аль нэг програмчлалын хэл дээр хийдэг. Оролцогчдод хэд хэдэн бодлого өгөх ба хэрэв оролцогчийн бичсэн код шүүгчдийн бэлдсэн тестүүдийг амжилттай давбал бодолт амжилттай болсонд тооцно. Бодлогууд нь хөгжилтэй, дахин давтагдашгүй абстракт нөхцөлтэй байдаг, үүнд сургуулийн сурагчид, оюутнууд болон настай хүмүүс ч оролцох боломжтой. Бодлогууд гурван янз байдаг (тэмцээний төрөл болон оролцогчдын чадвараас хамаарч):

  • алгоритмын — контестэнд хэд хэдээр орж ирдэг, бүтэн ба тал бодолт хийх боломжтой.
  • оновчтой байдлын — бүтэн бодолтгүй нэг том бодлого. Оролцогчийн бодолт хэр сайн оновчтой болсноор хэмжигдэнэ. Зарим тохиолдолд оролцогчдийн бодолт харилцан бие биенээс хамаардаг(тоглоом).
  • судалгааны — ICFPC-т байдаг шиг оноо нь объект дээрээс амжилттай олдсон ямар нэг олдоцын тоо хэмжээ, чанараас хамаардаг.

Бодолт нь тусгайлан өгөгдсөн програмчлалын хэл дээр бичигдcэн програм байх ба сервер дээр оролцогчийн кодыг компайлдаж сандбокс дээр ажиллуулж stdio-гоос оролтыг эсвэл оролтын файл уншиж хариуг гаргаж ирнэ.

Янз бүрийн форматаар мужийн/регионы болон дэлхийн аварга шалгаруулах онсайт-тэмцээнүүд, интернет-тэмцээн ба онсайт-финалууд нь жилд нэг удаа болдог.

Түүнчлэн интернэтэд бэлтгэл сургуулилт хийж болох янз бүрийн сайтууд байдаг.

Хамгийн амжилттай оролцогчид нь ихэвчлэн сургуулийн наснаас эхлэн энэ "спортоор" хичээллэсэн нөхдүүд байдаг.

Манай хойд болон урд хөршид энэ төрлийн тэмцээнд програмчлал сонирхдог залуус маш идэвхтэй оролцдог ба одоогийн байдлаар ICFPC-д оросоос топ 100 командын эгнээнд олон команд орсон байна.

Тэмцээний дүрэм[засварлах | edit source]

ACM — их сургуулийн оюутнуудад зориулсан. Хугацаа 5 цаг. Нэг бодлогын бодолтын хариуг тэр дор нь сервер дээр өгөгдсөн тестүүдээр шалгаад илгээдэг. Дэлхийн аваргад оюутан зөвхөн 2 удаа л оролцож болно (мужийн тэмцээнд — 5 удаа), тийм болохоор топ их сургуулиуд 3 хүртэлх шилдэг оролцогчидоо 2 жилд нэг удаа алдах ба шинээр бэлтгэх зайлшгүй шаардлага гарна. АСМ-н дүрэм нь бусад жижиг тэмцээнүүдэд хүртэл нөлөөлдөг алдартай дүрмүүдтэй.

ACM нэмэх — энэ нь АСМ тай төстэй боловч амжилттай бодолтонд нэг оноо биш харин 1-0.2*(амжилтгүй илгээсэн бодолтын тоо) гэсэн томъёогоор хэмжигдэх ба 6-р буруу илгээлтээс хойш дахин бодолтоо илгээх нь утгагүй юм.

IOI — сургуулийн сурагчдад зориулсан Олон улсын Мэдээлэлзүйн олимпиад (International Olympiad in Informatics). Бодолтын олон удаа илгээх боломжтой, шууд контестэд явж буй бодолтын процессыг интернэтээр мониторинг хийж болдог. Харамсалтай нь АСМ-тай адилхан болчихгүйн тулд токенийг бий болгосон(зарим тестийг далд байлгадаг). Авах оноо нь давсан тестийн тооноос хамаардаг (максимум=100, заримдаа 110 хурдэг). Энэ олимпиадад Монгол улсаас 2011 оны байдлаар хоёр медаль авсан байгаа. Тэдгээр нь 2005 онд Польш улсад болсон олимпиадаас Ч. Доржнамжилын болон 2006 онд Мексикт болсон олимпиадаас Б. Батбаатарын тус тус авсан хоёр хүрэл медаль юм.

Topcoder algorithm — бүх хүссэн хүн оролцох боломжтой. Нэг жава-клиент дээр "тоглож" болдог болохоор бусдаас онцгойрдог. Шалгалт нь интерактив биш, ө.х. буруу бодолтын талаар төгсгөлд нь л мэдэж болно. Мөн тэнд бусад оролцогчдын бодолтын алдааг олох үе/фаз байдаг(Challenge Phase - SRM), оролцогч нь бодлогын нөхцөлд таарсан оролтын өгөгдөл болон хариуг бэлдэж чэлленж хийдэг. Зөв чэлленж хийвэл нэмэлт оноо авч буруу байвал хасах оноо авна. Хэл нь жава, С++,C#, VB.net;

Google Code Jam — оролцогчид нь оролдлого болгондоо санамсаргүйгээр генерац(үүсгэгдсэн) хийгдсэн тест татаж авах ба үүнийг өөр дээрээ туршиж үзээд гарсан хариуг(файлыг) илгээнэ. Тийм болохоор оролцогч нь ямар ч хэлийг ашиглах боломжтой.

ICFPC — оновчтой бодолтыг олох ба судалгаа хийх бодлогуудтай. Гурав хоног командаар шийдлээ олдог болохоор энэ нь жинхэнэ амьдрал дээрх програмчлалтай төстэй бас "сургуулийнхны" хийдэг бодолтуудаас өөр байдаг.

Шүүгчдийн ажил[засварлах | edit source]

Тестлэж буй системийн ажиллагааг хангах, компиляторуудыг бэлдэх, бодлого болон тестийн таарч байгааг шалгах үүрэгтэй ба оролцогчдын асуусан асуултанд булийн логик байдлаар хариулна: YES, NO, NO COMMENT (байнга тохиолдох хариулт). Заримдаа шүүгчид алдаатай тест хийж алдах ба энэ үед режадж(англ. rejudge) хийж дахин бүх бодолтыг шалгана.

Ариун дайн[засварлах | edit source]

Тусгай олимпиадын гарчигууд:

  • олимпиадчид жинхэнэ програмчлалаар хичээллэж чадах уу?
  • програмчлалын олимпиадыг алдаршуулах хэрэгтэй юу?
  • макросуудыг ашиглах хэрэгтэй юу?

Талууд:

Тийм:

  • Алгоритмын мэдлэг нь зарим шинэ болон том проект хөгжүүлэлтэд хэрэг болно. Тухайлбал хайлтын систем нь жирийн паттерн болон декомпозицийн тусламжтайгаар проеклогдохгүй.
  • Яагаад том компаниуд эдгээр олимпиад-тэмцээнүүдэд их анхаардгийг төвөггүй мэдэж болно. Дэлхийн олимпиадын аваргууд том том компанид төвөггүй ордог.
  • Алгоритмууд энэ бол бидний бүх юм!

Үгүй:

  • Олимпиадын бодлогууд нь практикийн ямар ч ач холбогдолгүй байх тохиолдол байдаг. Жишээ нь: цэвэр математикийн бодлогууд эсвэл ямар нэг констант хэвлэж гаргах г.м.
  • Бодлого зохиож буй хүмүүсээс болж алдаатай бодлого тавигдах нь бий(жишээ нь гарны сканкод, PCX формат)
  • Хэсэг бодлогууд нь сурах бичиг дээр байдаг алгоритмуудыг шаардах боловч стандарт санд тэдгээр алгоритмууд нь байхгүй( огтлол эсвэл богино замын алгоритмууд).
  • Олимпиадын бодлогуудын бодолт нь маш богино (ихэнхдээ 200 мөрөөс бага), бүдүүлэг байдлаар бичигдсэн.
  • Бодолтонд хамгийн суурь хэрэгслүүдийг ашигладаг ба энэ нь олон оролцогчтой болоход чиглэгдсэн байдгаараа бичиж байгаа хэлээ сайн судлахгүйгээр бичих боломжийг олгодог.
  • Туслах санг ашиглах боломжгүй. Түүнчлэн java BigInteger гэх мэт сангийн(класс) тусламжтайгаар ч бодох боломжгүй урт арифметикийн бодлогууд байдаг, бас тэмдэгт мөртэй ажиллах бодлогууд зарим хэл дээр(ruby,php,C#,java,...) маш амархан хийгддэг бөгөөд үүнээс болж энгийн хэл(pascal,c++) хэрэглэгчид хугацаа их алддаг.
  • Хуучин аваргуудын талаар ямар нэг гайхалтай мэдээ ховор байдаг, тэд заримдаа шүүгчдийн бүрэлдэхүүнд явах нь элбэг, эсвэл нэг том компанид орсон нь дуулддаг. Магадгүй энд өөрийн шалтгаан байж болох юм.
  • Олон амжилтгүй оролтоос болж тамирчид сэтгэл санаагаар унаж програмчлалаар цаашид хичээллэх сонирхолгүй болдог.
   Programming contests are only programming contests, and nothing more (c)Petr

Серверүүд[засварлах | edit source]