НАД/Јануар 2022 — разлика између измена
< НАД
Пређи на навигацију
Пређи на претрагу
м (Formatiranje i kategorizacija) |
м (Odeljci za postavke i rešenja; nerešeno) |
||
| Ред 1: | Ред 1: | ||
{{tocright}} | {{tocright}} | ||
{{Нерешено}} | |||
'''Испит у јануарском испитном року 2022. године''' одржан је 29. јануара. | '''Испит у јануарском испитном року 2022. године''' одржан је 29. јануара. | ||
| Ред 7: | Ред 8: | ||
== Дискретна математика == | == Дискретна математика == | ||
=== 1. задатак === | === 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, 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. | * '''[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. | ||
==== Решење ==== | |||
=== 2. задатак === | === 2. задатак === | ||
==== Поставка ==== | |||
* '''[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> | *: <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> рекурзивне функције. | * '''[5 поена]''' Доказати са су <math>f: N_0 \rarr N_0</math> и <math>g: N_0 \rarr N_0</math> рекурзивне функције. | ||
==== Решење ==== | |||
=== 3. задатак === | === 3. задатак === | ||
==== Поставка ==== | |||
'''[5 поена]''' | '''[5 поена]''' | ||
* Дефинисати поступак микрорекурзије. | * Дефинисати поступак микрорекурзије. | ||
* Илустровати поступак микрорекурзије на примеру функције <math>h: N_0 \rarr N_0</math>, <math>h(x) = | \sqrt{x} |</math> | * Илустровати поступак микрорекурзије на примеру функције <math>h: N_0 \rarr N_0</math>, <math>h(x) = | \sqrt{x} |</math> | ||
==== Решење ==== | |||
=== 4. задатак === | === 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> пута). | '''[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> пута). | ||
==== Решење ==== | |||
== Логика == | == Логика == | ||
Тренутна верзија на датум 7. фебруар 2023. у 20:48
- Овај рок није решен. Помозите SI Wiki тако што ћете га решити.
Испит у јануарском испитном року 2022. године одржан је 29. јануара.
Теорија из нумеричке математике
Теоријски део није сачуван.
Дискретна математика
1. задатак
Поставка
- [5 поена] Тјурингова машина ради са азбуком , где је празан симбол. Нека је на трацу Тјурингове машине природан број задат својим тернарним записом између два празна симбола, (нпр. 5 је у тернарном запису 12, број 11 као 102 итд.). У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину којим се задатом броју додаје 1 у тернарном систему (у питању је сабирање по модулу 3).
- [5 поена] Тјурингова машина ради са азбуком , где је b празан симбол. Нека је задат као низ од јединица између два празна симбола. У све остале ћелије је уписан празан симбол. Нека се глава Тјурингове машине налази над крајњим левим знаком задатаог броја. Конструисати програм за Тјурингову машину који испитује да ли је број дељив са 3.
Решење
2. задатак
Поставка
- [5 поена] Одредити сложеност за испитивање функције и датих са
- и
- [5 поена] Доказати са су и рекурзивне функције.
Решење
3. задатак
Поставка
[5 поена]
- Дефинисати поступак микрорекурзије.
- Илустровати поступак микрорекурзије на примеру функције ,
Решење
4. задатак
Поставка
[5 поена] Доказати да се у коначном пољу , је прост број, за произвољне елементе важи , где је ( пута).
Решење
Логика
Задаци нису сачувани.