Cercul de informatică, liceul Tudor Vianu, clasa XI/XII, anul 2014-2015
From Algopedia
Jump to navigationJump to search
Note de curs
- Clasele 9-12 lecția 1 - 17 sep 2014 -- prezentarea cercului; bune obiceiuri; probleme de logică
- Clasele 11-12 lecția 2 - 24 sep 2014 -- geometrie computațională (formule, probleme, șublerul rotitor)
- Clasele 11-12 lecția 3 - 1 oct 2014 -- geometrie computațională (șublerul rotitor, înfășurătoare convexă)
- Clasele 11-12 lecția 4 - 8 oct 2014 -- discuție despre facultăți; probleme de la OJI din anii trecuți
- Clasele 11-12 lecția 5 - 15 oct 2014 -- probleme de la OJI din anii trecuți
- Clasele 11-12 lecția 6 - 22 oct 2014 -- operații pe biți; codificări
- Clasele 11-12 lecția 7 - 29 oct 2014 -- arbori indexați binar
- Clasele 9-12 lecția 8 - 5 nov 2014 -- obiceiuri bune în programare
- Clasele 9-12 lecția 9 - 12 nov 2014 -- barajul pentru Șumen, seniori, runda a 2-a
- Clasele 11-12 lecția 10 - 19 nov 2014 -- grafuri: introducere, parcurgeri, sortare topologică
- Clasele 11-12 lecția 11 - 26 nov 2014 -- grafuri: componente conexe; componente tare conexe; componente biconexe, puncte de articulație, punți
- Clasele 11-12 lecția 12 - 3 dec 2014 -- grafuri: arbori parțiali minimi; distanțe minime
- Clasele 11-12 lecția 13 - 10 dec 2014 -- arbori: reprezentări, parcurgeri, probleme
- 17 dec 2014 -- serbare de final de an
- Clasele 11-12 lecția 14 - 7 ian 2015 -- trie; arbori de sufixe
- Clasele 11-12 lecția 15 - 14 ian 2015 -- șiruri de sufixe
- Clasele 11-12 lecția 16 - 21 ian 2015 -- skip lists
- Clasele 11-12 lecția 17 - 28 ian 2015 -- probleme de la ONI din anii trecuți
- 4 feb 2015 -- vacanță intersemestrială
- Clasele 11-12 lecția 18 - 11 feb 2015 -- probleme de la ONI din anii trecuți
- Clasele 11-12 lecția 19 - 18 feb 2015 -- arbori de intervale
- Clasele 11-12 lecția 20 - 25 feb 2015 -- discutarea problemelor de la OLI; cicluri euleriene
- Clasele 11-12 lecția 21 - 4 mar 2015 -- fluxuri în grafuri (introducere); întrebări pentru OJI (dacă există)
- Clasele 11-12 lecția 22 - 11 mar 2015 -- discutarea problemelor de la OJI; idei pentru concursul de programe; cuplaje în grafuri bipartite
- Clasele 11-12 lecția 23 - 18 mar 2015 -- fluxuri în grafuri (metoda push-relabel)
- Clasele 11-12 lecția 24 - 25 mar 2015 -- arbori cartezieni; treaps
- Clasele 11-12 lecția 25 - 1 apr 2015 -- premierea concursului de teme; geometrie computațională (sweep line); retușuri pentru ONI
- 8 apr 2015 -- ONI, săptămâna altfel
- 15 apr 2015 -- vacanța de Paște
- Clasele 11-12 lecția 26 - 22 apr 2015 -- discutarea problemelor de la ONI; prezentare de proiect
- Clasele 11-12 lecția 27 - 29 apr 2015 -- GNU/Linux, introducere
- Clasele 11-12 lecția 28 - 6 mai 2015 -- GNU/Linux (servicii, runlevels, porturi, anatomia unei cereri http, anatomia unui e-mail)
- Clasele 11-12 lecția 29 - 13 mai 2015 -- Show and tell
- Clasele 11-12 lecția 30 - 20 mai 2015 -- NP-completitudine; algoritmi de aproximare
- Clasele 9-12 lecția 31 - 27 mai 2015 -- concursul de programe de 4-poker, ora 12:30
- Clasele 11-12 lecția 32 - 3 iun 2015 -- mediul industrial și mediul academic; o zi din viața unui informatician
- Clasele 11-12 lecția 33 - 10 iun 2015 -- puzzle-uri de logică
- Clasele 9-12 lecția 34 - 17 iun 2015 -- petrecere la sfârșit de an
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 |