Subiectele neoficiale, dar necesare

Programa olimpiadei de informatică
pentru performanță națională.

Subiectele din programa olimpiadei de informatică sunt propuse în baza experienței de predare acumulată. Profesorii care predau astăzi la Nerdvana au redactat-o, după 20 de ani de predare la ciclul gimanzial și liceal.

Așadar, aceasta nu este o listă de subiecte oficială, pe care organizatorii concursurilor au oferit-o. Este, de fapt, o listă creată pe baza problemelor propuse la aceste concursuri. Ordinea subiectelor pe care o sugerăm a fost introdusă pentru a oferi elevilor un parcurs cât mai logic și eficient.

Lista de probleme oferită la fiecare clasă este compusă din problemele pe care noi le lucrăm cu elevii noștri. De aceea, există șansa să nu le regăsiți pe toate cele date în olimpiadele de până acum. Vom actualiza lista pe măsură ce vom analiza și rezolva alte probleme.

Totodată, pentru a păstra lista cât mai simplă, problemele apar doar la capitolul cel mai reprezentativ. Înseamnă că, cel mai probabil, rezolvarea uneia necesită cunoștințele din toate subiectele enunțate anterior.

Primele concepte din programa olimpiadei de informatică

Clasa a 5-a

1Concepte matematice
  • împărțirea cu rest;
  • divizori;
  • cel mai mare divizor comun (CMMDC);
  • ridicarea la putere;
  • radical;
  • numere prime;
  • numere prime între ele;
  • factorial;
  • Fibonacci.
2Introducere în algoritmi
  • despre algoritmi;
  • variabile;
  • operatori;
  • structura liniară;
  • structura alternativă;
  • structura repetitivă de tip WHILE-DO;
  • exerciții cu concepte elementare de calcul: maxim, divizibilitate, paritate, radical.
3Introducere în limbajul C / C++
  • citire;
  • scriere;
  • atribuire;
  • comenzile IF și WHILE.
5Verificare număr palindrom

Probleme date la concursuri:

  1. Palindrom2 (OJI 2016)
6Determinare divizori și verificare număr prim
7Interschimbarea a două variabile
8Algoritmul lui Euclid pentru găsirea CMMDC

Probleme date la concursuri:

  1. Cozonaci (Concursul Grigore Moisil 2011)
9Roluri ale variabilelor: acumulator, contor, steguleț

Aproape toate problemele de la clasa a cincea vor avea variabile cu unul dintre aceste roluri.

11Radical
12Secvențe (șir de numere)
13Incrementare, decrementare, comenzile FOR și DO-WHILE în limbajul C / C++
18Vectori circulari

Probleme date la concursuri:

  1. Culori1 (ONI 2012)
19Vectori preinițializați

Probleme date la concursuri:

  1. Goe (ONI 2011)
  2. Speciale (OJI 2015)
20Ciurul lui Eratostene
21Sortarea prin numărare (Counting Sort)

Probleme date la concursuri:

  1. Șiruri1 (OJI 2004)
22Sortarea prin selecție (Select Sort)

Probleme date la concursuri:

  1. Arme (OJI 2012)
  2. Cartonaș (ONI 2009)
23Lucrul cu unități de măsură ale timpului

Aplicabilitate și concepte intermediare din programa olimpiadei la informatică

Clasa a 6-a

1Recapitulare noțiuni clasa a 5-a
  1. Constante C;
  2. Instrucțiunea SWITCH;
  3. Divizibilitate;
  4. Algoritmul lui Euclid;
  5. Ciurul lui Eratostene;
  6. Interclasare;
  7. Sortare prin selecție;
  8. Căutare binară;
3Concepte matematice
  1. Logaritm (minim logaritm în baza doi);
  2. Baze de numerație ;
4Complexitatea algoritmilor
  1. Analiza complexității algoritmilor ca timp și memorie ocupată;
  2. Notația O mare (big O);
  3. Studiul complexității în problemele rezolvate la lecții și la teme.
5Exponențiere rapidă

Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Scopul este de a ridica un număr la o putere cu un număr cât mai mic de înmulțiri.

Probleme date la concursuri:

  1. Puteri2 (Olimpiada pe școală 2015)
  2. Abc1 (Olimpiada pe școală 2012)
6Element majoritar

Metodă de determinare a unui element dintr-un vector care are cea mai mare frecvență de apariție, cu o rezolvare fără sortare. Acesta se implementează prin simpla parcurgere a vectorului.

Probleme date la concursuri:

  1. Proiecte
  2. Majoritar
7Probleme des întâlnite
  1. Secvență crescătoare prin rotație;
    1. Secvență bitonă
  2. Interpretrarea corectă a unei secvențe de paranteze;
    1. Paranteze1
    2. Încâlceală (Olimpiada pe școală 2012)
  3. Multiplicitatea unui număr în n! (formula lui Legendre).
    1. KFact
    2. Factk (Campion 2004)
    3. Exponent (OJI 2003)
    4. Fact (ONI 2006)
