Témy, príklady & stuff

Témy

Jednotlivé hodiny by som rád robil monotématické. Tu sú zhruba témy, ktoré by som rád prebral.

  1. Úvodná prednáška, 9. septembra
    - kto som, čo som ... :-)
    - čo budeme robiť
    - kde sa dajú nájsť príklady: KSP, MOP, PKSP, IPSC, IOI, CEOI, ACM, Univerzitné súťaže, ...
    - aké existujú knižky: Žužliakove skriptá, Mountove skriptá, CLR
    - že treba riešiť matiku/fyziku: MO, KMS, Strom, PraSe, FO, FKS
    - jednoduché greedy algoritmy, časová zložitosť
    - KSP vedci
    - PKSP 10-4-3 Ssssssstttttriiinng, PKSP 10-2-2 Minitónní postupnost, KSP 1324
  2. Stack, fronta, algoritmy na mape 0/1 (floodfill), 23. september
    - prehľadávanie do šírky a do hĺbky
    - či sa dá výjsť z bludiska
    - koľko je ostrovov na mape
    - najkratšia cesta
    - Vyberko 1998
    - IOI 2003, Amazing Robots
    - Turtles CEOI 1997
    - CEOI 1999
    - Villa, Vyberko 1997
  3. Grafy 1: reprezentácie grafov a najkratšie cesty, 30. september
    - Dijkstrov algoritmus
    - Floyd-Warshallov algorimus
    - výberko 2003, syr
    - MOP Nitra, ked som bol 3 tretiak, kamióny
    - Pravdepodobnost, KSP-Z +-15.
    - Poštár zvoní iba raz
  4. Quicksort, Binary search, Medián, 7. obtóber
    - klasika s ropovodom a vrtnými vežami
    - KSP 1713, CEOI +-1999, Vojaci
    - Najdlhšia neklesajúca podpostupnosť, MOP
    - KSP 1413
  5. Geometria 1: Obsah, obvod, ťažisko, príslušnosť do vnútra mnohouholníka, 21. október
    - geometrické vzorce
    - Origami, CPSPC 1999
    - výberko 2003, klinec
    - vyberko 1998, Video Surveilance
    - Dáždovka, výberko 1997
    - KSP 1421 O koláči II
    - výberko 1999, geometrický FW
  6. Backtracking, 28. október
    - rozdiel DFS a Backtracku (Hamiltonovská kružnica)
    - rezanie
    - Hadica Sally
    - Kôň, Výberko 1997
    - Amazing Walks, Výberko 1997
    - Koláč, Výberko 1996
    - 3D veža, KSP
    - Graph Coloring, Výberko 1997
  7. Dynamické programovanie 1, 4. november
    - idea sa bude ilustrovať na príkladoch
    - Santove fľaše
    - MOP Nitra 1997 0/1 Matica
    - Doplnenie na palindróm
    - CEOI 1996, Ships
    - CEOI 1996, Cutting Rectangles
    - kľúče, KSP 14. ročník
  8. Grafy 2: DFS, Topologický sort, Artikulácie, mosty, dvojsúvislosť, 11. november -- MOP
    - KSP 20. ročník, Artikulácie
    - KSP 14. ročník, Mosty
    - Randomly Wired Neural Nets, Výberko 1998
    - Kráľovskí posli, Výberko 1998
  9. Teória hier, 18. november
    - úvod na nejakom trápnom nime
    - vyhrávajúce a prehrávajúce pozície
    - Na kope je N zápaliek (N nepárne). Dvaja hráči striedavo odoberajú z kopy 1, 2 alebo 3 zápalky. Hra sa končí, keď je kopa prázdna. Prehráva hráč s nepárnym počtom zápaliek.
    - PKSP 10-3-2
    - Voracious steve
    - MOP, ked som bol druhák - Košice
    - Výberko 2002 schody
    - KSP 1715 Hra s pešiakmi
    - IOI 2003, Kravy
    - Got root?, IPSC 2003
    - enemkopový nim, CPSPC 1999
    - Conqueror, CEOI 2002
  10. Spájané zoznamy a vyhľadávacie stromy (bez vyvažovania), 25. november
    - ako sa používajú pointre a ako sa alokuje pamať
    - zacyklenosť jednosmerného zoznamu
    - O magickom kruhu
  11. Halda (Heap), 2. december
    - heap a heapsort
    - PKSP 10-4-1 Wagón klád
    - Dijkstrov alg. s heapom
  12. Teória čísel 1: nsd, gcd, prvočísla, 9. december
    - úvod do deliteľnosti a kongrunencií
    - prvočíselný rozklad
    - euklidov algoritmus pre nsd
    - Pikova veta
    - Výberko 1996, Objects
    - Výberko 1997, Circular numbers
    - Diskrétny logaritmus, Rýchlostné
    - IPSC 1999, Faktoriál
    - Antiprime numbers, POI-8-1
  13. Grafy 3: Najlacnejšia kostra a stromy, 13. január
    - Primov algoritmus
    - Kruskalov algoritmus
    - Union/Find set
    - IOI 2003, Trail Maintance
    - KSP Zoči-voči
    - CEOI 1999, Hádanie binárnej postupnosti
    - KSP(-Z) Danova kostra
    - KSP 20. ročník, O telegrafnej sieti
  14. Geometria 2: Konvexný obal a iné, 27. január
    - PKSP 10-3-4 Hic sun leones
    - CEOI 2002 Košice, A highway and the seven dwarfs
    - výberko 2002, omotaj
    - partizánska metóda, quickhull, graham scan, namakaný
    - konvexný obal kruhov
    - zjednotenie obĺžnikov
    - prieniky N úsečiek
  15. Grafy 4: Párovanie v bipartitnom grafe
    - plain verzia
    - veveričky dlaždičkujú, KSP +/- 14. ročník
    - guards CEOI 2002
  16. Dynamické programovanie 2
    - kompresia reťazcov: A4(B)C7(CD)
    - MOP 1999/2000-II-2
  17. Riešenie sústav lineárnych rovníc
    - Jordan, Gauss, (metóda hlavných prvkov)
    - riešenie sústav nad Zp
    - výberko 2002 a 2003
    - niečo nad Z2
  18. Hashovanie
    - idea
    - Research, Vyberko 1997
  19. Grafy 5: Toky
    - Ford fulkersonov algoritmus
    - súvislosť s párovaním v bipartitinom grafe
    - KSP, +/-14. ročník, Rumovody
    - IPSC 2002, futbal
    - ? KSP Rytieri
  20. Kombinatorika
    - permutácia, cykly, inverzie
    - kódovanie a generovanie kombinatorických objektov
    - rátanie počtu kombinatorických objektov: inverzie permutácie, KSP trojuholníky, CPSPC 1999
    - KSP iglu, 00-čísla
    - CEOI 1997, Hexadecimal numbers
    - CEOI 1999
    - CPSPC 1999
    - Výberko 1996, Subsets
    - CEOI 2002, A decorative fence
    - POI-7-2, Automophisms
  21. Rozdeľuj a panuj, nuansy k rekurzii
    - KSP 18?? turnaj
    - najbližšie dva body
    - Mergesort
    - Spatial Structures, Výberko 1998
    - čo je chvostová rekurzia
    - Ako zabezpečiť, že Quicksort bude mať *vždy* najviac logaritmický stack?
    - počet inverzií
  22. Intervalové stromy a prípadne iné extravagatné dátové štruktúry
    - KSP Kuboh
  23. Stringy
    - Fibonacciho slová, Výberko 1998
    - Viruses, POI-7-1

