Impulzus

 
A Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Hallgatói Képviseletének lapja
Random cikkajánló

Füstölők, illóolajok

Persze itt nem a dohányzásra szeretném buzdítani a népet.

Objektum-orientált főzés

"...alternatív elnevezése az igénytelen konyhaművészet."

Theo papa

"...ők mindent megtesznek"

EHK-tükör

Együttműködve a KTH leendő vezetőségével, az EHK koordinálásában a karok bevonásával elkezdődött a hallgatók felvilágosításához szükséges előkészítő munka, hogy minden információhoz hozzájussatok még időben. Ezt egyelőre jelentősen akadályozza, hogy nincsenek még készen az Ügyrendek.

20 éves a PC

"Becsapjuk magunkat azzal, hogy mennyi minden újat tud a gépünk, pedig pont a PC-nek köszönhetjük, hogy ennyire lemaradtunk."

Közös tárgyak

Közös tárgyak, tanárok.

Életkép egy büféinfós hétköznapjáról, elmondva szabadköltészetben

Sokat éltél vidéken és nem fejlődött ki az agyad!

Olvassunk!

Megcáfolását (vagy meg nem cáfolását) az olvasóra bíznám. A bulikról csak annyit, hogy voltunk más karok gólyabáljain, a saját gólyabálunkon, részt vettünk a Villanykari Korsóavató Szakestélyen.

Kórházajánló 3 – új helyeken

Közöltem, hogy azért jöttem ide, mert szeretném megvizsgáltatni magam hozzáértő emberrel, és azért nincs háziorvosi beutalóm, mert egyetemista vagyok, egy hete költöztem fel, és ebből kifolyóan a lakcímbejelentést sem tudtam még megoldani.

Beszámoló a 2001. évi ACM programozási versenyről

Az ACM egy nemzetközi feladatmegoldó programozási verseny, melyen háromfős, egyetemistákból álló csapatok indulhatnak. Az egyetemi forduló első két helyezett csapata jut tovább a regionális fordulóba (Közép-Európa), onnan pedig az első 2-3 csapat kerül be a nemzetközi döntőbe, amelyet többnyire az Amerikai Egyesült Államokban, idén pl. Hawaii-on rendeznek. A csapatok főleg a dicsőségért és ösztöndíjakért versenyeznek.

A verseny időtartama 5 óra, ezalatt 8 programozási feladatot kell megoldani, azaz 8 programot kell elkészíteni a specifikációnak megfelelően. Tervezés és dokumentálás nem szükséges, sőt, még kommentezés vagy a program helyes működésének bizonyítása sem! Egy megoldást akkor fogadnak el a szervezők, ha a beadott program az általuk előre meghatározott bemenetre (a "tesztvektorra") rövid időn belül helyes választ ad. Természetesen a konkrét tesztvektort nem árulják el a versenyzőknek, de várható, hogy a vektor a teljes specifikációt számon kéri. A félig működő vagy közelítő megoldások érvénytelennek számítanak. Az a csapat nyer, amelyik a legtöbb jó megoldást adja be, döntetlen esetén az győz, aki - egy speciálisan számított időeredmény alapján - kevesebb idő alatt oldotta meg a feladatokat. Mindhárom forduló a fenti sémát követi, különbség csak a feladatok nehézségében mutatkozik.

A versenyzőknek egyaránt jól kell tudniuk gyors és helyes algoritmusokat tervezni, és azokat precízen lekódolni. A programok elkészítéséhez csapatonként egyetlen számítógép áll rendelkezésre (C, C++ és Pascal fordítókkal), semmilyen más félvezetőeszközt nem szabad használni. A kész program forráskódját kell beadni, melyet a szervezők azonnal tesztelnek, és néhány percen belül elárulják, hogy elfogadták-e a megoldást, vagy ha nem, akkor két szóban megmondják, miért (compile error, run-time error, wrong answer, timed out, presentation error). Egy feladatra többször is be lehet adni megoldást.

