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

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

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

Теорија из нумеричке математике

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))$ тачна и нетачна формула.