Materia pentru olimpiada de informatică - tot ce trebuie să știi

Această pagină conține programa olimpiadei de informatică. Deși această listă nu este oficială (deoarece ministerul nu precizează exact ce se poate da la olimpiadă), îți oferim o listă cu posibile subiecte ce se pot da și care s-au dat în anii anteriori, atât pentru gimnaziu (clasele V-VIII) cât și pentru liceu (clasele IX-XI, clasa a XII-a având aceeași materie ca la clasa a XI-a). Această listă se aplică atât pentru olimpiade, cât și pentru majoritatea concursurilor de nivel județean, interjudețean sau național.

Lista aceasta este actualizată regulat, iar la Bibliografie poți găsi mai multe resurse care au ajutat la redactarea listei.

Nu în ultimul rând, pentru fiecare subiect în parte poți găsi resurse care să te ajute să aprofundezi materia. Succes!

Programa olimpiadei la informatică pentru clasa a V-a

Clasa a V-a reprezintă primul an în studiul informaticii și în studiul conceptelor matematice. În acest sens, materia cuprinde noțiuni introductive în informatică, precum și concepte ușoare de logică și matematică.

Citire și afișare de la tastatură și din fișier

• Citirea numerelor de la tastatură;
• Citirea numerelor din fișier (mai multe detalii în această lecție);

Variabile și tipuri de date

• Cunoașterea tipurilor simple de date (mai multe detalii în această lecție):
  • numere întregi (int, long long);
  • numere reale (float, double);
  • caractere (char);
  • boolean (bool);
• Operatori și expresii cu variabile:
  • operații cu numere;
  • atribuiri;
  • concepte precum paritate sau radicalul unui număr;

Alte noțiuni elementare de programare

• Instrucțiunea de decizie if (mai multe detalii în această lecție);
• Instrucțiunile repetitive while, do while și for (mai multe detalii în această lecție);
• Calcule simple ale unor expresii:
  • șiruri, sume și expresii cunoscute (Suma Gauss, Șirul lui Fibonacci, factorialul unui număr);
  • maxime și minime (lecție);

Algoritmi esențiali în programare

• Cifrele unui număr (lecție):
  • extragerea cifrelor unui număr;
  • operații cu cifrele unui număr: suma cifrelor, cifra maximă sau minimă, numărul de cifre, oglinditul unui număr, noțiunea de palindrom;
  • compunerea unui număr cu cifre;
• Divizibilitate (lecție):
  • aflarea divizorilor unui număr;
  • primalitate;
  • factori primi (divizori primi);
  • CMMDC și CMMMC cu ajutorul algoritmului lui Euclid;

Vectori (tablouri unidimensionale)

• Declararea și parcurgerea unui vector (lecție);
• Citirea și afișarea unui vector (lecție);
• Vectori de frecvență și caracteristici (lecție);
• Sortarea vectorilor (lecție);
• Alți vectori utili:
  • Ciurul lui Eratostene;

Matrice (tablouri bidimensionale)

Problemele cu matrice sunt rare și nu conțin noțiuni avansate.

• Declararea și parcurgerea unei matrice (lecție);
• Citirea și afișarea unei matrice (lecție);

Programa olimpiadei de informatică pentru clasa a VI-a

Programa clasei a VI-a cuprinde materia clasei a V-a, la care se adaugă anumite noțiuni în plus.

Materia clasei a V-a

Toate noțiunile cuprinse la materia clasei a V-a.

Cunoașterea noțiunilor intermediare din informatică

• Complexitatea unui algoritm (lecție):
  • analiza unui algoritm din punct de vedere al timpului și al memoriei folosite;
  • notația O mare (big O notation).
• Tipuri de date simple:
  • tipurile învățate și în clasa a V-a: bool, char, int, long long, float, double;
  • variantele unsigned (fără semn) ale anumitor tipuri de date: unsigned int, unsigned long long, unsigned char (lecție);
  • variantele short (scurt) ale anumitor tipuri de date: short int, unsigned short int (lecție);
  • conversii între tipurile de date;

Algoritmi esențiali

• Baze de numerație:
  • baza 2, baza 4, baza 8 și baza 16;
  • convertirea unui număr din baza 10 în baza 2 (lecție) sau în altă bază;
  • convertirea unui număr din baza 2 în baza 10 (lecție);
• Exponențiere rapidă: ridicare la putere în timp logaritmic (lecție);

Vectori

