2 Увод

Дигитална револуција: Од аналогног сигнала до дигиталног податка

Прелазак са аналогне на дигиталну технологију представља једну од највећих промена у новијој историји, али тај процес није био линеаран. Он је савршен пример како се технолошки скокови дешавају када дође до синергије технологије и знања тј. када раније позната теоријска знања добију прилику за практичну примену захваљујући неком кључном пробоју у технологији.

Аналогни сигнали, попут звука на грамофонској плочи или видеа на старој видео касети, непрекидни су и подложни деградацији. Свако копирање или пренос уноси шум и губитак квалитета. Иако је теорија о претварању аналогних сигнала у дискретне, нумеричке вредности (бројеве) постојала деценијама, пре свега кроз радове Клода Шенона и развој Булове алгебре, недостајао је кључни елемент тј. ефикасан начин за обраду тих бројева.

Технолошки пробој који је све променио био је проналазак транзистора, а касније и интегрисаног кола. Ови изуми су омогућили стварање малих и брзих процесора способних да изврше милијарде операција у секунди. Тада се теоријско знање о дигитализацији спојило се са моћним хардвером за то време и бенефити су били огромни:

Савршено копирање: Дигитални подаци (низ нула и јединица) могу се копирати бесконачан број пута без икаквог губитка квалитета.
Лако чување и пренос: Огромне количине информација могу се сачувати на малом простору и пренети широм света готово тренутно.
Алгоритамска обрада: Једном када су звук, слика или текст претворени у бројеве, на њих се могу применити алгоритми за компресију, претрагу, анализу и обраду на начине који су у аналогном свету били незамисливи.

Пример

Код аналогног фотоапарата, светлост која пролази кроз објектив пада на филм обложен светлочулним хемикалијама. Интензитет светлости изазива хемијску реакцију која оставља трајан траг на филму. После фотографисања филм се мора развијати у мрачној комори, а добијена фотографија не може се лако мењати или обрађивати.

Са појавом дигиталних фотоапарата, процес креирања фотографије је постао електронски. Светлост више не делује на филм, већ на сензор (CCD или CMOS) који мери јачину светлости у свакој тачки и све те вредности чува у матрици бројеве. На пример, потпуној тами се може доделити вредност 0, а најсветлијој белој 255. За слике у боји, користе се филтери (најчешће црвени, зелени и плави) преко пиксела, па се за сваки пиксел бележе три вредности које одређују његову коначну боју. На тај начин настаје дигитална фотографија, скуп дискретних вредности које описују боју и осветљење сваког пиксела.

Претварање слике у низ бројева откључава огроман потенцијал за обраду, који је у аналогном свету био незамислив:

Дигитална фотографија се може одмах прегледати, проценити да ли је добра и обрисати је ако није, што штеди време и ресурсе.
Омогућено је једноставна обрада, корекција контраст, осветљења, боје.
Дигитална фотографија се може копирати милион пута и свака копија ће бити апсолутно идентична оригиналу. Дељење путем интернета је тренутно и глобално.
Дигитална фотографија може бити улаз за даљу рачунарску обраду и напредну анализу, као што су препознавање лица, детекција објеката и слично.

Графикон у наставку приказује прелазак са филмских (наранџаста) на дигиталне фотоапарате (љубичасто) у периоду од 1950. до 2023. године. Види се постепени раст продаје филмских апарата до краја 20. века, након чега следи нагли пораст и доминација дигиталних камера око 2010. године, а затим пад услед појаве камера на паметним телефонима.

Приметимо да сличан циклус и технолошки скок видимо и данас са вештачком интелигенцијом (AI). Иако теоријски модели попут неуронских мрежа постоје деценијама, тек развој изузетно моћног хардвера (попут графичких процесора – GPU) и доступност велике количине података омогућили су њихову широку примену и технолошку револуцију којој данас сведочимо.

Као што смо видели на овом примеру дигиталне фотографије, процес дигитализације се у основи своди на растављање сложене, континуалне целине (слике) на огроман број једноставних, појединачних елемената (пиксела). Да бисмо могли математички прецизно да опишемо и радимо са оваквим групама елемената, било да су то пиксели на сензору, бројеви у меморији или корисници на друштвеној мрежи, потребан нам је најосновнији алат за груписање. Тај темељни концепт, који представља азбуку дискретне математике, јесте скуп.

Скупови

Скуп је основни математички појам који представља колекцију добро дефинисаних и међусобно различитих објеката, који се називају елементима скупа. Елементи се не понављају у скупу тј. сваки елемент је јединствен. Објекти у скупу могу бити бројеви, матрице, функције, слова, људи, други скупови итд.

