НАД/РТИ Јул 2022

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

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

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

1. питање

Поставка

[5 поена] Извести Њутнову методу (на произвољан начин).

2. питање

Поставка

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

3. питање

Поставка

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

4. питање

Поставка

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

Теорија из дискретне математике

1. питање

Поставка

• Навести полазне рекурзивне функције.
• 2 лака примера за примитивну рекурзију чије поставке нису сачуване.

2. питање

Поставка

Дефинисати проблем трговачког путника и извести сложеност за његово решавање.

3. питање

Поставка

За прстен $(Z4,+_4, \sdot _4)$ наћи идемпотентне елементе, нилипотентне елементе, делитеље нуле, инвертибилне елементе.

Задаци из дискретне математике

1. задатак

Поставка

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

2. задатак

Поставка

Одредити сложеност $Ax=b$, где је $A$ горње троугаона матрица, $x$ матрица коефицијената, а $b$ матрица решења.

3. задатак

Поставка

Доказати примитивну рекурзивност функција:

• $x / 3$
• $x \% 3$

Логика

1. питање

Поставка

• Дефинисати сколемизацију.
• Написати формулу за метод резолуције.

2. питање

Поставка

Дат је скуп саставака, наћи ербранов домен.

3. питање

Поставка

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