* 'Implementare':eliminare-gaussiana#implementare
* 'Aplicaţii':eliminare-gaussiana#aplicatii
** 'Problema 1':elimirare-gaussiana#problema-1

** 'Go2':eliminare-gaussiana#go2

* 'Bibliografie':eliminare-gaussiana#bibliografie
h2(#descriere). Descriere

</tex>
Pentru a obţine a doua matrice am înmulţit prima linie cu <tex>\frac{3}{2}</tex> şi am adunat-o la a doua linie, iar apoi am adunat-o la ultima linie(<tex>\frac{2}{2}=1</tex>). Pentru a obţine ultima matrice am înmulţit a doua linie cu <tex>-\frac{2}{\frac{1}{2}}=-4</tex>.

Cum se poate observa şi din exemplu la fiecare pas construim o coloană şi o linie din matricea finală, coloana fiind umplută cu $0$ sub linia fixată. Să presupunem că vrem să transformăm toate elementele de sub linia $i$ aflate pe coloana $j$ în $0$. Pentru fiecare linie $k$ ( $k>i$ ) vom înmulţi linia $i$ cu <tex>-\frac{a_{kj}}{a_ij}</tex> şi o vom aduna la linia $k$ astfel elementul de pe coloana $j$ transformându-se în $0$. În cazul în care <tex>a_{ij}=0</tex> trebuie să căutăm o linie $k$(k > i) astfel încât <tex>a_{kj}\neq 0</tex>. În cazul în care această linie nu există, sistemul nu are soluţie. Aplicând aceşti pasi vom ajunge în final la o matrice triunghiulară din care vom afla necunoscutele.

Cum se poate observa şi din exemplu la fiecare pas construim o coloană şi o linie din matricea finală, coloana fiind umplută cu $0$ sub linia fixată. Să presupunem că vrem să transformăm toate elementele de sub linia $i$ aflate pe coloana $j$ în $0$. Pentru fiecare linie $k$ ( $k>i$ ) vom înmulţi linia $i$ cu <tex>-\frac{a_{kj}}{a_ij}</tex> şi o vom aduna la linia $k$ astfel elementul de pe coloana $j$ transformându-se în $0$. În cazul în care <tex>a_{ij}=0</tex> trebuie să căutăm o linie $k$(k > i) astfel încât <tex>a_{kj}\neq 0</tex>. În cazul în care această linie nu există, sistemul nu are soluţie. Aplicând aceşti pasi vom ajunge în final la o matrice triunghiulară din care vom afla necunoscutele. Complexitatea algoritmului este <tex>O(N^3)</tex>

h2(#implementare). Implementare

h2(#aplicatii). Aplicaţii

h3(#problema-1). Problema 1
Se dă un sistem cu variabile de tip boolean de forma

h2(#problema-1). Problema 1
 
Se dă un sistem cu variabile de tip boolean de forma celui de mai jos. Prin <tex> \oplus </tex> am notat operatorul xor. Să se afle numărul de soluţii care verifică sistemul.

<tex>
\begin{cases}
x_{1} \oplus x_{2} \oplus x_{3} = 1 \\

\end{pmatrix}
</tex>

Prin <tex> \oplus </tex> am notat operatorul xor. Să se afle numărul de soluţii care verifică sistemul.
Această problemă este destul de des întâlnită la concursurile de programare şi pune unele dificultăţi deoarece toate variabilele depind între ele, problema neputând fi împărţită în subprobleme. Pentru a rezolva problema vom asocia sistemului o matrice în care pentru fiecare ecuaţie vom pune pe linia corespunzătoare $1$ pe coloana corespunzătoare variabilelor care apar în ecuaţia curentă, iar pe ultima coloană vom pune rezultatul ecuaţiei.

Această problemă este destul de des întâlnită la concursurile de programare şi pune unele dificultăţi deoarece toate variabilele depind între ele, problema neputând fi împărţită în subprobleme. Pentru a rezolva problema vom asocia sistemului o matrice în care pentru fiecare ecuaţie vom pune pe linia ei şi coloana corespunzătoare variabilelor care apar în ecuaţie valoarea $1$, iar pe ultima coloană vom pune rezultatul ecuaţiei. Matricea obţinută vom încerca să o reducem. Pentru a o reduce vom folosi două operaţii:
<tex>L_{i} \longleftrightarrow L_{j}</tex> : interschimbarea a două linii
<tex>L_{j} \longleftarrow L_{j} \oplus L_{i}</tex> unde <tex>L_{i}</tex> este o linie a matricei.
Având matricea redusă, numărul de soluţii este dat de numărul de coloane, fie el $x$, pe care nu am putut găsi un $1$ cu care să reducem liniile de mai jos. Astfel celelalte variabile vor fi determinate în funcţie de variabila corespunzătoare acestei coloane, sistemul avand soluţie indiferent de valoarea variabilei. În final numărul de soluţii va fi <tex>2^x</tex>
 
h2(#go2). 'Go2':problema/go2 (Algoritmiada 2012 runda 4)
 
Problema ne cere să aflăm numărul de matrici de $N x M$ ( $N,M<101$ ) binare cu unele celule deja completate astfel încât pentru orice căsuţă numărul de vecini(sus, jos, stânga, dreapta) care au valoarea $1$ să fie par.
 
h3. Soluţie
 
O primă soluţie ar fi să asociem fiecărei celule o variabilă, iar pentru fiecare celulă să scriem ecuaţia specifică în final rezultând un sistem cu $MxN$ ecaţii şi $MxN$ necunoscute. Complexitatea este <tex>O((N+M)^3)</tex> şi obţine $50$ de puncte. Pentru a obţine $100$ de puncte este necesar să observăm că dacă am fixat o linie, celelalte vor fi unic determinate în funcţie de aceasta.
 

'The magic matrix':http://community.topcoder.com/stat?c=problem_statement&pm=12495
https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix
'Go2':http://www.infoarena.ro/problema/go2