НАД/РТИ Јануар 2022

Испит у јануарском испитном року одржан је 29. 1. 2022. године.

Теорија НУМ

1. питање [5]

Поставка

Извести Њутнову методу аналитички и геометријски.

2. питање [5]

Поставка

Описати примену ЛУ декомпозиције за дато Л и У.

3. питање [5]

Поставка

Дефинисати оцену грешке интерполације и одговарајући доказ.

4. питање [5]

Поставка

Извести композитно симпсоново правило користећи основно и грешку композитног симпсоновог правила користећи основну.

Теорија ДИС

1. питање

Поставка

Дефинисати Черчове тезе.

2. питање

Поставка

• Објаснити сложеност алгоритма помоћу Тјурингове машине.
• Шта је мера сложености?

3. питање

Поставка

Конструисати алгебарске структуре $GF(4)$ и $Z4$

Задаци ДИС

1. задатак

Тјурингова машина ради са азбуком ${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).

2. задатак

Доказати да се у коначном пољу $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$ пута).

3. задатак

• [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$ рекурзивне функције.

Логика

1. питање

Поставка

Став потпуности за исказни рачун

2. питање

Поставка

Навести неко формалну теорију која је одлучива и објаснити зашто је одлучива.

3. питање

Поставка

Пребацити израз у пренекс нормалну форму па у сколемову.

4. питање

Поставка

Наћи интерпретацију при којој је $(\forall X)(R(x) => Q(x,y))$ тачна и нетачна формула.