НАД/Јануар 2022 — разлика између измена

Тренутна верзија на датум 7. фебруар 2023. у 20:48

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

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

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

Теоријски део није сачуван.

Дискретна математика

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 \mathbb{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$ пута).

Решење

Логика

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

@@ Ред 1: / Ред 1: @@
 {{tocright}}
-Испит у септембарском испитном року одржан је 14. 9. 2022. године.
+{{Нерешено}}
+'''Испит у јануарском испитном року 2022. године''' одржан је 29. јануара.
-== Теорија НУМ ==
+== Теорија из нумеричке математике ==
-Није објављено.
+Теоријски део није сачуван.
-== ДИС ==
+== Дискретна математика ==
+=== 1. задатак ===
+==== Поставка ====
+* '''[5 поена]''' Тјурингова машина ради са азбуком <math>{0, 1, 2, b}</math>, где је <math>b</math> празан симбол. Нека је на трацу Тјурингове машине природан број задат својим тернарним записом између два празна симбола, (нпр. 5 је у тернарном запису 12, број 11 као 102 итд.). У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину <math>f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}</math> којим се задатом броју додаје 1 у тернарном систему (у питању је сабирање по модулу 3).
+* '''[5 поена]''' Тјурингова машина ради са азбуком <math>{0, 1, b}</math>, где је b празан симбол. Нека је <math>n \isin \mathbb{N}</math> задат као низ од <math>n+1</math> јединица између два празна симбола. У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину <math>f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}</math> који испитује да ли је број <math>n</math> дељив са 3.
-=== 1. задатак ===
+==== Решење ====
-* '''[5]''' Тјурингова машина ради са азбуком <math>{0, 1, 2, b}</math>, где је b празан симбол. Нека је на трацу Тјурингове машине природан број задат својим тернарним записом између два празна симбола, (нпр. 5 је у тернарном запису 12, број 11 као 102 итд.). У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину <math>f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}</math> којим се задатом броју додаје 1 у тернарном систему (у питању је сабирање по модулу 3).
-* '''[5]''' Тјурингова машина ради са азбуком <math>{0, 1, b}</math>, где је b празан симбол. Нека је n<math>\isin</math><math>N</math> задат као низ од <math>n+1</math> јединица између два празна симбола. У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину <math>f: (Q U {q_0}) \times S \rarr (Q U {\{q+,q-\}}) \times S \times {\{+1,-1\}}</math> који испитује да ли је број <math>n</math> дељив са 3.
 === 2. задатак ===
-* '''[5]''' Одредити сложеност за испитивање функције <math>f: N_0 \rarr N_0</math> и <math>g: N_0 \rarr N_0</math> датих са
+==== Поставка ====
-<div><math>f(n) = \sum_{k=0}^n \binom{n}{k}</math> и <math>g(n) = \sum_{k=0}^n k \binom{n}{k}</math></div>
+* '''[5 поена]''' Одредити сложеност за испитивање функције <math>f: N_0 \rarr N_0</math> и <math>g: N_0 \rarr N_0</math> датих са
-* '''[5]''' Доказати са су <math>f: N_0 \rarr N_0</math> и <math>g: N_0 \rarr N_0</math> рекурзивне функције.
+*: <math>f(n) = \sum_{k=0}^n \binom{n}{k}</math> и <math>g(n) = \sum_{k=0}^n k \binom{n}{k}</math>
+* '''[5 поена]''' Доказати са су <math>f: N_0 \rarr N_0</math> и <math>g: N_0 \rarr N_0</math> рекурзивне функције.
+==== Решење ====
-=== 3. задатак [5]===
+=== 3. задатак ===
+==== Поставка ====
+'''[5 поена]'''
 * Дефинисати поступак микрорекурзије.
 * Илустровати поступак микрорекурзије на примеру функције <math>h: N_0 \rarr N_0</math>, <math>h(x) = | \sqrt{x} |</math>
-=== 4. задатак [5]===
+==== Решење ====
-* Доказати да се у коначном пољу <math>GF(p) = (Z_{p}, +_{p}, \sdot _{p}), Zp = {0,1,2....p-1}</math>, <math>p</math> је прост број, за произвољне елементе <math>a, b \isin Z_p</math> важи <math>(a +_p b)^p = a^p +_p + b^p</math>, где је <math>a^p = a \sdot _p ... a \sdot _p</math> (<math>p</math> пута).
+=== 4. задатак ===
+==== Поставка ====
+'''[5 поена]''' Доказати да се у коначном пољу <math>GF(p) = (Z_{p}, +_{p}, \sdot _{p}), Zp = {0,1,2....p-1}</math>, <math>p</math> је прост број, за произвољне елементе <math>a, b \isin Z_p</math> важи <math>(a +_p b)^p = a^p +_p + b^p</math>, где је <math>a^p = a \sdot _p ... a \sdot _p</math> (<math>p</math> пута).
+==== Решење ====
 == Логика ==
 Задаци нису сачувани.
+[[Категорија:НАД]]
+[[Категорија:Рокови]]

НАД/Јануар 2022 — разлика између измена

Тренутна верзија на датум 7. фебруар 2023. у 20:48

Садржај

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

Дискретна математика

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Логика

Мени за навигацију

НАД/Јануар 2022 — разлика између измена

Тренутна верзија на датум 7. фебруар 2023. у 20:48

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

Дискретна математика

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Логика

Мени за навигацију

Претрага