Provjera injektivnosti i surjektivnosti? (zadatak)

[Gost]

Napisite program koji ucitava prirodne brojeve m, n i niz brojeva f[1],...f[n] iz skupa {1,...,n}. Program povjerava i ispisuje je li funkcija f : {1,...,m} →
{1,...,n} reprezentirana tim nizom injekcija, odnosno surjekcija.

[Gost]

Dokazite da je funkcija f: {1,...n} --> {1,...,n} injekcija ako i samo
ako je surjekcija.

[krcko]

Za prvi zadatak trebas razumjeti kako funkciju izmedju konacnih skupova reprezentiramo nizom (duljine m, a ne n). Nije tesko napisati program koji provjerava injektivnost i surjektivnost po definiciji - prisjeti se definicije i vidjet ces. Ako negdje zapnes, slobodno pitaj.

Drugi zadatak necu pitati na usmenom

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[Gost]

učitaj m,n
za i=1,...,m radi učitaj f[i]
br=1
za i=1,...,n radi
za j=1,...,m radi
ako je i!=f(j) onda br=0
ako je br=0 radi ispiši "funkcija nije surjekcija"
else ispiši "funkcija je surjekcija"

koliko (ni)je ovo dobro?

[krcko]

Prilicno nije dobro - radi ispravno samo za n=1 (tada su sve funkcije surjekcije).

Problem je u ovom. Program prvo stavi br na 1. Za svaki i iz kodomene i za svaki j iz domene stavlja br na nulu ako se j ne preslika u i. Na kraju ce br sigurno biti nula - ne moze se svaki element domene preslikati u svaki element kodomene.

Razmisljaj ovako. Neka br bude brojac elemenata iz kodomene koji su pogodjeni s nekim elementom iz domene. Za svaki i iz kodomene provjeri da li postoji element iz domene koji se u njega preslika. Ako postoji, povecaj br za jedan. Na kraju provjeri da li je br=n.

Efikasniji algoritam prekine potragu cim naleti na prvi element kodomene u koji se nitko ne preslika. Funkciju proglasi surjekcijom samo ako dodje do kraja kodomene.

Jos efikasniji algoritam koristi drugi niz i radi u vremenu O(m) za m>=n i u konstantnom vremenu za m<n.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.