Скупови се најчешће задају на два начина:

Набрајањем елемената где се елементи директно наводе унутар витичастих заграда.
- Пример: $A = \{1, 2, 3, 4, 5\}$
Описом својства које сви његови елементи задовољавају
- Пример: $B = \{ x \mid x \text{ је паран број између 1 и 10} \}$

Приликом задавања скупа помоћу неког својства теба бити пажљив. На пример размотримо скуп $X=\{ A \mid A \notin A \}$ који садржи све скупове који не садрже сами себе као елемент. Да ли скуп $R$ садржи самог себе као елемент?

Ако претпоставимо да $X$ садржи самог себе $X\in X$ , онда по дефиницији скупа $X$, он не би требало да садржи самог себе $X\notin X$ (јер садржи само оне скупове који не садрже сами себе).
Ако претпоставимо да $X$ не садржи самог себе $X\notin X$, онда по дефиницији скупа $X$, он припада скупу X тј. $X\in X$ (јер задовољава услов да не садржи самог себе).

Ово доводи до контрадикције у оба случаја.

Да би овај парадокс учинио приступачнијим, Расел је формулисао причу о берберину:

У једном селу постоји берберин који брије све оне, и само оне, који не брију сами себе. Поставља се питање: Ко брије берберина?

Ако берберин брије самог себе, по дефиницији, он не би требало да брије самог себе (јер брије само оне који не брију сами себе).
Ако берберин не брије самог себе тада, по дефиницији, он би требало да брије самог себе (јер брије све који не брију сами себе).

Овај парадокс, познат као Раселов парадокс, показује да наивна теорија скупова, која дозвољава формирање било ког скупа на основу било ког дефинисаног својства, води до противречности. Због тога се користе формални аксиоматски системе теорије скупова који строго одређују како се скупови смеју формирати, а њихово детаљније проучавање припада области математичке логике.

Елементи у скупу се не понављају тј. сваки елемент је јединствен. Редослед елемената није битан тако да је скуп $\{1, 2, 3\}$ исти као скуп $\{3, 2, 1\}$.

Скупове често приказујемо и графички коришћењем Венеових дијаграма који користе кругове или друге затворене криве за представљање скупова. Пресеци између кругова приказују заједничке елементе (пресеке) између скупова.

На пример, скуп бројева $А = \{1,2,3,4,5,6,7,8,9,10\}$ који су разврстани у делиоце броја 10 (скуп B) и парне бројеве (скуп C) приказан је на слици:

Основне релације међу скуповима су:

Једнакост скупова $=$
- Два скупа $A$ и $B$ су једнаки ако садрже потпуно исте елементе.
- Пример: Ако је $A = \{1, 2, 3\}$ и $B = \{3, 2, 1\}$, онда је $A = B$.
Подскуп $\subseteq$ и надскуп $\supseteq$:
- Скуп $A$ је подскуп скупа $B$ ако су сви елементи $A$ такође и елементи $B$.
- Скуп $B$ је надскуп скупа $A$ ако је $A \subseteq B$.
- Пример: $A = {2, 3}, B = {1, 2, 3, 4} $, тада је $A \subseteq B$ и $B \supseteq A$.
Прави подскуп $\subset$ и прави надскуп $\supset$:
- Скуп $A$ је прави подскуп скупа $B$ ако је $A \subseteq B$ и $A \neq B$.
- Скуп $B$ је прави надскуп скупа $A$ ако је $B \supseteq A$ и $A \neq B$.
- Пример: $A = \{2, 3\}, B = \{1, 2, 3, 4\}$, тада је $A \subset B$ и $B \supset A$.

Основне операције између скупова су:

