Анализ на задача 3 - Университет

Третата задача от конкурса тази година всъщност се свежда до две силно различими подзадачи, след по-подробен анализ. Едната е как оптимално да се разделят на бележки темите, които всеки има да праща, а другата - как да се разпределят студентите по места. Интересното е, че макар първата част да не зависи от втората, разпределението по места много силно се влияе от броя бележки, които всеки трябва да изпрати. Това води до сериозната дилема върху коя част колко усилия да бъдат отделени.

Първата подзадача се свежда до много често срещания и изследван Bin packing problem[1]. За момента не е известен алгоритъм, който да успява да намери оптимално разбиване за ограниченията в задачата, но дори доста простите евристики постигат много добри резултати. Темите лесно могат да бъдат подредени в намаляващ ред по дължина и всяка да се постави на първата бележка, на която има достатъчно свободно място, или на нова, ако такава не съществува. Тази стратегия гарантира използването на най-много 11/9*MIN+1 бележки, където MIN е теоретичният оптимум. Доказано е също така, че не съществува полиномиален алгоритъм, който да гарантира много по-добри резултати.

Втората подзадача също се свежда до широко изследван проблем – Quadratic assignment problem[2]. Поради практическата насоченост съществуват множество добри идеи и алгоритми по въпроса. Един от тези, на които наистина си заслужава да се обърне внимание, е A Greedy Genetic Algorithm for the Quadratic Assignment Problem[3], който постига впечатляващи резултати на стандартните тестове за този проблем от QAPLIB[4]. Ключовите моменти, както във всеки генетичен алгоритъм, са първоначалните популации и удачното им съчетаване. Новият аспект, който се появява в конкретната ситуация на тази задача, е, че тежестите на връзките между отделните студенти зависят от първата подзадача и съответно не са оптимални. В течение на построяването на разпределението по места могат да бъдат правени нови опити за оптимизиране на кореспонденцията между ключови студенти. По този начин усилията върху първата подзадача могат да бъдат концентрирани в области, за които това би било най-полезно.

Оценяването беше извършено посредством десет теста, обхващащи целия диапазон от възможни размери. Наборът включва и три специални теста: T5, в който има само двама студенти и резултатът зависи само от решаването на първата подзадача, и T6 и T7, в които пък всички теми са по-дълги от половината на размера на бележката и съответно резултатът зависи изцяло от решаването на втората подзадача. Като цяло в тестовете беше дадена по-голяма тежест на разпределението на темите, за да могат да изпъкнат очакваните малки разлики в различните решения, но има и един допълнителен тест за втората подзадача, където се очакват по-разнообразни решения.

Линкове

[1] http://en.wikipedia.org/wiki/Bin_packing_problem    http://www.cs.arizona.edu/icon/oddsends/bpack/ bpack.htm

[2] http://en.wikipedia.org/wiki/Quadratic_assignment_ problem

[3] http://web.mit.edu/jorlin/www/papersfolder/QAP.pdf

[4] http://www.seas.upenn.edu/qaplib/

Студент печели Турнира на БАСКОМ

За шеста поредна година Българската асоциация на софтуерните компании (БАСКОМ), проведе Турнир по програмиране. Той се състоя в рамките на третия новогодишен кръг от частния конкурс на PC Magazine Bulgaria и Мусала Софт. В конкурса класирането оглави Божидар Пенчев, който е студент втори курс в специалност Компютърни науки към СУ. Той за първи път повежда кръг от състезанието и също така за първи път печели Турнира на БАСКОМ. Неговата награда бе в размер на 1500 лв. Втора награда, която беше в размер на 1000 лв., отиде при Георги Герганов, а участникът, заел трето място - Йордан Маджунков, получи 500 лв. Победителите са бивши състезатели в ученически национални и международни състезания и олимпиади, а Георги и Йордан са лауреати от международна олимпиада по физика. Всички получиха и едногодишен абонамент за PC Magazine Bulgaria.

Организацията на награждаването и осигуряването на наградния фонд за турнира се осъществи с подкрепата на фирми - спонсори от БАСКОМ – Telerik, Nemetschek Bulgaria и Dreamix. Наградите бяха раздадени на официална церемония на 29 януари в столичния клуб „Битбургер” по време на традиционното новогодишно парти на БАСКОМ. Домакин на събитието бе председателят на БАСКОМ Георги Брашнаров, а сред гостите бяха Лидия Петкова, отдел продажби в Telerik, Горан Миланов, мениджър продажби - Nemetschek Bulgaria, Цветелин Андреев, ръководител проекти - Dreamix, Тервел Няголов - главен ре- дактор на PC Magazine Bulgaria, Елена Маринова – президент на Мусала Софт, и др.