Recapitularea câtorva noțiuni folositoare

1. Conversii între baza 2 și baza 10

1.1 Conversia unui număr din baza 10 în baza 2

1.1.1 Teoria: se realizează prin împărțiri repetate:

Împart numărul dat la 2, cu rest, apoi împart câtul la 2, cu rest, apoi împart noul cât la 2, cu rest ... până ajung la 0.

Citind resturile obținute (care nu pot fi decât 0, sau 1), invers, de la ultimul spre primul, obțin scrierea numărului în baza 2

1.1.2 Exemplu: convertim 82 din baza 10 în baza 2

82:2 = 41 (rest 0)

41:2 = 20 (rest 1)

20:2 = 10 (rest 0)

10:2 = 5 (rest 0)

5:2 = 2 (rest 1)

2:2 = 1 (rest 0)

1:2 = 0 (rest 1) <- Am obținut câtul 0, mă opresc.

Citim resturile invers, de jos în sus: 1 0 1 0 0 1 0. Am obținut cifrele reprezentării lui 82 în baza 2: 82(10) = 1010010(2)

1.2 Conversia unui număr din baza 2 în baza 10

1.2.1 Teoria: se face invers, prin înmulțiri și adunări

Iau prima cifră, o înmulțesc cu 2 și adun următoarea cifră. Înmulțesc rezultatul cu 2 și adun următoarea cifră. Înmulțesc rezultatul cu 2 și adun următoarea cifră etc.

Recunoașteți Schema lui Horner, nu?

1.2.2 Exemplu: convertim 1010010 din baza 2, în baza 10

1x2 + 0 = 2

2x2 + 1 = 5

5x2 + 0 = 10

10x2 + 0 = 20

20x2 + 1 = 41

41x2 + 0 = 82

2. Structuri de date

   Vezi un rezumat folositor aici

1. Coada

