ATP Tehnici de programare

tehnici_de_programare.c

Tehnici de programare
----------------------


- Backtracking
- Divide Et Impera
- Greedy

Backtracking

Apps:

1) Generare Permutari

permutari de multimea A = {1,2,3}
n = 3 cardinalul
3!

3 factorial

6 solutii



solutia 1: 1 2 3
solutia 2: 1 3 2
solutia 3: 2 1 3
solutia 4: 2 3 1
solutia 5: 3 1 2
solutia 6: 3 2 1

display_solution: 1 2 3
display_solution: 1 3 2
display_solution: 2 1 3
display_solution: 2 3 1
display_solution: 3 1 2
display_solution: 3 2 1

nivelul 3: 2 (level = 3) stack[3] = 2
nivelul 2: 3 (level = 2) stack[2] = 3
nivelul 1: 1 (level = 1) stack[1] = 1

stack[1] = 1
stack[2] = 2
stack[3] = 3


2) Problema colorarii hartilor

         1 tara i are frontiera comuna cu tara j
A[i,j] =
         0 , altfel, adica daca nu are frontiera comuna


tara 1: - culoare 1;
tara 2: - culoare 2;
tara 3: - culoare 1;
tara 4: - culoare 3;
tara 5: - culoare 4;


A[1,2] = 1
A[1,3] = 1
A[1,4] = 1
A[1,5] = 1

A[2,1] = 1
A[2,3] = 1
A[2,4] = 0
A[2,5] = 0

A[3,1] = 1
A[3,2] = 1
A[3,4] = 1
A[3,5] = 0

A[4,1] = 1
A[4,2] = 0
A[4,3] = 1
A[4,5] = 1

A[5,1] = 1
A[5,2] = 0
A[5,3] = 0
A[5,4] = 4

int succ() {

}

int valid() {

    for(int i = 1; i <= level-1; ++i) {

          if(stack[i] == stack[k] && A[i][level] == 1) return 0;
    }

    return 1;
}

int main() {

    for(int i = 1; i <= n; ++i) {

        for(int j = 1; j <= i - 1; ++j) {

           cout<<"A["<<i<<","<<j<<"]=";
           cin>>A[i][j];

           A[i][j] = A[j][i];
        }
    }
}



tara i are culoarea stack[i] (culoarea)

/*
Fiind dată o hartă cu n țări, se cer toate soluțiile de colorare a hărții, utilizand cel
mult patru culori, astfel încât două țări cu frontieră comună să fie colorate cu culori
diferite. Este demonstrat faptul că sunt suficiente numai patru culori pentru ca orice hartă
să poată fi colorată.
*/

Backtracking este o tehnica de programare algoritmica care exploreaza sistematic spatiul solutiilor
prin construirea incrementala a solutiilor candidate si abandonarea celor canditate care nu pot fi completate la solitia valida.



- explorare sistematica - toate solutiile posibile sunt considerate

- constructie incrementala: solutia se construieste element cu element

- eliminarea timpurie a cailor care nu duc la soluti valide

- recursivitate: implementare naturala prin apeluri recursive


algoritmul Backtracking:

input: k - nivelul curent in arborele de solutii

output: toate solutiile valide

begin

   pentru fiecare valoare v din Domeniu(k) executa

      daca Promitator(k, v) atunci

           x[k] = v

           daca k == n atunci
                PRocesareSolutie(v)

          altfel
            Backtracking(k+1)

          end
      end
  end
end


Problema care se pot rezolva cu Backtracking:

- problema comis voiajorului (Genetic Algorithm)

- Generarea functiilor surjective

- Generarea functiilor injective

- Knight's tour

- Reginele pe tabla de sah

- Gasesti o iesire din labirint

- Sudoku

- Ball Problem.

.....
ETC


Divide Et Impera
-----------------------



Divide Et Impera este o paradigma algoritmica care rezolva problemele prin impartirea lor
in subprobleme mai mici de acelasi tip, rezolvarea independenta a acestora, si combinarea rezultatelor


Principiile fundamentale:

- Divizibilitate: problema poate fi impartita in subprobleme similare
- independenta subproblemelor: subproblemele pot fi rezolvate independent
- combinabilitate . Rezultatele pot fi combinate eficient

Max dintr-un sir de numere

sir = {10,3,33,17,117,2,3,45}