NAD/RTI Januar 2022

Ovaj rok nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

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

Teorija iz numeričke matematike

1. pitanje

Postavka

[5 poena] Izvesti Njutnovu metodu analitički i geometrijski.

2. pitanje

Postavka

[5 poena] Opisati primenu LU dekompozicije za dato L i U.

3. pitanje

Postavka

[5 poena] Definisati ocenu greške interpolacije i odgovarajući dokaz.

4. pitanje

Postavka

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

Teorija iz diskretne matematike

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 iz diskretne matematike

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

Logika

1. pitanje

Postavka

Stav potpunosti za iskazni račun.

2. pitanje

Postavka

Navesti neku 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.