• Căutarea binară (lecție);
• Interclasare (lecție);
• Algoritmi tip Ciurul lui Eratostene (lecție);
• Numere mari (lecție);

Matrice

• Declarare și parcurgere (lecție);
• Citire și afișare (lecție);
• Matrice pătratice: diagonala principală și secundară (lecție);
• Alte parcurgeri asemănătoare;

Subprograme (funcții)

• Funcții care returnează un anumit tip de date (lecție);
• Funcții de tipul void (lecție);

Programa olimpiadei de informatică pentru clasa a VII-a

Programa clasei a VII-a constă în aprofundarea noțiunilor de informatică învățate și abordare anumitor probleme ce țin mai mult de logică și de matematică decât de teorie a informaticii.

Materia claselor a V-a și a VI-a

Trebuie cunoscute noțiunile învățate în clasele anterioare.

Subprograme (funcții)

• Funcții care returnează un anumit tip de date (lecție);
• Funcții de tipul void (lecție);
• Funcții care returnează valori prin parametri (lecție);
• Funcții recursive (lecție);

Structuri de date (tipul struct)

• Declararea tipului struct (lecție);
• Aplicații cu tipul struct;

Șiruri de caractere

• Prelucrarea șirurilor de caractere (lecție);
• Funcții predefinite cu șiruri de caractere (lecție):
  • strcpy, strncpy;
  • strcat, strncat;
  • strcmp;
  • strchr, strstr;
  • strlen;
  • toupper, tolower, isupper, islower;
  • isdigit, isalpha;
  • ale funcții utile;

Algoritmi avansați

Pentru etapele națională ale olimpiadei și ale altor concursuri, pot apărea următorii algoritmi avansați:

• Algoritmul Fill (lecție);
• Algoritmul lui Lee (lecție);
• Divide et Impera (lecție);

Programa olimpiadei de informatică pentru clasa a VIII-a

Programa olimpiadei pentru clasa a VIII-a constă în subiecte mai dificile din punct de vedere al logicii folosite în problemă, însă se folosesc aproape aceleași noțiuni de informatică ca cele învățate în clasele anterioare.

Materia claselor a V-a, a VI-a, a VII-a

Pentru clasa a VIII-a, trebuie știute toate noțiunile învățate anterior.

Geometrie

• Probleme ce țin de geometria în plan:
  • distanțe dintre puncte cu coordonate
  • numărarea
  • coliniaritate

Programa olimpiadei de informatică pentru clasa a IX-a

Materia clasei a IX-a îmbină noțiuni elementare de informatică cu noțiuni avansate ale matematicii. Astfel, deși cunoștințele de informatică sunt puține, problemele pot fi destul de dificile.

Noțiuni elementare ale informaticii

• Ce este un algoritm; complexitatea unui algoritm (lecție);
• Citirea și afișarea din fișiere (lecție);

Variabile și tipuri de date

• Cunoașterea tipurilor simple de date (mai multe detalii în această lecție):
  • numere întregi (int, long long);
  • numere reale (float, double);
  • caractere (char);
  • boolean (bool);
• Operatori și expresii cu variabile:
  • operații cu numere;
  • atribuiri;
  • concepte precum paritate sau radicalul unui număr;

Alte noțiuni elementare de programare

• Instrucțiunea de decizie if (mai multe detalii în această lecție);
• Instrucțiunile repetitive while, do while și for (mai multe detalii în această lecție);
• Calcule simple ale unor expresii:
  • șiruri, sume și expresii cunoscute (Suma Gauss, Șirul lui Fibonacci, factorialul unui număr);
  • maxime și minime (lecție);

Algoritmi esențiali în programare

• Cifrele unui număr (lecție):
  • extragerea cifrelor unui număr;
  • operații cu cifrele unui număr: suma cifrelor, cifra maximă sau minimă, numărul de cifre, oglinditul unui număr, noțiunea de palindrom;
  • compunerea unui număr cu cifre;
• Divizibilitate (lecție):
  • aflarea divizorilor unui număr;
  • primalitate;
  • factori primi (divizori primi);
  • CMMDC și CMMMC cu ajutorul algoritmului lui Euclid;
• Baze de numerație:
  • baza 2, baza 4, baza 8 și baza 16;
  • convertirea unui număr din baza 10 în baza 2 (lecție) sau în altă bază;
  • convertirea unui număr din baza 2 în baza 10 (lecție);
• Exponențiere rapidă: ridicare la putere în timp logaritmic (lecție);

Vectori (tablouri unidimensionale)

