Backtracking

Funcții Injective & Surjective

Posted by Feroviarul on

Funcții injective. Aspecte teoretice:

Fie A si B doua mulțimi nevide.

Definiție: O funcție f:A\rightarrow B se numește injectivă (injecție) daca \forall x_{1}, x_{2}\in A, x_{1}\neq x_{2} avem f\left(x_{1}\right)\neq f\left(x_{2}\right)

Observație: Faptul ca f este injectivă mai poate fi exprimat și astfel:

1) daca x_{1} si x_{2} sunt elemente oarecare din A cu proprietatea ca f\left(x_{1}\right)=f\left(x_{2}\right), atunci rezultă că x_{1}=x_{2}

2) Funcția f:A\rightarrow B este injectivă dacă \forall y\in B ecuația f\left(x\right)=y are cel mult o soluție x\in A

functie injectiva exemplu

Problemă:

Să se afișeze toate funcțiile injective f: A->B, unde A și B sunt două mulțimi cu m
respectiv n elemente. Se va afișa tabelul de variație al funcției.

pascal logo
Cod Sursa Pascal

 

program GenerareaFunctiilorInjective;
uses Crt;
type vector = array[1..10] of integer;
var NrSol: Integer;
procedure Scrie(m: integer; x: vector);
var i: Integer;
begin
Inc(NrSol);
WriteLn(‘Solutia nr. ‘,NrSol);
Write(‘ x |’);
for i := 1 to m do Write(i:3);
WriteLn; Write(‘—-|’);
for i:=1 to m do Write(‘—‘);
WriteLn; Write(‘f(x)|’);
for i := 1 to m do Write(x[i]:3);
WriteLn; ReadLn
end;
function PotContinua(x: vector; k: integer): Boolean;
var atac: Boolean; i: Integer;
begin
atac := false; i := 1;
while (i < k) and (not atac) do
if x[i] = x[k] then atac := True
else i := i+1;
PotContinua := not atac
end;
procedure FunctiiInjective(m, n: Integer; var x: vector);
var k: Integer; cont: Boolean;
begin
k := 1; x[k] := 0;

while k > 0 do
begin
cont := False;
while (x[k] < n) and (not cont) do
begin
x[k] := x[k] + 1;
if PotContinua(x,k) then cont := True
end;
if not cont then k := k – 1
else
if k = m then Scrie(m,x)
else
begin
k := k + 1; x[k] := 0
end
end
end;
var x: vector;
m,n: integer;
begin
ClrScr;
WriteLn(‘ Generarea functiilor injective ‘);
WriteLn(‘ ****************************** ‘);
WriteLn; NrSol:=0;
Write(‘Dati cardinalul multimii A: ‘); ReadLn(m);
Write(‘Dati cardinalul multimii B: ‘); ReadLn(n);
FunctiiInjective(m,n,x)
end.

Rezultat:

functii injective rezultat

Funcții surjective. Aspecte teoretice:

Fie A si B două mulțimi nevide.

Def: O funcție f:A\rightarrow B este o funcție surjectiva (surjecție) daca pentru oricare y\in B exista cel puțin un x\in A astfel încât f\left(x\right)=y

Observație: O funcție f:A\rightarrow B este o funcție surjectivă, daca \forall y\in B ecuația f\left(x\right)=y are cel puțin o soluție x\in A.

functie surjectiva exemplu

Problemă:

Să se afișeze toate funcțiile surjective f: A->B, unde A și B sunt două mulțimi cu m
respectiv n elemente. Se va afișa tabelul de variație al funcției.

program GenerareaFunctiilorSurjective;
uses Crt;
type vector = array[1..10] of Integer;
var NrSol: Integer;
x: vector;
n,m,k,i: Integer;
procedure Scrie;
begin
Inc(NrSol);
WriteLn(‘Solutia nr. ‘,NrSol);
Write(‘ x |’);
for i := 1 to m do
Write(i:3);
WriteLn;
Write(‘—-|’);
for i:=1 to m do
Write(‘—‘);
WriteLn;
Write(‘f(x)|’);
for i := 1 to m do
Write(x[i]:3);
WriteLn;
if ReadKey=#27 then Halt
end;
function PotContinua: Boolean;
var codomeniu: set of Byte;
begin
if k<m then PotContinua:=True
else
begin
codomeniu:=[];
for i:=1 to m do
codomeniu:=codomeniu+[x[i]];
PotContinua:=codomeniu=[1..n]
end;
end;
procedure FunctiiSurjective;
var cont: Boolean;
begin
k := 1; x[k] := 0;
while k > 0 do
begin
cont := False;
while (x[k] < n) and (not cont) do
begin
x[k] := x[k] + 1;
if PotContinua then cont := True
end;
if not cont then k := k – 1
else
if k = m then
Scrie
else
begin
k := k + 1;
x[k] := 0
end
end
end;
begin
ClrScr;
WriteLn(‘ Generarea functiilor surjective ‘);
WriteLn(‘ ******************************* ‘);
WriteLn; NrSol:=0;
Write(‘Dati cardinalul multimii A: ‘); ReadLn(m);
Write(‘Dati cardinalul multimii B: ‘); ReadLn(n);
FunctiiSurjective
end.

Rezultat:

functii surjective rezultat

 

Leave a comment