Унија скупова $\cup$:
- Унија два скупа $A$ и $B$ је скуп свих елемената који припадају бар једном од скупова $A$ или $B$ односно $A \cup B = \{ x \mid x \in A \ \text{или} \ x \in B \}$.
- Пример: Ако је $A = \{1, 2, 3\}$ и $B = \{3, 4, 5\}$, онда је $A \cup B = \{1, 2, 3, 4, 5\}$.
Пресек скупова $\cap$:
- Пресек два скупа $A$ и $B$ је скуп свих елемената који су заједнички за оба скупа односно $A \cap B = \{ x \mid x \in A \ \text{и} \ x \in B \}$.
- Пример: Ако је $A = \{1, 2, 3\}$ и $B = \{2, 3, 4\}$, онда је $A \cap B = \{2, 3\}$.
Разлика скупова $\setminus$:
- Разлика скупова $A$ и $B$ је скуп елемената који припадају скупу $A$, али не и скупу $B$ односно $A \setminus B = \{ x \mid x \in A \ \text{и} \ x \notin B \}$.
- Пример: Ако је $A = \{1, 2, 3, 4\}$ и $B = \{3, 4, 5\}$, онда је $A \setminus B = \{1, 2\}$.
Симетрична разлика $\triangle$:
- Симетрична разлика скупова $A$ и $B$ је скуп елемената који припадају тачно једном од скупова $A$ или $B$ односно $A \triangle B = (A \setminus B) \cup (B \setminus A)$.
- Пример: Ако је $A = \{1, 2, 3\}$ и $B = \{3, 4, 5\}$, онда је $A \triangle B = \{1, 2, 4, 5\}$.
Комплемент скупа:
- Комплемент скупа $A$ у односу на неки универзални скуп $U$ ¹ је скуп свих елемената који припадају $U$, али не припадају $A$ односно $A' = U \setminus A$.
- Пример: Ако је $U = \{1, 2, 3, 4, 5\}$ и $A = \{2, 3\}$, онда је $A' = \{1, 4, 5\}$.

За неведене операције важе следеће особине:
- Комутативност уније и пресека:
  - $A \cup B = B \cup A$.
  - $A \cap B = B \cap A$.
- Асоцијативност уније и пресека:
  - $(A \cup B) \cup C = A \cup (B \cup C)$.
  - $(A \cap B) \cap C = A \cap (B \cap C)$.
- Дистрибутивност:
  - $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
  - $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
- Де Морганови закони:
  - $(A \cup B)' = A' \cap B'$.
  - $(A \cap B)' = A' \cup B'$.

Партитивни скуп неког скупа $A$ је скуп свих могућих подскупова скупа $A$. Означава се са $\mathcal{P}(A)$. Формално: \[ \mathcal{P}(A) = \{ B \mid B \subseteq A \} \]

Пример: Ако је $A = \{a, b, c\}$, онда је:

\[ \mathcal{P}(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \} \]

Ако скуп $A$ има $n$ елемената, онда партитивни скуп $\mathcal{P}(A)$ има $2^n$ елемената. Сваки подскуп је јединствено одређен комбинацијом избора елемената. За сваки од $n$ елемената постоје две могућности (узети или не узети), што резултира укупним бројем комбинација $2^n$. Ово је аналогно бројању у бинарном систему** од $0$ до $2^n - 1$, где сваки број представља један подскуп.

За претходни пример:

Бинарни низ	Избор елемената (a, b, c)	Подскуп
000	(0, 0, 0)	$\emptyset$ (празан скуп)
001	(0, 0, 1)	$\{c\}$
010	(0, 1, 0)	$\{b\}$
011	(0, 1, 1)	$\{b, c\}$
100	(1, 0, 0)	$\{a\}$
101	(1, 0, 1)	$\{a, c\}$
110	(1, 1, 0)	$\{a, b\}$
111	(1, 1, 1)	$\{a, b, c\}$

Укупно: $2^3 = 8$ подскупова.

Декартов производ $n$ скупова $A_1, A_2, A_3, \dotsc, A_n$ је скуп свих уређених $n$-торки где је први елемент из скупа $A_1$, други из скупа $A_2$, трећи из $A_3$, и тако даље, до $n$-тог елемента из скупа $A_n$ тј. \[ A_1 \times A_2 \times A_3 \times \dotsb \times A_n = \{ (a_1, a_2, a_3, \dotsc, a_n) \mid a_1 \in A_1, \ a_2 \in A_2, \ \dotsc, \ a_n \in A_n \} \]

Пример Нека су дати скупови:

$A_1 = \{1, 2\}$
$A_2 = \{a, b\}$
$A_3 = \{\alpha, \beta\}$

тада је:

\[ A_1 \times A_2 \times A_3 = \{ (1, a, \alpha), \ (1, a, \beta), \ (1, b, \alpha), \ (1, b, \beta), \ (2, a, \alpha), \ (2, a, \beta), \ (2, b, \alpha), \ (2, b, \beta) \} \]

У овом примеру укупно има $2 \cdot 2 \cdot 2 = 8$ уређених тројки а генерално важи: \[ \left| A_1 \times A_2 \times \dotsb \times A_n \right| = |A_1| \times |A_2| \times \dotsb \times |A_n| \]