Advanced topics

Tú sú nejaké náročnejšie veci. Tie budem rozprávať, keď nám zvýši čas, prípadne podľa záujmu a úrovne obecenstva.

Rozcvičky

  1. Jedno chýbajúce číslo z množiny {1,2,...,n}.
  2. Záporné mocniny 2
  3. Parita počtu deliteľov
  4. Daný string nad {a,b}. Povedzte a/n, či sa dá rozedliť na dva stringy, tak aby #a v 1. = #b v 2.
  5. 2D veža
  6. Súvislá podpostupnosť s najväčším súčtom
  7. Je daná postupnosť kladných čísel a číslo K. Existuje súvislá podpostupnosť so súčtom K?
  8. Plocha prieniku obdĺžnikov
  9. V poli je dané číslo po cifrách. Vypíšte najmenšie väčšie číslo, ktoré sa skladá z tých istých cifier.
  10. Je dane n,k. Kolko existuje binarnych postupnosti dlzky n, takych ze neobsahuju k rovnakych cifier za sebou?
  11. Je daná permutácia involúcia?
  12. Koľko cyklov má daná permutácia?
  13. Koľko inverzií má permutácia?
  14. Koľko výmen treba na utriedenia permutácie?
  15. Hladné kravy, USACO Fall 2002 Orange
  16. Počet núl na konci faktoriálu
  17. Density map, POI-8-1
  18. Intervals, POI-8-1

Tažké príklady

Tu je pár príkladov do zálohy pre snaživcov, čo nedajú pokoj a stále frflú, že všetko, čo vysvetľujem, je ľahké. (Niektoré z tých príkladov by som nevedel vyriešiť ani ja.) Ak sa vám bude máliť, budete si na internete hľadať a riešiť príklady sami.

  1. Výberko 1999 streda21, Though Nut to Crack
  2. Výberko 1999, Plášť kvádra
  3. Eulerovský ťah, +- 15. ročník KSP-Z
  4. Kódovanie permutácií, kombinácií, CEOI 1997 Novy Sanc
  5. CEOI 1997 Novy Sanc, Hamiltonovská kružnica, +- 15. ročník KSP 1. kolo
  6. CEOI 1998 Vojaci, aj v KSP
  7. KSP Vrabec Čin-Čin, PKSP Rozkopaná ulica
  8. KSP O univerzitnom knihovníkovi
  9. Kandidáti, MOP 1999 II-3
  10. eNeM kopový nim, CPSPC 1999
  11. Kryhy, KSP 1444
  12. 3D krabica a veža
  13. KSP 1531 O zlej kráľovnej
  14. Fibonacciho slová, Výberko 1998
  15. KSP Skáčúci študenti
  16. BW, Výberko 1996
  17. Numbering Path, Výberko 1997
  18. Kráľovskí posli, Výberko 1998
  19. Diskrétny logaritmus, Rýchlostné
  20. Musketeers, POI-6-1
  21. Ghostbusters, CLR
  22. Water, POI-6-3
  23. O čiernych krabičkách, KSP 1935

Iné

© Dávid Pál, 2003/2004