Clasa a 6-a

Programa (neoficială) pentru olimpiada la gimnaziu

1. Recapitulare noțiuni clasa a 5-a

Elemente de matematică necesare pentru înțelegerea materiei informatică la clasa a 5-a.

1.1. Divizibilitate
1.2. Algoritmul lui Euclid
1.3. Ciurul lui Eratostene
1.4. Sortare prin selecție

2. Concepte matematice

2.1. Logaritm 4 subcapitole
2.1.1. Conceptul de logaritm ca invers al ridicării la putere.
2.1.2. Logaritmul în baza doi.
2.1.3. Logaritmul în alte baze.
2.1.4. Operații de bază cu logaritmi -log(a * b), log(a^b).
2.2. Baze de numerație 13 subcapitole5 probleme
2.2.1. Despre sistemul pozițional de reprezentare a numerelor și avantajul acestuia.
2.2.2. log(n) cifre pentru reprezentarea numărului n.
2.2.3. Sistemul pozițional zecimal (indian/arab).
2.2.5. Conversia de la baza 10 la baza 2.
2.2.6. Conversia de la baza 2 la baza 10.
2.2.7. Analogia bazelor - asemănarea cu lucrul cu cifrele unui număr din clasa a cincea.
2.2.8. Sistemul pozițional hexazecimal.
2.2.9. Conversia de la baza 2 la baza 16.
2.2.10. Conversia de la baza 16 la baza 2.
2.2.11. Constante hexazecimale în C/C++.
2.2.12. Alte baze de numerație.
2.2.13. Probleme cu baze de numerație (VArena)
  • Cepe , dată la OJI 2005
  • Tablou, dată la ONI 2008
  • Bază ascunsă
  • Decbin, dată la Campion 2005
  • Paritate, dată la OJI 2007
  • 3. Complexitatea algoritmilor

    3.1. Analiza complexității algoritmilor ca timp și memorie ocupată
    3.2. Notația O mare (big O)
    3.3. Comparația algoritmilor prin prisma complexității timp/memorie.
    3.4. Studiul complexității în problemele rezolvate la lecții și la teme.

    4. Elemente de limbaj de programare

    4.1. Tipuri de date simple în limbajul C / C++4 subcapitole
    4.1.1. Tipul char / unsigned char
    4.1.2. Tipul short / unsigned short
    4.1.3. Tipul long long și unsigned long long
    4.1.4. Tipul float / double / long double
    4.2. Conversii între tipurile de date simple6 subcapitole
    4.2.1. Conversie de întregi de la mic la mare
    4.2.2. Conversie de întregi de la mare la mic
    4.2.3. Conversie de la întreg la double
    4.2.4. Conversie de la double la întreg
    4.2.5. Tipul unei expresii
    4.2.6. Depășiri ale tipului de date
    4.3. Constante C / C++
    4.4. Instrucțiunea switch

    5. Structuri de date

    Structuri clasice de date ce apar în materia de clasa a 6-a.

    5.1. Numere mari8 subcapitole1 problemă
    5.1.1. Reprezentare și afișare
    5.1.2. Adunarea unui număr mic la unul mare
    5.1.3. Scăderea unui număr mic din unul mare long
    5.1.4. Adunarea a două numere mari
    5.1.5. Scăderea a două numere mari
    5.1.6. Înmulțirea unui număr mare cu unul mic
    5.1.7. Împărțirea unui număr mare la unul mic
    5.1.8. Probleme cu numere mari (VArena)
    • Descmult, dată la ONI 2018
    • 5.2. Matrice8 subcapitole3 probleme
      5.2.1. Operațiuni de bază
      5.2.1.1. Citire și afișare
      5.2.1.2. Parcurgeri pe linii, coloane și diagonale
      5.2.1.3. Alte parcurgeri
      5.2.1.4. Transpunere
      5.2.1.5. Căutarea unui element într-o matrice
      5.2.1.6. Căutarea unui vector într-o matrice
      5.2.1.7. Căutarea submatrice într-o matrice
      5.2.1.8. Probleme cu matrice (VArena)
      • Litere1, dată la OJI 2016
      • Figura, dată la ONI 2010
      • Joc1, dată la ONI 2011
      • 5.2.2. Vectori de direcție și bordare
        5.2.2.1. Vectori de direcție

        Sunt vectori preinițializați în care stocăm cele patru sau opt direcții de deplasare în matrice. Scopul este de a simplifica parcurgerile în matrice și a scurta programele.

        5.2.2.2. Bordare

        Se referă la adăugarea unei "borduri" extra unei matrice, bordură ce conține valori speciale. Scopul este de a simplifica testul de ieșire din matrice.

        5.2.2.3. Probleme cu vectori de direcție și bordare (VArena)
        • Robinson, dată la ONI 2005
        • Furnica, dată la OJI 2007
        • Ouă, dată la ONI 2007
        • Medalion, dată la ONI 2012
        • Ținta, dată la ONI 2014
        • 6. Metode și tehnici de programare

          6.1. Simulare 27 probleme

          Simularea se referă la reprezentarea unor aspecte din lumea reală într-un program pe calculator. Programul de simulare îşi propune să calculeze nu numai rezultatele finale, cât şi rezultate de pe parcursul simulării. Deşi simularea variază în funcţie de sistemul simulat, există unele caracteristici comune: sistemul simulat, starea sistemului, tactul simulării, bucla de evenimente, condiția de oprire.

          Probleme cu simulare (VArena)
          • Chip si Dale, dată la Olimpiada locală 2013
          • Magician, dată la Olimpiada locală 2017
          • Ruleta1, dată la OJI 2009
          • Fermier1, dată la OJI 2017
          • Șoricel, dată la OJI 2017
          • Turnuri, dată la OJI 2018
          • Album, dată la OJI 2019
          • Maxim2, dată la OJI 2019
          • Cutii1, dată la ONI 2003
          • Roboți, dată la ONI 2006
          • Cifru1, dată la ONI 2007
          • Minute1, dată la ONI 2007
          • Turn, dată la ONI 2007
          • Melci, dată la ONI 2008
          • Tetris, dată la ONI 2009
          • Joc3, dată la ONI 2011
          • Talent, dată la ONI 2011
          • XY, dată la ONI 2011
          • Remi, dată la ONI 2013
          • Roboțel, dată la ONI 2016
          • Faleza, dată la ONI 2017
          • Pește, dată la ONI 2017
          • Gazon, dată la ONI 2018
          • Maya, dată la ONI 2019
          • Bile2, dată la Campion 2005
          • Albine, dată la Campion 2011
          • Atlantis, dată la Infotehnium 2019
          • 6.2. Memoizare 2 probleme

            Memoizarea este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare.

            Probleme cu memoizare (VArena)
            • Creioane, dată la ONI 2008
            • Bila1, dată la ONI 2010
            • 7. Algoritmi ce apar la concursuri

              Acești algoritmi nu se încadrează într-o clasă anume. De aceea i-am grupat într-o secțiune separată.

              7.1. Exponenț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.

              7.2. Element 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.

              7.3. Interclasare
              7.4 Căutare binară