Релације, функције, операције

Бинарна релација повезује елементе из једног скупа са елементима из другог скупа по одређеном правилу или својству. Формално, релација $R$ од скупа $A$ до скупа $B$ је подскуп Декартовог производа $A \times B$. Када је $A = B$, говоримо о релацији на скупу $A$.

Пример:

Нека је $A = \{1, 2, 3\}$, и нека је дата релација $R$ на $A$ као $R = \{ (1, 2), \ (1, 3), \ (2, 3) \}$. Ако пажљиво погледамо који елементи су у релацији тј. шта су елементи скупа $R$ можемо рећи да је на овај начин дефинисана речација мање ($<$) на скупу $A$. Дакле $a$ је у релацији са $b$ ако је $a$ мање од $b$: —

Функција $f$ из скупа $A$ у скуп $B$ је релација која сваком елементу $a \in A$ придружује тачно један елемент $b \in B$. У том случају користимо запис $f: A \to B$ Код релације, један елемент $a \in A$ може бити повезан са више елемената у $B$, или ни са једним. У функцији, сваки $a \in A$ је повезан са тачно једним $b \in B$.

Операција дужине $n$ ($n$-арна операција) на скупу $A$ је било која функција $f: A^n \to A$. Дакле то је функција која узима $n$ елемената из скупа $A$ и враћа један елемент из скупа $A$.

Бинарне операције су посебан случај када је $n = 2$ (на пример, сабирање или множење реалних бројева). Унарне операције су посебан случај када када је $n = 1$ (на пример, негација, апсолутна вредност реалног броја)

Скупови и торке у програмском језику Python

У програмском језику Python, скупови су уграђена структура података која представља неуређену колекцију² јединствених елемената.

Дефинисање скупа

Витичасте заграде и набрајање ³:**

A = {1, 2, 3, 4}

Функција set()

A = set([1, 2, 3, 4])
prazan_skup = set()

Set comprehension конструкција

А = {x for x in range(1, 11) if x % 2 == 0}
print(А)  # Излаз: {2, 4, 6, 8, 10}

{2, 4, 6, 8, 10}

Током имплементације различитих алгоритама јавља се потреба за додавање и уклањање елемената из скупа. Додавање елемента се врши методом (add) ⁴ док се за брисање елемента из скупа може користити метода remove или discard. Обе методе имају исту функцију само ће се при коришћењу remove методе јавити грешка ако елемент не постоји у скупу, док се при коришћењу методе discard неће јавити грешка ако елемент није пронађен.

A = {1, 2, 3}
A.add(4)
print(A)  # Излаз: {1, 2, 3, 4}
A.remove(2)
print(A)  # Излаз: {1, 3, 4}
A.discard(5)
print(A)  # Излаз: {1, 3, 4}
#A.remove(5) ---> KeyError: 5

{1, 2, 3, 4}
{1, 3, 4}
{1, 3, 4}

Релације између скупова

Провера подскупа (метод issubset или оператор<=):

A = {1, 2}
B = {1, 2, 3}
print(A.issubset(B))  # Излаз: True
print(A <= B)  # Излаз: True

True
True

Провера надскупа (метод issuperset или оператор >=):**

A = {1, 2}
B = {1, 2, 3}
print(A.issuperset(B))  # Излаз: False
print(A >= B)  # Излаз: False

False
False

Провера једнакости скупова (оператор ==)

A = {1, 2, 3}
B = {3, 2, 1}
print(A == B)  # Излаз: True

True

Провера дисјунктности скупова ( метод isdisjoint)

A = {1, 2}
B = {3, 4}
print(A.isdisjoint(B))  # Излаз: True

True

Oперације над скуповима

Унија скупова (метод union или оператор |)

A = {1, 2, 3}
B = {3, 4, 5}
C = A.union(B)
print(C)  # Излаз: {1, 2, 3, 4, 5}
C = A | B
print(C)  # Излаз: {1, 2, 3, 4, 5}

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}

Пресек скупова (метод intersection или оператор &)

A = {1, 2, 3}
B = {2, 3, 4}
C = A.intersection(B)
print(C)  # Излаз: {2, 3}
C = A & B
print(C)  # Излаз: {2, 3}

{2, 3}
{2, 3}

Разлика скупова (метод difference или оператор-)

A = {1, 2, 3, 4}
B = {3, 4, 5}
C = A.difference(B)
print(C)  # Излаз: {1, 2}
C = A - B
print(C)  # Излаз: {1, 2}

{1, 2}
{1, 2}

