Clasa a 7-a și a 8-a

Se referă la: matematica permutărilor.

1.1.1. Funcția permutare

1.1.2. Ciclurile permutărilor

1.1.3. Numerotarea permutărilor

1.1.4. Permutări cu repetiție

1.1.5 Algoritmul next-permutation

1.1.6. Probleme în care apare conceptul de permutare (fără a necesita generarea tuturor permutărilor) (VArena):

• sport, dată la ONI 2011 clasa a 8-a
• puzzle, dată la ONI 2008 baraj gimnaziu
• decod, dată la ONI 2009 baraj gimnaziu
• nrcuv, dată la ONI 2009 baraj gimnaziu (necesită numere mari)
• taburet, data la ONI 2011 baraj gimnaziu

Se referă la: matematica combinărilor, binomul lui Newton, triunghiul lui Pascal.

Concept asemănător permutărilor.

Se referă la: conceptul de element al unui vector care conține un indice către același vector. Este util pentru înțelegerea listelor și a altor structuri cu legături.

Se referă la: puncte și drepte în plan, proiecții în spațiu.

Probleme în care apare geometrie (VArena):

Se referă la: calculul global al sumei operațiilor unui algoritm, în care deși oricare din operații poate fi scumpă, media lor este mai puțin scumpă.

2.1.1. Incrementare contor binar

2.1.2. Permutări eficiente folosind o listă: necesită liste

2.1.3. Poziția primului element mai mare la stânga fiecărui element într-un vector

2.1.4. Problema bibliotecarului (coada implementată cu două stive)

Probleme cu analiză amortizată (VArena):

3.1.1. Când folosim funcții?

3.1.2. Definiție, sintaxă, apel, valoare returnată

3.1.3. Transmiterea parametrilor prin valoare și referință

3.1.4. Transmiterea corectă a vectorilor ca parametri

3.1.5. Reguli de scoping (vizibilitatea variabilelor în funcții)

3.1.6. Cum denumim funcțiile?

3.1.7. Funcțiile și programarea structurată

4.2.1. Probleme cu stive (VArena):

4.3.1 Probleme cu liste (VArena):

• la coadă
• arc1, dată la OJI 2015 clasa a 9-a (modificată)

4.3.2 Probleme cu vector de liste (VArena):

• bile1, dată la ONI 2012 clasa a 7-a
• zigzag, dată la ONI 2012 clasa a 7-a
• onigim, dată la ONI 2013 clasa a 5-a (modificată)
• macheta, dată la ONI 2011 clasa a 8-a
• criptic
• run, dată la concurs Shumen juniori 2013

4.4.1. Probleme cu tipul coadă (VArena):

• maxim2, dată la ONI 2019 clasa a 6-a (punctul 2)
• livada, dată la cercul de informatică Vianu 2014 clasa a 9-a

4.4.2. Probleme cu tipul coadă (PBInfo):

• vase
• fractii3
• expand

4.4.3. Algoritmul lui Lee (BFS în matrice)

Este materie extra, care se poate da la baraj gimnaziu.

4.4.4. Probleme cu algoritmul lui Lee (VArena):

• alee, dată la OJI 2007 clasa a 10-a
• insule, dată la OJI 2009 clasa a 10-a
• miting, dată la OJI 2016 clasa a 10-a (grea)
• inginer, dată la .campion 2008
• rj, dată la OJI 2004 clasa a 10-a

4.4.5. Probleme cu algoritmul lui Lee (InfoArena):

• muzeu
• traseu3, dată la ONI 2014, clasa a 9-a
• gheizere, dată la ONI 2012, clasa a 10-a
• ai, dată la OJI 2011, clasa a 10-a

5.1.1. Santinele

5.1.2. Bordare

5.1.3. Este un caracter literă?

5.1.4. Ciurul lui Eratostene

5.1.5. Sume parțiale pe vectori (1D) și matrice (2D)

5.1.6. Popcount (numărul de biți 1 dintr-un întreg)

5.1.7. Sume de intervale (șmenul lui Mars)

5.1.8. Probleme cu precalculare (VArena):

5.2.1 Recursivitate top-down

5.2.2 Recursivitate bottom-up

5.2.3 Transformarea recursivității din top-down în bottom-up

5.2.4 Permutări, combinări, aranjamente

5.2.5 Flood fill

5.2.6 Probleme cu recursivitate (VArena):

• combinări
• v, dată la OJI 2004 clasa a 7-a
• permutări1
• aranjamente
• optim, dată la ONI 2012 clasa a 8-a.
• 2numere, dată la ONI 2008 baraj gimnaziu.
  Necesită generare de permutări.
• balance, dată la Shumen 2012 juniori

5.2.7 Probleme cu flood fill (VArena):

• oraș, dată la .campion 2011
• enclave
• ozn, dată la barajul pentru Shumen din Tudor Vianu anul 2014, juniori
• drenaj, dată la OMI Iasi 2011

