ACM programozási versenyre felkészítő szakkör, 2010

A foglalkozások helyszíne és időpontja: IB 134., péntek 14:15 (BME I. épület, SZIT tanszéken belül).

A válogató verseny előtt – és igény szerint esetleg utána is – felkészítő, feladatmegoldó foglalkozásokat tartunk heti egy alkalommal. Régebbi feladatsorok segítségével áttekintjük a fontosabb feladattípusokat, és praktikus tanácsokat adunk a versennyel, programozással kapcsolatban.

Tematika

Elképzeléseink szerint a következő témaköröket fogjuk több-kevesebb részletességgel áttekinteni:

  • gráfreprezentációk és alapvető gráfalgoritmusok (Dijkstra, Ford, BFS, DFS, DAG)
  • dinamikus programozás
  • mintaillesztés
  • szövegkeresés
  • geometriai problémák
  • backtrack

A részvétel jelentkezést nem igényel, a félév során bármikor lehet csatlakozni, mindenkit szeretettel várunk. Az aktuális információkról ezen a honlapon, illetve acm-valogato levelezőlistán keresztül lehet tájékozódni.

0. alkalom Időpont-megbeszélés szept. 10., 14:15-16:00

Ezen a héten még csak a foglalkozások időpontját beszéltük meg, nem oldottunk meg feladatokat.

Volt viszont házi feladat: Easy Climb.

1. alkalom Bemelegítés: gondolkodtató, de röviden megoldható feladatok szept. 17., 14:15-16:00

A következő feladatokat oldottuk meg:

Szó volt még az C++ STL (Standard Template Library) könyvtáráról, mely rendkívül hasznos adatszerkezetek és algoritmusok implementációit tartalmazza.

Emellett javasoltuk még ezeket a könyveket és on-line versenyeket. Utóbbiak mindegyike lehetőséget ad a gyakorlásra is, a beküldött forráskódot tesztesetek hadára kiértékeli és beszámol a futtatás sikeréről/sikertelenségéről.

A házi feladat végiggondolni, hogy amortizált időben miért O(1) komplexitású az std::vector-ba egy elem beszúrása, illetve gondolkodni ezen a feladaton: Lucky Cities.

2. alkalom Dinamikus programozás, kétszeresen összefüggő komponensek szept. 24., 14:15-16:00

Nehézségi és szépségi fokuk miatt házi feladat maradt mind a Number Game, mind a Hot Dog. Ezeket szépen elosztva a következő alkalmak során fogjuk átbeszélni.

3. alkalom Játékelmélet, minimális teljes párosítás kétféleképp, DP okt. 1., 14:15-16:00

4. alkalom Eldöntési problémává alakítás, és két nehezebb feladat okt. 8., 14:15-16:00

A következő feladatokat oldottuk meg:

A Bribes maradt házi feladatnak.

5. alkalom Dinamikus programozás-szeánsz (friss!) okt. 15., 14:15-16:00

Ezen az alkalmon megbeszéltünk minden hátramaradt feladatot, nincs házi feladat sem, a következő órán vadonat új feladatcsokorral várunk mindenkit!

6. alkalom okt. 22., 14:15-16:00

Hamarosan!

7. alkalom Őszi szünetre való tekintettel elmarad! okt. 29., 14:15-16:00

Figyelem! Ez az alkalom a legtöbb résztvevőnek aktuális őszi szünetre való tekintettel elmarad!

8. alkalom nov. 5., 14:15-16:00

Hamarosan!

VERSENY! Országos válogató nov 7., 09:00-15:00

A jelentkezéssel, illetve magával a versennyel kapcsolatos információkat lásd a főoldal aktuális pontja alatt!

9. alkalom nov. 12., 14:15-16:00

Hamarosan!

VERSENY! Közép-európai válogató nov. 19–21.

A helyszín: Wrocław, Lengyelország.

VERSENY! Nemzetközi döntő márc., 2011.

A helyszín: Kairó, Egyiptom.