NAD/K1 2021

Prvi kolokvijum održan je 2.11.2021. i sastojao se od 4 zadatka. Svaki zadatak vredeo je 5 poena.

Zadaci

1. zadatak

Postavka

Tjuringova mašina radi sa azbukom ${0, 1, b}$, gde je b prazan simbol. Neka je n$\isin$$N$ zadat kao niz od $n+1$ jedinica između dva prazna simbola. U sve ostale ćelije je upisan prazan simbol. Neka se glava Tjuringove mašine nalazi nad krajnjim levim znakom zadataog broja. Konstruisati program za Tjuringovu mašinu $f: Q \times X \rarr (Q U {q+,q-}) \times S \times X {+1,-1}$ koji računa $n+(n-1)$

2. zadatak

Postavka

Dokazati da su sume prvih $n$ članova

• aritmetičke progresije sa prvi članom $a_1=1$ i različkom $d=2$
• geometrijske progresije sa prvim članom $a_1=1$ i količnikom $d=2$

3. zadatak

Postavka

Neka su date funkcije $f: N \rarr R$ i $f: N \rarr R$.

• $f(n)=\frac{n^2-1}{2n}$ i $g(n)=2n$;
• $f(n)=3n+\sqrt{n^3}$ i $g(n)=2n^2$;
• $f(n)=n+\log_{2} n$ i $g(n)=n+\sqrt{n}$;

Odrediti koja od relacija $g(n)=O(f(n))$ i/ili $f(n)=O(g(n))$ važi kada $n \rarr \infty$. Odgovor detaljno obrazložiti.

4. zadatak

Postavka

Neka je dato konačno polje $(Z_{11}, +_{11}, \sdot _{11})$, gde je $Z_{11}$ skup ostataka pri deljenju sa 11, a $+_{11}$ i $\sdot _{11}$ redom, sabiranje, odnosno množenje po modulu 11. Izračunati:

• $2 \sdot _{11} (4 +_{11} 6)^{-1}$
• $(3 +_{11} 15)^{11}$

Odrediti sve elemente $x \isin Z_{11}$ za koje važi:

• $2x =x +_{11} x = 0$
• $x^2 = x \sdot _{11} x = 1$
• $x^2 = x \sdot _{11} x = x$