NAD/Januar 2022

Ispit u januarskom ispitnom roku 2022. godine održan je 29. januara.

Teorija iz numeričke matematike

Teorijski deo nije sačuvan.

Diskretna matematika

1. zadatak

• [5 poena] Tjuringova mašina radi sa azbukom ${0, 1, 2, b}$, gde je $b$ prazan simbol. Neka je na tracu Tjuringove mašine prirodan broj zadat svojim ternarnim zapisom između dva prazna simbola, (npr. 5 je u ternarnom zapisu 12, broj 11 kao 102 itd.). 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 U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}$ kojim se zadatom broju dodaje 1 u ternarnom sistemu (u pitanju je sabiranje po modulu 3).
• [5 poena] Tjuringova mašina radi sa azbukom ${0, 1, b}$, gde je b prazan simbol. Neka je $n \isin \mathbb{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 U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}$ koji ispituje da li je broj $n$ deljiv sa 3.

2. zadatak

• [5 poena] Odrediti složenost za ispitivanje funkcije $f: N_0 \rarr N_0$ i $g: N_0 \rarr N_0$ datih sa

  $f(n) = \sum_{k=0}^n \binom{n}{k}$ i $g(n) = \sum_{k=0}^n k \binom{n}{k}$

• [5 poena] Dokazati sa su $f: N_0 \rarr N_0$ i $g: N_0 \rarr N_0$ rekurzivne funkcije.

3. zadatak

[5 poena]

• Definisati postupak mikrorekurzije.
• Ilustrovati postupak mikrorekurzije na primeru funkcije $h: N_0 \rarr N_0$, $h(x) = | \sqrt{x} |$

4. zadatak

[5 poena] Dokazati da se u konačnom polju $GF(p) = (Z_{p}, +_{p}, \sdot _{p}), Zp = {0,1,2....p-1}$, $p$ je prost broj, za proizvoljne elemente $a, b \isin Z_p$ važi $(a +_p b)^p = a^p +_p + b^p$, gde je $a^p = a \sdot _p ... a \sdot _p$ ($p$ puta).

Logika

Zadaci nisu sačuvani.