Cercul de informatică, liceul Tudor Vianu, clasa XI/XII, anul 2014-2015

From Algopedia
Jump to navigationJump to search

Note de curs

Clasamentul temelor

Planul de bătaie

Din experiența anilor trecuți, iată structura lecțiilor. Nu am stabilit încă o ordine, depinde și ce vreți voi. Suntem ușor împinși de la spate de olimpiada care începe prin februarie. Aș vrea să păstrăm capitolele compacte (toate lecțiile în șir).

Nr. lecții Subiect
Algoritmice
1 unelte pentru calculul complexității (analiză amortizată, the master theorem, arbori de decizie, reduceri)
2 arbori (definiții, proprietăți / reprezentări / parcurgeri, recursivitate / aplicații; expresii aritmetice / structuri de mulțimi disjuncte)
5 grafuri (definiții, reprezentări / BFS, demonstrații / DFS, timpi de vizitare / sortare topologică / arbori parțiali minimi / componente conexe, tare conexe / componente biconexe, puncte de articulație / distanțe minime / cuplaj / flux maxim)
2 programare dinamică
1 automate finite deterministe (posibil și lema de pompare)
3 șiruri de caractere (reprezentări / quicksort ternar / căutări: naivă, Rabin Karp / căutări: cu automate, KMP / trie / arbori de sufixe / șiruri de sufixe)
3 geometrie computațională (matematică / formule simple (apartenență, intersecții, arii) / closest pair / înfășurătoare convexă / sweep line / dualitate / diagrame Voronoi)
1 skip lists (+ un minim de probabilități)
1 tabele hash
1 parcurgeri Euler, LCA + RMQ
1 arbori de intervale
1 probleme de la OJI din anii trecuți
1 probleme de la ONI din anii trecuți
3 subiecte noi (doar n-om fi acoperit tot în 2 ani!)
Non-algoritmice
1 discuție despre facultăți, industrie și mediul academic
1 show-and-tell: povestiți ce programați voi
1 bune obiceiuri în programare
2 GNU/Linux
Opționale
1 arbori cartezieni, treaps, arbori echilibrați (ca principiu)
1 algoritmi randomizați
1 criptografie
2 compresie
1 clasificare bayesiană
1 concurs de programe
1 minimax, alpha-beta, proof number search
1 inginerie, programarea industrială, practici, unelte