8Tipuri de date simple în limbajul C / C++
  1. Unități de măsură a memoriei calculatorului
  2. Tipul char
  3. Tipul unsigned char
  4. Tipul short
  5. Tipul unsigned short
  6. Tipul int
  7. Tipul unsigned int
  8. Tipurile long și unsigned long
  9. Tipul long long
  10. Tipul unsigned long long
  11. Tipul float
  12. Tipul double
9Conversii între tipurile de date simple
  1. Conversie de întregi de la mic la mare;
  2. Conversie de întregi de la mare la mic;
  3. Conversie de la întreg la double;
  4. Conversie de la double la întreg;
  5. Tipul unei expresii;
  6. Depășiri ale tipului de date.
10Baze de numerație
  1. Sistemul pozițional zecimal;
  2. Sistemul pozițional binar;
  3. Conversia de la baza 10 la baza 2;
  4. Conversia de la baza 2 la baza 10;
  5. Analogia bazelor;
  6. Baza 16;
  7. Conversia de la baza 2 la baza 16;
  8. Conversia de la baza 16 la baza 2;
  9. Constante hexazecimale în C;
  10. Alte baze de numerație.

Probleme date la concursuri:

  1. Bază ascunsă
  2. Decbin (Campion 2005)
  3. Cepe (OJI 2005)
  4. Paritate (OJI 2007)
  5. Tablou (ONI 2008)
11Numere mari
  1. Reprezentare și afișare
  2. Adunarea unui număr mic la unul mare
  3. Scăderea unui număr mic din unul mare
  4. Adunarea a două numere mari
  5. Scăderea a două numere mari
  6. Înmulțirea unui număr mare cu unul mic
  7. Împărțirea unui număr mare la unul mic

Probleme date la concursuri:

  1. ANAF
  2. Cmmp1 (Info Oltenia 2019)
  3. Ech (OJI 2015)
  4. Inventie (ONI 2015)
  5. Axyz (OJI 2016)
  6. Cod (ONI 2016)
12Matrice - operațiuni de bază
  1. Citire și afișare;
  2. Parcurgeri pe linii, coloane și diagonale;
  3. Alte parcurgeri;
  4. Transpunere;
  5. Căutarea unui element într-o matrice;
  6. Căutarea unui vector într-o matrice;
  7. Căutarea submatrice într-o matrice.

Probleme date la concursuri:

  1. Leduri (Campion 2003)
  2. Codificare (Campion 2007)
  3. El (Campion 2010)
  4. Parola1 (Concursul Grigore Moisil 2011)
  5. Magic (Infotehnium 2013)
  6. Pomi (Infotehnium 2019)
  7. Suprapuneri1 (OJI 2007)
  8. Litere1 (OJI 2016)
  9. Figura (ONI 2010)
  10. Joc1 (ONI 2011)
  11. Taburet (ONI 2011)
13Matrice - vectori de direcție și bordare
  1. Vectori de direcție: vectori preinițializați în care stocîm cele patru sau opt direcții de deplasare în matrice. Scopul este de a simplifica și scurta programele;
  2. Bordare: adăugarea unei "borduri" extra unei matrice, bordură ce conține valori speciale. Scopul este de a simplifica testul de ieșire din matrice.

Probleme date la concursuri:

  1. Furnica (OJI 2007)
  2. Robinson (ONI 2005)
  3. Ouă (ONI 2007)
  4. Medalion (ONI 2012)
  5. Ținta (ONI 2014)
15Memoizare

Metoda de a scădea complexitatea unui algoritm folosind o tabelă de stocare a datelor deja calculate, pentru a evita recalcularea lor.

Probleme date la concursuri:

  1. Creioane (ONI 2008)
  2. Bila1 (ONI 2010)

Concepte avansate, strâns legate între ele, din programa olimpiadei la informatică

Clasele a 7-a și a 8-a


Subiectele dintre cele două clase se întrepătrund și este foarte dificil de făcut o diferență și unde ar trebui să facem împărțirea. Vom trata cele două clase în același capitol.

1Concepte matematice
  1. Combinări;
  2. Permutări.
3Funcții în limbajul C/C++
4Măsurarea timpului de execuție a unui program
5Algoritmi esențiali și concepte
  1. Indirectare;
  2. Problema selecției;
  3. Problema numărării în cerc;
  4. Tip de date abstract (TDA);
  5. Arbori de joc și algoritmul minimax.
  6. Interclasarea vectorilor ordonați

Probleme date la concursuri:

  1. Portofel (PACO 2013)
  2. Complot (Olimpiada locală 2015)
6Stive
9Recursivitate
  1. Recursie Top-Down;
  2. Recursie Bottom-Up cu acumulator;
  3. Transformarea recursiei din Top-Down în Bottom-Up.

Probleme date la concursuri:

  1. Optim (ONI 2012)
