НАД/К1 2021

Први колоквијум одржан је 2.11.2021. и састојао се од 4 задатка. Сваки задатак вредео је 5 поена. Колоквијум је трајао 70 минута.

Задаци

1. задатак

Поставка

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

2. задатак

Поставка

Доказати да су суме првих $n$ чланова

• аритметичке прогресије са први чланом $a_1=1$ и различком $d=2$
• геометријске прогресије са првим чланом $a_1=1$ и количником $d=2$

3. задатак

Поставка

Нека су дате функције $f: N \rarr R$ и $f: N \rarr R$.

• $f(n)=\frac{n^2-1}{2n}$ и $g(n)=2n$;
• $f(n)=3n+\sqrt{n^3}$ и $g(n)=2n^2$;
• $f(n)=n+\log_{2} n$ и $g(n)=n+\sqrt{n}$;

Одредити која од релација $g(n)=O(f(n))$ и/или $f(n)=O(g(n))$ важи када $n \rarr \infty$. Одговор детаљно образложити.

4. задатак

Поставка

Нека је дато коначно поље $(Z_{11}, +_{11}, \sdot _{11})$, где је $Z_{11}$ скуп остатака при дељењу са 11, а $+_{11}$ и $\sdot _{11}$ редом, сабирање, односно множење по модулу 11. Израчунати:

• $2 \sdot _{11} (4 +_{11} 6)^{-1}$
• $(3 +_{11} 15)^{11}$

Одредити све елементе $x \isin Z_{11}$ за које важи:

• $2x =x +_{11} x = 0$
• $x^2 = x \sdot _{11} x = 1$
• $x^2 = x \sdot _{11} x = x$