Este o structură de tip FIFO (First-In-First-Out = Primul (care) intră (este) primul (care) iese

Ca la o coadă la magazin, primul venit e primul servit

2. Stiva

Este o structură de tip LIFO (Last-In-First-Out = Ultimul (care a) intrat (este) primul (care) iese

Ca la o stivă de cutii, una peste alt. Ultima așezată va fi prima luată

3. Grafuri

   Vezi un rezumat folositor aici

Într-un graf noduri sunt unite prin muchii. Numărul de muchii care leagă un nod este numit gradul acelui nod

Într-un graf neorientat (neordonat), muchiile leagă două noduri fără să conteze ordinea acestora

Un graf este numit complet, dacă fiecare nod al său este legat de fiecare alt nod al său. 

CALCULE:

De exemplu, un graf complet cu două noduri (A,B), are o singură muchie (între ele, AB)

Un graf complet cu trei noduri (A, B, C), are (1) muchia AB + (2) două muchii, care leagă C cu fiecare din cele două anterioare (AC, BC). În total ... 3

Un graf complet cu patru noduri (A, B, C, D) are ... 3 muchii (din graful ABC) + încă 3 (cele care leagă al patrulea nod, D, cu cele trei anterioare). În total (1+2)+3 = 6

Câte muchii va avea un graf complet cu 5 noduri? 1+2+3+4 = 10 ... etc.

CALCULE

pentru fiecare muchie trebuie să existe câte două noduri (la un graf orientat).

Într-un graf orientat (ordonat), muchia merge de la nodul de pornire, la nodul de sosire. Pot exista două muchii între aceleași două noduri

Reprezentăm în programare un graf printr-un vector cu n elemente, pentru n noduri, și o matrice de adiacență, a, pătrată, de n x n, fiecare linie corespunzând unui nod de pornire și fiecare coloană reprezentând un nod de sosire, având ca elemente pe a[i][j] pe 0 (dacă nu există drum de la nodul i la nodul j), respectiv 1 (dacă există un asemenea drum). Evident, pentru un graf neorientat, matricea va fi simetrică (dacă i este legat cu j, automat și j este legat de i).

4. Arbori binari

Dintr-un nod inițial, rădăcină (se reprezintă, de obicei, în partea de sus), repetat apoi pentru fiecare alt nod, pot fi legațe două noduri, unul spre stânga, unul spre dreapta, sau un nod (fie spre stânga, fie spre dreapta), fie niciunul (atunci nodul se numește frunză sau nod terminal)

În imagine, 1 este rădăcina, iar 4, 5, 8, 9 și 7 sunt frunze.  Din 3, 6 este un nod spre stânga, iar 7 este un nod spre dreapta.

La un arbore putem construi

Vectorul TATĂ (pentru fiecare nod, în ordine pentru 1, 2, ... în figură ne oprim la 9 ... se scrie nodul din care provine, sau 0 dacă nu are nici un nod de origine (cazul rădăcinii)

În figură, vectorul TATĂ va fi (pentru 1, punem un 0, nu are tată; pentru 2 punem 1; pentru 3 punem 1; pentru 4 punem 2, pentru 5 punem 2; pentru 6 punem 3; pentru 7 punem 3; pentru 8 punem 6; pentru 9 punem 6. Cum am luat în ordine nodurile, 1,2,3, 4,5,6,7,8,9, nu mai scriem „pentru cine”, ci doar tatăl, direct. Cui corespunde, rezultă din poziție)

TATĂ = [0, 1, 1, 2, 2, 3, 3, 6, 6]

Vectorul STÂNGA va descrie, similar, nodurile descendente, spre stânga (0 dacă nu coboară nimic spre stânga)

STÂNGA = [2, 4, 6, 0, 0, 8, 0, 0, 0]  (primul 2 pentru că din 1, spre stânga, coboară 2; al doilea 4, pentru că din 2, spre stânga coboară 4, al patrulea este 0, pentru că din 4 nu coboară nimic spre stânga etc.)

Vectorul DREAPTA va descrie, similar, nodurile descendente, spre dreapta (0 dacă nu coboară nimic spre dreapta)

DREAPTA = [3, 5, 7, 0, 0, 5, 0, 0, 9]

Se pot formula probleme de genul „știind vectorul stânga și vectorul dreapta, să se reprezinte arborele”. Se rezolvă ca niște puzzle-uri. Se iau perechile, se desenează, apoi se lipesc împreună. Odată desenat, putem găsi rădăcina (cel din care pornesc toate) și frunzele (cele din care nu continuă nimic)

Tehnici (metode) de programare

Fiecare tehnică/metodă de programare este benefică pentru anumite categorii de probleme, niciuna însă nu acoperă toate tipurile de probleme.

Programarea recursivă

O secvență de program se apelează pe ea însăși.

    vezi https://www.youtube.com/watch?v=MVRIt8x2Jco

Backtracking

În rezolvarea unei probleme cu prea multe variante posibile, se micșorează numărul de soluții posibile încercate revenind la o soluție parțială anterioară, atunci când soluția deja în construcție se dovedește nepotrivită. Este o tehnică utilizată, de exemplu, la jocul de șah pe calculator, în loc să încercăm toate mutările posibile, începem o secvență, iar dacă ea se dovedește ineficientă renunțăm la căutarea mai departe, schimbând „înapoi” ceva, în secvența deja începută.

    vezi https://ro.wikipedia.org/wiki/Backtracking

Divide et impera

   vezi https://www.youtube.com/watch?v=LU404wd8pDU

   vezi https://ro.wikipedia.org/wiki/Divide_et_impera_(informatică)

Greedy

   vezi https://www.youtube.com/watch?v=BvWwX5XWaEc

   vezi https://ro.wikipedia.org/wiki/Algoritm_greedy

Limbaj SQL

SQL este un limbaj pentru interogarea structurată a bazelor de date (Structured Query Language)

   vezi https://www.w3schools.com/sql/

vedeți și https://www.w3schools.com/sql/trysql.asp?filename=trysql_select_orderby_desc

vedeți și https://www.w3schools.com/sql/trysql.asp?filename=trysql_select_where_and