NAD/RTI Januar 2022

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

Teorija NUM

1. pitanje [5]

Postavka

Izvesti Njutnovu metodu analitički i geometrijski.

2. pitanje [5]

Postavka

Opisati primenu LU dekompozicije za dato L i U.

3. pitanje [5]

Postavka

Definisati ocenu greške interpolacije i odgovarajući dokaz.

4. pitanje [5]

Postavka

Izvesti kompozitno simpsonovo pravilo koristeći osnovno i grešku kompozitnog simpsonovog pravila koristeći osnovnu.

Teorija DIS

1. pitanje

Postavka

Definisati Čerčove teze.

2. pitanje

Postavka

• Objasniti složenost algoritma pomoću Tjuringove mašine.
• Šta je mera složenosti?

3. pitanje

Postavka

Konstruisati algebarske strukture $GF(4)$ i $Z4$

Zadaci DIS

1. zadatak

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).

2. zadatak

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).

3. zadatak

• [5] 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] Dokazati sa su $f: N_0 \rarr N_0$ i $g: N_0 \rarr N_0$ rekurzivne funkcije.

Logika

1. pitanje

Postavka

Stav potpunosti za iskazni račun

2. pitanje

Postavka

Navesti neko formalnu teoriju koja je odlučiva i objasniti zašto je odlučiva.

3. pitanje

Postavka

Prebaciti izraz u preneks normalnu formu pa u skolemovu.

4. pitanje

Postavka

Naći interpretaciju pri kojoj je $(\forall X)(R(x) => Q(x,y))$ tačna i netačna formula.