A jó szerepléshez jó szervezési készség, az algoritmusok elméletében való jártasság, kiváló problémamegoldó készség és pontos kódolási képesség szükséges. A legnagyobb nehézséget a helyes algoritmus (és adatábrázolás) megtalálása okozza. Bár a tipikus algoritmusok ismerete előnyt jelent, a feladatok nem intézhetők el pusztán a közismert algoritmusokkal: mindegyikben van néhány csavarás. A megoldás, miután megszületett, már egyszerű: a helyes mintamegoldások tipikusan 1-2 kB-os C programok. Nem is kell bennük bonyolult adatszerkezeteket használni: legtöbbször a statikusan allokált tömb is megteszi, még kupacra és bináris fára is csak ritkán van szükség. A megoldás folyamata hasonló egy matekfeladat megoldásához vagy matematikai tételbizonyításhoz - izgalmas, alkotó szellemi tevékenység. A legtöbb problémára hamar találhatunk megoldást, de ezek a hirtelen előálló algoritmusok általában túl lassúak (exponenciális, de néha még az O(n2,5) is lassú lehet) vagy túl sok memóriát használnak. Az igazi kihívás tehát a gyors (és egyúttal trükkös, szellemes) megoldás felfedezése.

A közép-európai fordulót idén Varsóban rendezték. Mind a szervezésről, mind a szállásról csak elismerően nyilatkozhatunk, a rendezők mindent megtettek a kényelmünkért. A Varsói Egyetemhez közeli Hotel Verában szálltunk meg, kényelmes, tágas, háromfős szobákban. Az étkezésre se lehet panaszunk: bőséges, svédasztalos reggeli várt minket, és napközben is rengeteg szendvicset, üdítőt és gyümölcsöt készítettek ki a versenyzőknek. Az időjárással viszont nem volt szerencsénk: szinte egész nap csípős szél fújt, borús volt az ég, és a hideg utat talált a kabátok résein.

Az ötórás verseny vasárnap zajlott, és még aznap este kihirdették az eredményeket. A verseny ideje alatt minden szobában több segítő állt a rendelkezésünkre, még a nyomtatott lapokért sem magunknak kellett elmennünk. A verseny állását egy jól megírt webes felületen követhettük nyomon, és a megoldásainkat is a weben kellett beadni. A bírálat néhány percen belül megérkezett. A szervezők itt is kitűnő munkát végeztek, a verseny gördülékenyen zajlott. Csak egyetlen feladatban adódott egy - a probléma szempontjából - lényegtelen félreértelmezési lehetőség, végül bármely értelmezés szerinti megoldásokat elfogadták.

Szombaton, a versenyt megelőző napon két érdekes előadást hallgattunk meg (angolul) az egyetem kitűnően felszerelt, új előadótermében: Tényleg szükség van véletlenszámokra? illetve Knots... címmel. Ezután egy rövid próbaversenyt tartottak, melynek során megismerkedtünk a szobával és a számunkra biztosított számítógéppel. Lehetőségünk volt saját config-file-ok létrehozására is, de ezeket este törölték, ezért kinyomtattuk, majd másnap - immár a verseny idejének rovására - begépeltük őket. A hardverrel és az előre telepített Linux rendszerrel csak apróbb kellemetlenségek voltak, de mindenben megfelelt a specifikációnak. Összefoglalásul elmondhatjuk, hogy a szervezők igencsak kitettek magukért mind a verseny ideje alatt, mind előtte.