• Declararea și parcurgerea unui vector (lecție);
• Citirea și afișarea unui vector (lecție);
• Vectori de frecvență și caracteristici (lecție);
• Sortarea vectorilor (lecție);
• Căutarea binară (lecție);
• Interclasare (lecție);
• Ciurul lui Eratostene (lecție);
• Algoritmi tip Ciurul lui Eratostene (lecție);
• Numere mari (lecție);

Matrice (tablouri bidimensionale)

• Declararea și parcurgerea unei matrice (lecție);
• Citirea și afișarea unei matrice (lecție);
• Matrice pătratice: diagonala principală și secundară (lecție);
• Alte parcurgeri asemănătoare;

Lucrul cu biți

• Biții unui număr (lecție);
• Aplicații cu biții unui număr:
  • operațiile AND, OR, XOR;
  • înmulțirea și împărțirea unui număr cu 2^n;
  • cel mai semnificativ bit;
  • cel mai puțin semnificativ bit;
  • verificarea valorii unui bit pe o anumită poziție;

Algoritmi avansați

• Sume parțiale pe vectori și pe matrice;
• Șmenul lui Mars pe vectori și pe matrice;

Programa olimpiadei de informatică pentru clasa a X-a

Clasa a X-a aduce în prim plan algoritmi noi și noțiuni de recursivitate.

Materia clasei a IX-a

Trebuie cunoscută materia completă a clasei a IX-a, care cuprinde bazele informaticii.

Subprograme (funcții)

• Funcții care returnează un anumit tip de date (lecție);
• Funcții de tipul void (lecție);
• Funcții care returnează valori prin parametri (lecție);
• Funcții recursive (lecție);

Structuri de date (tipul struct)

• Declararea tipului struct (lecție);
• Aplicații cu tipul struct;

Șiruri de caractere

• Prelucrarea șirurilor de caractere (lecție);
• Funcții predefinite cu șiruri de caractere (lecție):
  • strcpy, strncpy;
  • strcat, strncat;
  • strcmp;
  • strchr, strstr;
  • strlen;
  • toupper, tolower, isupper, islower;
  • isdigit, isalpha, isalnum;
  • ale funcții utile;

Algoritmi recursivi

• Funcții recursive (lecție);
• Divide et Impera (lecție);
• Algoritmi de Fill: DFS (lecție);

Structuri de date liniare

• Stiva/stack (lecție);
• Coada/queue (lecție);
• Evaluator de expresii;
• Algoritmul lui Lee: BFS (lecție);

Noțiuni de combinatorică

• Diverse noțiuni de combinatorică (lecție):
  • permutări;
  • aranjamente;
  • combinări;
  • produsul cartezian;
  • submulțimile;

Backtracking

• Ce este backtrackingul (lecție):
  • implementarea permutărilor cu backtracking;
  • implementarea aranjamentelor cu backtracking;
  • implementarea combinărilor cu backtracking;
  • implementarea submulțimilor cu backtracking;

Programa olimpiadei de informatică pentru clasa a XI-a și a XII-a

Ultimii doi ani de informatică studiază aceeași materie. Problemele sunt de logică și se pune accentul pe metode de rezolvare în locul algoritmilor propriu ziși.

Materia claselor a IX-a și a X-a

Trebuie cunoscute noțiunile claselor a IX-a și a X-a în mare măsură.

Backtracking

• Ce este backtrackingul (lecție):
  • implementarea permutărilor cu backtracking;
  • implementarea aranjamentelor cu backtracking;
  • implementarea combinărilor cu backtracking;
  • implementarea submulțimilor cu backtracking;
  • implementarea produsului cartezian cu backtracking;
  • implementarea parițiilor unui număr cu backtracking;
  • alte probleme asemănătoare;
• Backtracking în plan (lecție);
• Alte aplicații cu backtracking;

Metoda programării dinamice

• Ce este programarea dinamică;
• Probleme cu programare dinamică;

Metoda greedy

• Ce este metoda de programare greedy;
• Probleme cu metoda de rezolvare greedy;

Grafuri

• Grafuri neorientate:
  • parcurgeri;
  • componente conexe;
  • algoritmi de drum minim;
• Graful orientate:
  • parcurgeri;
  • sortare topologică;
  • algoritmi de drum minim;
• Arbori:
  • parcurgeri;

Bibliografie sau alte resurse

• Doroș.eu: Programa olimpiadei de informatică
• Nerdvana: Programa olimpiadei pentru gimnaziu și liceu
• Olimpiada.info