Симетрична разлика (метод symmetric_difference или оператор ^)

A = {1, 2, 3}
B = {3, 4, 5}
C = A.symmetric_difference(B)
print(C)  # Излаз: {1, 2, 4, 5}
C = A ^ B
print(C)  # Излаз: {1, 2, 4, 5}

{1, 2, 4, 5}
{1, 2, 4, 5}

Пример

Ана, Борис и Владимир похађају предмет Дискретне математичке структуре, док Борис, Горан и Дејан похађају предмет Математика 1.

Одреди:

које студенте похађају оба предмета,
које похађају само Математику 1,
и скуп свих студената који похађају бар један од ова два предмета.

# Скуп студената који похађају ДМС
dms_studenti = {'Ана', 'Борис', 'Владимир'}

# Скуп студената који похађа М1
m1_studenti = {'Борис', 'Горан', 'Дејан'}

# Студенти који похађају оба предмета
oba_predmeta_studenti = dms_studenti & m1_studenti
print(oba_predmeta_studenti)  # Излаз: {'Борис'}

# Студенти који похађају М1, али не и ДМС
samo_m1_studenti = m1_studenti - dms_studenti
print(samo_m1_studenti)  # Излаз: {'Горан', 'Дејан'}

# Сви студенти
svi_studenti = dms_studenti | m1_studenti
print(svi_studenti)  # Излаз: {'Ана', 'Борис', 'Владимир', 'Горан', 'Дејан'}

{'Борис'}
{'Горан', 'Дејан'}
{'Горан', 'Ана', 'Борис', 'Владимир', 'Дејан'}

Пример

Дата је листа бројева у којој се неки елементи понављају. Уклонити дупликате из листе и приказати листу са јединственим вредностима.

lista_brojeva = [1, 2, 2, 3, 4, 4, 5]
lista_brojeva_bez_duplikata = list(set(lista_brojeva))
print(lista_brojeva_bez_duplikata)  # Излаз: [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

Торке (tuples) су непроменљиве (immutable), уређене секвенце у Пајтону које служе за груписање обично хетерогених елемената.

Дефинисање торке

Обичне заграде и набрајање:

moja_torka = (1, 'jabuka', 3.14, True)

Функција tuple()

druga_torka = tuple(['a', 'b', 'c'])
prazna_torka = tuple()

За дефинисање торке са само једним елементом, неопходно је користити зарез иза елемента, нпр. t = (1,). У супротном, Пајтон ће то протумачити само као број или стринг у заградама.

Основна карактеристика торки је њихова непроменљивост (immutability). Једном када је торка креирана, њени елементи се не могу мењати, додавати нити брисати. Ово их чини идеалним за чување података за које желимо да остану константни, као што су координате, подешавања или кључеви у речницима.

t = (1, 2, 3)

# Покушај измене елемента ће изазвати грешку
# t[0] = 5 ---> TypeError: 'tuple' object does not support item assignment

# Покушај додавања или брисања такође није могућ
# t.append(4) ---> AttributeError: 'tuple' object has no attribute 'append'

Паковање и распакивање торки

Python нуди елегантан начин за рад са торкама кроз механизме паковања и распакивања.

Паковање је процес креирања торке, где се више вредности “пакује” у једну променљиву. Распакивање је обрнут процес, где се вредности из торке додељују појединачним променљивима. Заграде око торке нису увек обавезне, што чини код читљивијим.

# Паковање торке (заграде нису неопходне)
podaci = "Пера", "Перић", "23.05.1995" 

# Распакивање торке
(ime, prezime, datum_rodjenja) = podaci
# или без заграда
# ime, prezime, datum_rodjenja = podaci

print(f"Име: {ime}, Презиме: {prezime}") # Излаз: Име: Пера, Презиме: Перић

Име: Пера, Презиме: Перић

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

x, y = 10, 20
x, y = y, x # Замена вредности
print(f"x = {x}, y = {y}") # Излаз: x = 20, y = 10

x = 20, y = 10

Поред тога торке се често користе у функцијама за враћање више вредности као једне целине и за прихватање променљивог броја аргумената који се аутоматски пакују у торку.

Скуп који садржи све елементе који се разматрају у датом контексту.↩︎
Не чува се редослед елемената, није могуће приступити елементима путем индекса.↩︎
Празан скуп се мора дефинисати коришћењем функције set(), јер {} представља празан речник у Python-у.↩︎
Скупови не дозвољавају дупликате; ако покушамо да додамо дупликат, он ће бити игнорисан↩︎