Sari la conținut

Clasele XI-XII

Introducere#

Aici găsiți programa claselor XI-XII pentru Olimpiada de Informatică, conform programei create de SEPI în anul școlar 2023-2024, împreună cu locurile de unde puteți învăța aceste conținuturi în arhiva noastră.

Pe lângă conținuturile de mai jos, programa include și materia clasei a zecea, care poate fi accesată în articolul corespunzător.

Observație

Următoarele capitole sunt atât pentru etapa județeană, cât și pentru etapa națională.

Metoda programării dinamice#

  • Programare dinamică pe arbori și grafuri
  • Programare dinamică pe stări exponențiale (bitmask DP) - link articol
  • Terminologie (graf neorientat, graf orientat, lanţ, lanţ elementar, drum, drum elementar, ciclu, ciclu elementar, circuit, circuit elementar, grad, graf parţial, subgraf, conexitate, tare conexitate, arbore, graf ponderat, arbore parţial, arbore parţial de cost minim) - link articol
  • Tipuri speciale de grafuri (graf complet, graf hamiltonian, graf eulerian, graf bipartit, graf turneu) - link articol
  • Reprezentarea grafurilor (matrice de adiacenţă, liste de adiacenţă, lista muchiilor/arcelor) - link articol
  • Grafuri ponderate. Reprezentarea grafurilor ponderate (matricea costurilor, liste de adiacență cu costuri, lista muchiilor/arcelor cu costuri) - link articol
  • Algoritmi de prelucrare a grafurilor
    • Parcurgerea grafurilor în lăţime (BFS), în adâncime (DFS), parcurgerea euleriană
    • Determinarea componentelor conexe ale unui graf neorientat - link articol
    • Determinarea componentelor tare conexe ale unui graf orientat. Algoritmul Kosaraju-Sharir. Graful componentelor tare-conexe - link articol
    • Determinarea matricei lanţurilor/drumurilor (algoritmul Roy-Warshall) - link articol
    • Descompunerea unui graf orientat fără circuite pe niveluri. Sortare topologică - link articol
    • Determinarea drumurilor de cost minim într-un graf. Algoritmul lui Dijkstra, algoritmul Bellman-Ford, algoritmul Roy-Floyd - link articol
    • Determinarea unui lanț/ciclu hamiltonian
    • Determinarea unui lanț/ciclu eulerian

Arbori#

  • Arbori cu rădăcină (definiţie, proprietăţi, reprezentarea arborilor cu rădăcină) - link articol
  • Arbori binari (definiţie, proprietăţi specifice; reprezentarea arborilor binari) - link articol
  • Operații pe structuri de date (interogări, actualizări)
  • Arbore binar complet – definiţie, proprietăţi, reprezentare secvenţială
  • Heap-uri – definiţie, proprietăţi, operaţii specifice (inserare nod, extragerea nodului cu cheie maximă/minimă) (std::priority_queue în C++)
  • Arbore binar de căutare – definiţie, proprietăţi, operaţii specifice (inserare nod, ştergere nod, căutare element) (std::set în C++)
  • Reprezentarea mulțimilor disjuncte. Algoritmii Union-Find - link articol

Observație

Următoarele capitole sunt doar pentru etapa națională

Algoritmi pe grafuri#

  • Determinarea punctelor de articulație, a punților și descompunerea grafurilor în componente biconexe. - link articol
  • Algoritmul lui Dial (optimizarea algoritmului lui Dijkstra pentru grafuri cu ponderi dintr-un interval mic de valori) - link articol

Structuri de date arborescente#

  • Determinarea celui mai apropiat strămoș comun a două noduri dintr-un arbore (lowest common ancestor - LCA) - link articol
  • Determinarea diametrului unui arbore - link articol
  • Arbori indexați binar - link articol
  • Arbori de intervale - link articol