НАД/Јануар 2022

Испит у септембарском испитном року одржан је 14. 9. 2022. године.

Теорија НУМ

Није објављено.

ДИС

1. задатак

• [5] Тјурингова машина ради са азбуком ${0, 1, 2, b}$, где је b празан симбол. Нека је на трацу Тјурингове машине природан број задат својим тернарним записом између два празна симбола, (нпр. 5 је у тернарном запису 12, број 11 као 102 итд.). У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину $f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}$ којим се задатом броју додаје 1 у тернарном систему (у питању је сабирање по модулу 3).
• [5] Тјурингова машина ради са азбуком ${0, 1, b}$, где је b празан симбол. Нека је n$\isin$$N$ задат као низ од $n+1$ јединица између два празна симбола. У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину $f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}$ који испитује да ли је број $n$ дељив са 3.

2. задатак

• [5] Одредити сложеност за испитивање функције $f: N_0 \rarr N_0$ и $g: N_0 \rarr N_0$ датих са

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

• [5] Доказати са су $f: N_0 \rarr N_0$ и $g: N_0 \rarr N_0$ рекурзивне функције.

3. задатак [5]

• Дефинисати поступак микрорекурзије.
• Илустровати поступак микрорекурзије на примеру функције $h: N_0 \rarr N_0$, $h(x) = | \sqrt{x} |$

4. задатак [5]

• Доказати да се у коначном пољу $GF(p) = (Z_{p}, +_{p}, \sdot _{p}), Zp = {0,1,2....p-1}$, $p$ је прост број, за произвољне елементе $a, b \isin Z_p$ важи $(a +_p b)^p = a^p +_p + b^p$, где је $a^p = a \sdot _p ... a \sdot _p$ ($p$ пута).

Логика

Задаци нису сачувани.