Szakmai szempontból két problémát találtunk. Az egyik, hogy a megoldásokat elég szerencsétlen opciókkal, optimalizálás nélkül fordították (emiatt például a C++ kódban sebesség-megfontolások miatt több helyen inline függvények helyett a #define-ok sűrűjébe kényszerültünk), valamint az elvileg a versenyzők rendelkezésére bocsátott STL használatát is kerülnünk kellett. Ezt szóvá is tettük, de a kedvünkért már nem változtattak a szabályokon. A másik probléma pedig az volt, hogy nem került sor szakmai kiértékelésre, a helyes megoldások hivatalos (akár vázlatszerű) megbeszélésére. Bár ez kétségkívül időcsúszást okozott volna, még belefért volna a vasárnapi programba. (Az első, BME-n belüli fordulóban egyik probléma sem jelentkezett.)

A versenyen a legjobb teljesítményt a lengyelek nyújtották, az első 6 csapat közül 4 lengyel volt. A magyar csapatok eredményei lentebb láthatók. A BME részéről egy kis szerencsével a 11. és 18. helyezés helyett könnyen lehetett volna kb. 6. és 10., de a lengyelek eredményét - utólag visszagondolva - aligha tudtuk volna megközelíteni. A feladatok nehezek voltak (de nem megoldhatatlanok), ami jónak értékelhető, mert az első néhány helyezett sorrendjét vitathatatlanul meghatározta. Talán lehetett volna kicsit több könnyebb feladatot is berakni, hogy több 4-5 példát megoldó, és kevesebb 2-3 példát megoldó csapat legyen.

Az ACM verseny abban különbözik a valóságban végzett programozói tevékenységtől, hogy a valóságban sokkal kevesebb alkalom nyílik problémamegoldásra, kreatív munkára: helyette csak a meglevő szoftverek hibáit kell foltozgatni, kerülgetni, vagy unalmas, mechanikus adatmanipulácót, adatkonverziót kell végezni. Az ACM ügyesen elkerüli az ilyen helyzeteket, és lehetővé teszi, hogy a versenyzők teljes figyelmüket az algoritmus kiötlésére és csiszolására fordíthassák. Tévedés azonban úgy gondolkodni, hogy az ACM feladatok távol állnak a valóságos problémáktól, és - mivel az életben másra van szükség - fölösleges ilyenfajta programozási játszadozással elütni az időt. Az ACM verseny épphogy hiánypótló az egyetemi évek alatt: számos alapkészséget fejleszt, pallérozza és éberen tartja a gondolkodást. A gyakorlatiasabb megmérettetést kedvelőknek figyelmébe ajánlom a tavalyelőtti, a BME által szervezett 24 órás programozóversenyt, amely érdekes és hasznos átmenet volt a valóság és az ACM között. Reméljük, hogy a sikerén felbuzdulva idén (jövőre) is meg fogják rendezni!

Felmerül a kérdés, hogyan lehet egy ACM-szerű programozási versenyre tanulni, felkészülni. Lexikális ismeretre nincs szükség, mivel bármilyen könyv és írásos anyag használható a verseny alatt. Bár vannak típuspéldák és tipikus trükkök, ezek alkalmazása még nem elég a feladatok megoldásához. Az ACM ebben az értelemben is hasonló a matematikaversenyekhez: a széleskörű rálátás mellett elengedhetetlen a feladatmegoldási készség. Mindezeket csak sok egyéni gyakorlással, gondolkozással lehet megszerezni. Sajnos jelenleg a BME-n nincs olyan tantárgy, ami ebben segítene: a Programozás alapjai és az Algoritmusok elmélete tárgyak idejébe egyszerűen nem fér bele a nehezebb, trükkösebb programok írása. Szívesen vennénk egy új, gyakorlatiasabb választható tárgyat, amelynek fő célja a problémamegoldó-készség feljlesztése és az ACM versenyre való felkészítés lenne.

Ez a verseny a feladatok jellege folytán méltán tekinthető a Nemzetközi Informatikai Diákolimpia folytatásának. Bár a megoldásnál az Algoritmuselmélet tárgy anyagánál mélyebb ismeretekre nincs szükség, egy maxpontos zárthelyi (noha elég ritka) messze nem elég a sikeres szerepléshez, kifinomult gyakorlati érzék is szükséges hozzá. Nem véletlen, hogy az egyetemi válogató első két helyén viszonylag magasan olyan csapatok végeztek, amelyekben egy-egy volt kettős diákolimpikon szerepelt. Talán az a legfontosabb, hogy "sokat látott" emberek legyenek a csapatban. Ennek érzékeltetésére a sikerrel megoldott feladatainkat hozhatjuk fel: két példa (MAYA, CISTERN) nagyon egyszerű volt, megoldása pusztán jól koordinált programozási (kódolási) készséget igényelt (ami tanítható), és reguláris programozási kurzusok keretében elsajátítható. Ezeket egyetemünk mindkét csapata megoldotta. A második csapatunknak ezen kívül a STIRLING példát sikerült megoldania, amelyhez egy ügyes észrevétel, a feladat átfogalamazása volt szükséges (egy megfelelő változócsere). További két feladathoz (MORSE, EXCH) nagyon előremutató ötletük volt, de egy kis csavar hiányzott a befejezéshez. Első csapatunk a MORSE feladattal birkózott meg, mellyel az egyik csapattag már találkozott az 1998-as diákolimpiai válogatóverseny során, és így nem csak a megoldás alapalgoritmusát ismerte, melyet klasszikus (és tanulható) dinamikus programozási technikákkal ki lehet dolgozni a verseny ideje alatt (második csapatunk meg is tette), hanem az ennek hatékony megvalósításához szükséges adatszerkezetet is. A negyedik megoldott példánk a SEGMENTS volt, melyre rajtunk kívül csak a második helyen végzett varsói gárda adott be elfogadott programot (ők is csak kilenc (!) sikertelen próbálkozás után). Tulajdonképpen a szerencsének köszönhető ez a példa, mert az amúgy szuboptimális futási idejű program egy hajszállal átcsúszott az időlimiten. A megoldás négyzetesről majdnem lineárisra vagy legalábbis O(n·logn)-esre gyorsítható lett volna az adatszerkezet bonyolult tömörítésével (kiegyensúgyozott keresőfa, intervallum-fa), de ennek megírására nem maradt időnk. A további feladatokról: egy (GATES) teljesen megközelíthetetlen volt (csak a győztes oldotta meg), egy pedig (ALICE) majdnem reménytelen (csak az első három oldotta meg).

Összefoglalva: a diákolimpiákhoz képest, ahol az alkotó gondolkodás döntő szerepet játszik, itt esetleges ötletek és rutin szükséges - rengeteg megoldott feladat a csapat minél több tagjának háta mögött. Megkockáztatom, hogy bizonyos feladatok megoldása lehetetlen a verseny ideje alatt, ha legalább hasonlót nem oldott meg a versenyző korábbi pályafutása során. Szintén elengedhetetlen feltétel a jó szerepléshez, hogy összeszokott, jó csapattal kell kiállni, előre átgondolt szerepekkel és stratégiával (különösen mivel a megoldások beadásának ideje is számít). Ehhez pedig gyakorló versenyeket kell tartani, valódi versenyfeladatsorokkal.

Köszönettel tartozunk Benedek Balázsnak és Marx Dánielnek (volt eredményes ACM versenyzőknek) és Dr. Szirmay-Kalos Lászlónak, akik lelkesen és profi módon szervezték meg a verseny első, BME-s fordulóját, és utána is sokat segítettek a lengyelországi utunk szervezésében; valamint az Informatikai Központnak a verseny lebonyolításához szükséges termek rendelkezésre bocsátásáért.

Szintén köszönettel tartozunk dr. Rónyai Lajosnak és a Matematikai Intézet Algebra tanszéke munkatársainak, a Villamosmérnöki és Informatikai Karnak, a VIK Hallgatói Képviseletének és a Rektori Hivatalnak a kiutazásunkhoz nélkülözhetetlen anyagi támogatás felkutatásáért és adminisztrálásáért.

A megoldott példák száma:

0 csapat oldott meg 8 példát

2 csapat oldott meg 7 példát

1 csapat oldott meg 6 példát

1 csapat oldott meg 5 példát

7 csapat oldott meg 4 példát

13 csapat oldott meg 3 példát

14 csapat oldott meg 2 példát

14 csapat oldott meg 1 példát

8 csapat oldott meg 0 példát

Összesen 60 csapat Közép-Európából.

A közép-európai fordulón született magyar eredmények:

(4 jó megoldás, 11. helyezés) Pilászy István (BME III. Info.) - jobbra, Rácz Balázs(BME III. Alk. mat.) - balra, Szabó Péter (BME III. Info.) - középen

(3 jó megoldás, 18. helyezés) Golda Bence (BME II. Info.) - balra, Ritter Ádám (BME I. Info.) - középen, Sinóros-Szabó Péter (BME III. Info.) - jobbra

(2 jó megoldás, 25. helyezés) Budapest - ELTE

(2 jó megoldás, 28. helyezés) Budapest - ELTE

(2 jó megoldás, 34. helyezés) Szeged - SZTE

(2 jó megoldás, 38. helyezés) Szeged - SZTE

(1 jó megoldás, 42. helyezés) Debreceni Egyetem

(1 jó megoldás, 47. helyezés) Debreceni Egyetem

Ajánlott URL-ek:

– az idei BME egyetemi (1.) forduló lapja: résztvevők, feladatok, tesztvektorok, mintamegoldások, eredmény

http://www.iit.bme.hu/~szirmay/acm/

– az idei közép-európai (2.) forduló lapja: résztvevők, feladatok, eredmény

http://cepc.mimuw.edu.pl:8002/

– ACM versenyekről általában

http://icpc.baylor.edu/icpc/

– régebbi ACM versenyfeladatok

http://www.acm.inf.ethz.ch/ProblemSetArchive.html

– rengeteg ACM-hez hasonló feldat, webes kiértékeléssel

http://acm.uva.es/problemset/

A beszámolót írta:
Szabó Péter <pts@fazekas.hu>