Descriere - Manual de INFORMATICA pentru clasa a XI-a. Profilul real-intensiv (Pascal si C++)
Materialul este aprobat prin Ordinul MEdC nr. 4446 din 19.06.2006 si trateaza materia in ambele limbaje simultan - Pascal si C++.
Manualul scolar este structurat in noua capitole:
Capitolul 1. Alocarea dinamica a memoriei
Capitolul 2. Liste liniare
Capitolul 3. Metoda Divide et Impera
Capitolul 4. Metoda Backtracking
Capitolul 5. Metoda Greedy
Capitolul 6. Programare dinamica
Capitolul 7. Grafuri neorientate
Capitolul 8. Grafuri orientate
Capitolul 9. Arbori
Anexa 1. Aplicatii practice ale grafurilor
La acest manual a colaborat d-na prof. Rodica Pintea.
Cuprins
Capitolul 1. Alocarea dinamica a memoriei 7
1.1. Generalitati ……… 7
1.2. Variabile de tip pointer…………….............................................................. 8
1.2.1. Variabile de tip pointer in Pascal.........................................................................8
1.2.2. Variabile de tip pointer in C++...........................................................................11
1.3. Alocarea dinamica a memoriei. 14
1.3.1. Alocarea dinamica in Pascal............................................................................. 14
1.3.2. Alocarea dinamica in C++................................................................................. 17
Probleme propuse….. 21
Raspunsuri …………. 22
Capitolul 2. Liste liniare …… 23
2.1. Definitia listelor .. 23
2.2. Liste liniare alocate simplu inlantuit………… 24
2.2.1. Prezentare generala.. 24
2.2.2. Crearea si afisarea listelor………… 24
2.2.3. Operatii asupra unei liste liniare….. 28
2.2.4. Aplicatii ale listelor liniare………….. 34
2.2.4.1. Sortarea prin insertie....................................................................... 34
2.2.4.2. Sortarea topologica......................................................................... 36
2.2.4.3. Operatii cu polinoame..................................................................... 41
2.3. Liste liniare alocate dublu inlantuit………….. 50
2.3.1. Crearea unei liste liniare alocata dublu inlantuit… 50
2.3.2. Adaugarea unei inregistrari la dreapta…..……………................ 51
2.3.3. Adaugarea unei inregistrari la stanga…..…………….………….. 51
2.3.4. Adaugarea unei inregistrari in interiorul listei……..…………….. 51
2.3.5. Stergerea unei inregistrari din interiorul listei……..…………….. 52
2.3.6. Stergerea unei inregistrari la stanga/dreapta listei……….…….. 53
2.3.7. Listarea de la stanga la dreapta listei………..……..…................ 53
2.3.8. Listarea de la dreapta la stanga listei ……..…….. 53
2.4. Stiva implementata ca lista liniara simplu inlantuita………. 55
2.5. Coada implementata ca lista liniara simplu inlantuita…….. 56
Probleme propuse….. 58
Raspunsuri la testele grila………… 63
Capitolul 3. Metoda Divide et Impera…… 64
3.1. Prezentare generala………….. 64
3.2. Aplicatii…………. 64
3.2.1. Valoarea maxima dintr-un vector…. 64
3.2.2. Sortarea prin interclasare..………… 66
3.2.3. Sortarea rapida……… 68
3.2.4. Turnurile din Hanoi…. 71
3.2.5. Problema taieturilor…. 72
4 Cuprins
3.3. Fractali…………. 75
3.3.1. Elemente de grafica… 75
3.3.1.1. Generalitati (varianta Pascal).......................................................... 75
3.3.1.2. Generalitati (varianta C++).............................................................. 77
3.3.1.3. Setarea culorilor si procesul de desenare (Pascal si C++)............ 78
3.3.2. Curba lui Koch pentru un triunghi echilateral..…... 80
3.3.3. Curba lui Koch pentru un patrat..…. 83
3.3.4. Arborele…………..….. 85
Probleme propuse….. 87
Raspunsuri………….. 88
Capitolul 4. Metoda Backtracking………… 90
4.1. Prezentarea metodei…………. 90
4.1.1. Cand se utilizeaza metoda backtracking ?....................................................... 90
4.1.2. Principiul care sta la baza metodei backtracking.. 90
4.1.3. O modalitate de implementare a metodei backtracking. 92
4.1.4. Problema celor n dame……………. 95
4.2. Mai putine linii in programul sursa………….. 98
4.3. Cazul in care se cere o singura solutie. Exemplificare: problema colorarii hartilor…... 101
4.4. Aplicatii ale metodei backtracking in combinatorica……... 103
4.4.1. O generalizare utila.. 103
4.4.2. Produs cartezian…... 104
4.4.3. Generarea tuturor submultimilor unei multimi….. 106
4.4.4. Generarea combinarilor…………... 108
4.4.5. Generarea aranjamentelor……….. 110
4.4.6. Generarea tuturor partitiilor multimii {1, 2, ..., n}…... 112
4.5. Alte tipuri de probleme care se rezolva prin utilizarea metodei backtracking…………. 114
4.5.1. Generalitati…………. 114
4.5.2. Generarea partitiilor unui numar natural…………... 115
4.5.3. Plata unei sume cu bancnote de valori date……… 117
4.5.4. Problema labirintului… 119
4.5.5. Problema bilei………… 122
4.5.6. Saritura calului……….. 124
Probleme propuse… 125
Indicatii…………….. 128
Capitolul 5. Metoda Greedy 129
5.1. Generalitati …... 129
5.2. Probleme pentru care metoda Greedy conduce la solutia optima……... 130
5.2.1. Suma maxima……… 130
5.2.2. Problema planificarii spectacolelor 131
5.2.3. Problema rucsacului (cazul continuu)……..……. 133
5.2.4. O problema de maxim……..……… 135
5.3. Greedy euristic……................................................................................. 137
5.3.1. Plata unei sume intr-un numar minim de bancnote.…………… 137
5.3.2. Saritura calului……….. 139
5.3.3. Problema comis-voiajorului……….....141
Probleme propuse… 142
Raspunsuri / Indicatii…………...... 144
Manual de informatica pentru clasa a XI-a 5
Capitolul 6. Programare dinamica ……… 145
6.1. Generalitati …... 145
6.2. Problema triunghiului………... 147
6.3. Subsir crescator de lungime maxima……... 151
6.4. O problema cu sume……….............................................. 154
6.5. Problema rucsacului (cazul discret)……..… 156
6.6. Distanta Levenshtein……..…. 161
6.7. Inmultirea optima a unui sir de matrice…… 167
6.8. Probleme cu ordinea lexicografica a permutarilor………. 174
6.9. Numarul partitiilor unei multimi cu n elemente…………… 177
Probleme propuse… 180
Indicatii…………….. 183
Capitolul 7. Grafuri neorientate ………… 186
7.1. Introducere …... 186
7.2. Definitia grafului neorientat……………........ 187
7.3. Memorarea grafurilor……………................. 188
7.4. Graf complet…………….............................. 196
7.5. Graf partial, subgraf…................................. 197
7.6. Parcurgerea grafurilor neorientate…................................. 198
7.6.1. Parcurgerea in latime (BF – Bredth First)....................................................... 199
7.6.2. Parcurgerea in adancime (DF – Depth First)................................................. 201
7.6.3. Estimarea timpului necesar parcurgerii grafurilor........................................... 203
7.7. Lanturi…........................................................................... 203
7.8. Graf conex……………................................ 207
7.9. Componente conexe................................... 208
7.10. Cicluri........................................................ 210
7.11. Ciclu eulerian, graf eulerian………..……………........................................................ 212
7.12. Grafuri bipartite………..……………........................................................................... 215
7.13. Grafuri hemiltoniene..……………............................................................................. 217
Probleme propuse… 221
Raspunsuri………… 227
Capitolul 8. Grafuri orientate …………… 230
8.1. Notiunea de graf orientat……….................. 230
8.2. Memorarea grafurilor orientate……………....................... 233
8.3. Graf partial, subgraf…................................. 238
8.4. Parcurgerea grafurilor. Drumuri. Circuite…………................................. 239
8.5. Graf complet si graf turneu…………...................................................... 241
8.6. Graf tare conex. Componente tare conexe.................................................................. 243
8.7. Drumuri de cost minim................................................................................................. 246
8.7.1. Introducere..................................................................................................... 246
8.7.2. Algoritmul Roy-Floyd...................................................................................... 247
8.7.3. Utilizarea algoritmul Roy-Floyd pentru determinarea drumurilor de cost maxim.. 251
8.7.4. Algoritmul lui Dijkstra...................................................................................... 252
Probleme propuse… 256
Raspunsuri………… 260
6 Cuprins
Capitolul 9. Arbori ………… 261
9.1. Notiunea de arbore…….……….................. 261
9.2. Notiunea de arbore partial…....................... 263
9.3. Mai mult despre cicluri…............................. 264
9.4. Arbori cu radacina……….................................................. 267
9.4.1. Notiunea de arbore cu radacina..................................................................... 267
9.4.2. Memorarea arborilor cu radacina prin utilizarea referintelor descendente..... 268
9.4.3. Memorarea arborilor cu radacina prin utilizarea referintelor ascendente....... 268
9.4.4. inaltimea unui arbore cu radacina.................................................................. 270
9.5. Notiunea de padure.......................................................... 272
9.6. Arbori partiali de cost minim…..….......................................................... 275
9.6.1. Algoritmul lui Kruskal...................................................................................... 276
9.6.2. Algoritmul lui Prim.......................................................................................... 280
9.7. Arbori binari…..…................................................................................... 285
9.7.1. Notiunea de arbore binar. Proprietati............................................................. 285
9.7.2. Modalitati de reprezentare a arborilor binari................................................... 287
9.7.3. Modalitati de parcurgere a arborilor binari..................................................... 287
9.7.4. O aplicatie a arborilot binari: forma poloneza a expresiilor............................ 291
9.7.5. Arbore binar complet...................................................................................... 297
9.7.6. MinHeap-uri si MaxHeap-uri. Aplicatii............................................................ 299
9.7.7. Arbori de cautare............................................................................................ 304
Probleme propuse… 310
Raspunsuri………… 315
Anexa 1. Aplicatii practice ale grafurilor 316
Autori: Tudor Sorin, Vlad Tudor (Hutanu)