Revizitare din clasa a șasea. Folosirea memoizării în combinație cu recursivitatea pentru reducerea complexității algoritmilor.

Constă în împărțirea problemei în subprobleme mai mici, disjuncte.

5.4.1. Decrease and conquer (divide et impera degenerat)

Se folosește atunci când problema se reduce la o singură subproblemă mai mică.

5.4.2. Exemple de decrease and conquer:

• Algoritmul lui Euclid
• Căutare binară
• Algoritmul de selecție (al k-lea element în vector dacă acesta ar fi sortat)

5.4.3. Probleme cu decrease and conquer (VArena):

• zparcurgere
• tabela
• antitir

5.4.4. Exemple de probleme clasice de divide et impera:

• Turnurile din Hanoi
• Mergesort
• Quicksort

5.4.5. Probleme cu divide et impera (VArena):

• latin, dată la cercul de informatică Vianu, gimnaziu 2013
• pav, dată la Lot IS 2008
• forma, dată la olimpiada pe sector 2012, clasa a 8-a
• hanoi1
• puzzle2, dată la Infogim 2019 runda 1 clasa a 6-a

Găsirea optimului prin împărțirea problemei în subprobleme mai mici, nedisjuncte.

5.5.1 Exemple de probleme clasice de programare dinamică

• Subsecvența crescătoare de lungime maximă
• Subșirul de sumă maximală
• Subșirul comun maximal al două șiruri
• Subsecvența comună maximală a două șiruri
• Problema rucsacului
• Distanța edit (Levenshtein)
• Înmulțirea optimală a unui șir de matrice

5.5.2 Probleme cu programare dinamică (VArena):

• faleza, dată la ONI 2017 clasa a 6-a (are soluție fără PD)
• poteci, dată la ONI 2011 baraj gimnaziu
• optim, dată la ONI 2012 clasa a 8-a (are soluție fără PD)
• joc6, dată la ONI 2011 baraj gimnaziu
• zmax, dată la ONI 2013 baraj gimnaziu
• flori2, dată la ONI 2010 baraj gimnaziu
• neo, dată la ONI 2004 clasa a 7-a
• rafturi, dată la ONI 2009 clasa a 9-a
• siruri2, dată la OMI Iasi 2010
• cub, dată la Olimpiada locala 2010, clasele 11-12
• lacusta, dată la OJI 2005 clasa a 10-a
• sir1, dată la Cupa Martisor 2013
• tren, dată la .campion 2004

5.5.3 Numărare optime prin programare dinamică (câte soluții optime avem?)

5.5.4 Probleme suprapuse (numărare soluții ce nu necesită optim)

5.5.5 Probleme cu probleme suprapuse (numărare soluții ce nu necesită optim) (VArena):

• rucsac
• cifreco, dată la ONI 2012 baraj gimnaziu
• sir2, dată la olimpiada locală 2014

Necesită cunoștințe bune de recursivitate. Deși este subiect avansat, o introducere în domeniu este foarte utilă, deoarece apare des la concursuri în forme mai ușoare sau mai grele.

5.6.1. Gramatici (în special LL(1))

5.6.2. Analizorul recursiv cu proceduri

5.6.3. Dincolo de concurs: analiza corectitudinii unei fraze de la intrare

5.6.4. Exemple clasice de analiză sintactică

• Evaluarea unei expresii aritmetice
• Analiza unui șir de paranteze de diverse tipuri
• Notația postfix a unei expresii

5.6.5. Probleme cu analiză sintactică (VArena):

• adun, dată la ONI 2006 clasa a 8-a
• agenda, dată la ONI 2014 baraj gimnaziu
• datorii, dată la OJI 2020 clasa a 8-a
• gcl, dată la ONI 2018 baraj gimnaziu
• incalceala, dată la Olimpiada pe Scoala 2012, clasa a 7-a
• opmult, dată la ONI 2010 baraj gimnaziu
• pom, dată la Baraj Sumen 2013 juniori runda 2
• scădere , dată la ONI 2015 clasa a 7-a
• text , dată la OJI 2003 clasa a 9-a

Este un algoritm pentru rezolvarea problemelor în care reunim mulțimile unor membri dați. Necesită analiză amortizată

6.1.1. Probleme cu Union-Find (VArena):

Dată o submulţime de N intervale [ai, bi] să se găsească o submulţime maximală a acestei mulţimi care conţine doar intervale disjuncte (neintersectante).

6.2.1. Probleme cu intervale neintersectante (VArena):

Cum știm dacă programul scris de noi se încadrează în timp?

7.1.1. Măsurarea folosind 'gettimeofday()'

7.1.2. Executarea a unui program până la expirarea timpului alocat

7.1.3. Principii de măsurare

7.1.4. Efectul observatorului

Tehnică de a citi sau scrie numere din/în fișiere mult mai rapidă decât fscanf/stream-uri.

7.2.1. Folosind fgetc/fputc

7.2.2. Folosind fread/fwrite