10Fill recursiv (flood fill)
11Analiză amortizată
13Coadă
15Cozi duble și maximul dintr-o fereastră glisantă

Probleme date la concursuri:

  1. Maxim (ONI 2007)
  2. Cuburi (ONI 2012)
16Algoritmul Union-Find

Algoritm de rezolvarea a problemelor cu mulțimi disjuncte. Ne referim la operațiile de unire a mulțimilor și de căutare al unui element într-o mulțime.

Probleme date la concursuri:

  1. Exclusiv (OSEPI 2021, etapa județeană)
  2. Channels (Shumen 2012 Junior)
18Citire / scriere rapidă (parsing) și analiză sintactică

Diferențe între comenzile de citire și scriere. Metode de îmbunătățire a timpului de citire și scriere.

Probleme date la concursuri:

  1. Expr (OJI 2009)
  2. Agenda (ONI 2014)
  3. Nod (ONI 2014)
  4. Opmult (ONI 2014)
19Probleme de geometrie

Probleme care se bazează pe concepte de matematică, geometrie sau trigonometrie.

Probleme date la concursuri:

  1. Pătrate (Campion 2007)
  2. Puncte (OJI 2013)
  3. Zona (OJI 2013)
  4. Baloane (Olimpiada locală 2012)
  5. Cuburi3 (ONI 2005)
  6. Banda (ONI 2009)
  7. T Drept (ONI 2014)
20Programare dinamică
  1. Metoda greedy;
  2. Subsecvența crescătoare de lungime maximă;
  3. Subșirul de sumă maximală;
  4. Subsecvența comună maximală a două șiruri;
  5. Distanța edit (Levenshtein);
  6. Numărare optime prin programare dinamică.

Probleme date la concursuri:

  1. Tren (Campion 2004)
  2. Sir1 (Cupa Mărțișor 2013)
  3. Lăcusta (OJI 2005)
  4. Cub (Olimpiada locală 2012)
  5. Șiruri 2 (OMI 2010)
  6. Meteor (ONI 2004)
  7. Neo (ONI 2004)
  8. Rafturi (ONI 2009)
  9. Char (ONI 2010)
  10. Flori2 (ONI 2010)
  11. Raze (ONI 2010)
  12. Simetric (ONI 2010)
  13. Joc6 (ONI 2011)
  14. Poteci (ONI 2011)
  15. Optim (ONI 2012)
  16. Zmax (ONI 2013)
  17. Placa (ONI 2014)
  18. Faleza (ONI 2017)
  19. Points2 (Shumen 2010 Junior)
  20. Balance (Shumen 2012 Juniori)

Concepte intermediare din programa olimpiadei la informatică

Clasele a 9-a


Programa este în lucru. Aceasta este lista subiectelor abordate la cursurile IQ Academy, la clasa a 9-a, în anul școlar 2020-2021. Aceste subiecte vor face tema testului de selecție pentru cercul IQ Academy adresat clasei a 10-a în anul școlar 2021-2022.

1Generalități
  1. Complexități de timp și spațiu;
  2. Memoria pe stivă și memoria globală;
  3. Convertire tipuri de date;
2Divizibilitate și primalitate
  1. Suma și numărul divizorilor;
  2. Descompunere în factori primi;
  3. Algoritmul lui Euclid;
  4. Ciurul lui Eratostene.
3Vectori caracteristici (de frecvență)
  1. Problema elementului majoritar;
  2. Hashing.
4Baze de numerație
  1. Operații pe biți;
  2. Submulțimile unei mulțimi;
  3. Căutare binară;
  4. Exponențiere rapidă;
  5. Invers modular.
5Recursivitate
  1. Divide et impera;
  2. Mergesort;
  3. Quicksort;
  4. Statistici de ordine.
6Structuri de date
  1. Listă;
  2. Stivă;
  3. Coadă;
  4. Coadă cu două capete (deque);
  5. Implementări folosind struct.
7Alte tipuri de sortare
  1. Bucketsort;
  2. Radixsort.
8Parcurgeri în matrice
  1. Flood Fill (DFS);
  2. Algoritmul lui Lee (BFS).
9Backtracking
  1. Combinări;
  2. Permutări;
  3. Generare divizori prin backtracking.
10Greedy
  1. Problema rucsacului fracționar;
  2. Problema spectacolelor.
11Programare dinamică și calcul tabelar
  1. Subsecvență de sumă maximă;
  2. Subșir crescător maximal;
  3. Subsecvență comună maximală;
  4. Subșir comun maximal;
  5. Sume parțiale;
  6. “Șmenul lui Mars” (Difference Arrays) 1D & 2D;
  7. Problema rucsacului discret.
12Lucrul cu numere reale
  1. Probleme de precizie;
  2. Căutare binară pe numere reale.

Dacă îți dorești să înveți alături de profesorii care au conceput programa olimpiadei de informatică, verifică programul cursurilor de informatică Nerdvana și începe să te pregătești!