1  Дискретно и континуално

Од аналогног сигнала до дигиталног податка

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

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

Зашто се уопште прешло на дигиталну технологију када су аналогни уређаји радили добро? Одговор се крије у односу квалитета и цене. Код аналогне технологије квалитет расте са улагањем по кривој која подсећа на логаритамску (тачније, на инверзну експоненцијалну функцију), као на слици 1.1. Уз мало улагања добија се пристојан квалитет, али двоструко веће улагање не доноси двоструко бољи квалитет, већ тек нешто бољи. Што смо ближе савршенству, сваки нови помак је скупљи: бољи грамофон захтева прецизнију механику, бољу иглу и тежи тањир, бољи филм финија зрна светлочулног слоја. На крају огромна улагања доносе занемарљиво побољшање — аналогна технологија је ударила у „зид“ и за даљи напредак био је потребан сасвим другачији приступ.

Слика 1.1: Однос квалитета и цене код аналогне технологије (шематски): свако удвостручење улагања доноси све мањи помак у квалитету

Зашто дигитализација уопште ради

Дигитализација на први поглед делује као сулуда идеја. Непрекидан сигнал, на пример звук, мери се само у одређеним тренуцима (узорковање), а свака измерена вредност заокружује се на један од коначно много нивоа (квантизација). Све што се дешава између два мерења неповратно се губи, као и разлика између праве и заокружене вредности (слика 1.2). Како онда дигитални запис може бити једнако добар као аналогни, или чак бољи?

Слика 1.2: Аналогни сигнал (лево) и његов дигитални запис (десно): вредност се мери у једнаким временским размацима и заокружује на један од 8 нивоа

Одговор је у томе што информацију на крају прима човек, а људска чула имају ограничења. Не морамо да сачувамо све, довољно је да сачувамо онолико колико чула могу да разликују:

  • Звук. Људско ухо чује звукове фреквенције до око 20 000 Hz. Према теореми о узорковању (Никвист–Шенон), сигнал се може верно реконструисати ако се мери бар двоструко чешће од највеће фреквенције у њему. Зато музички CD бележи 44 100 узорака у секунди, а сваки узорак је број од 16 бита (65 536 нивоа), што је финије него што ухо може да примети.
  • Покрет. Низ мирних слика које се смењују довољно брзо око доживљава као непрекидан покрет. Филм користи 24 слике у секунди, телевизија 25 или 30, а видео игре и снимци брзих сцена 60 и више.
  • Слика и боја. Са уобичајене удаљености око не разликује тачке мање од отприлике десетог дела милиметра, па екран са довољно густим пикселима изгледа као непрекидна слика. По 256 нивоа за сваку од три основне боје даје \(256^3\), што је више од 16 милиона боја, а то је више него што око може да разликује.

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

Технолошки пробој

Пробој који је све променио био је проналазак транзистора, а касније и интегрисаног кола. Ови изуми су омогућили стварање малих и брзих процесора способних да изврше милијарде операција у секунди. Уз то, цена памћења и обраде бројева од тада опада експоненцијално (Муров закон: број транзистора на чипу удвостручава се отприлике на сваке две године), па дигитални квалитет стално расте, а цена пада — управо супротно од засићене криве аналогне технологије. Када се теоријско знање о дигитализацији спојило са моћним хардвером, предности су биле огромне:

  • Савршено копирање: Дигитални подаци (низ нула и јединица) могу се копирати бесконачан број пута без икаквог губитка квалитета.

  • Лако чување и пренос: Огромне количине информација могу се сачувати на малом простору и пренети широм света готово тренутно.

  • Алгоритамска обрада: Једном када су звук, слика или текст претворени у бројеве, на њих се могу применити алгоритми за компресију, претрагу, анализу и обраду на начине који су у аналогном свету били незамисливи.

Најбоље се то види на примеру фотографије.

Слика 1.3: Аналогни (лево) и дигитални (десно) фотоапарат

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

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

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

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

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

Слика 1.4: Продаја филмских и дигиталних фотоапарата у свету (приближне вредности)

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

Прекретницу су донели велики језички модели (енгл. large language models, LLM), засновани на архитектури трансформера (2017): неуронске мреже са стотинама милијарди параметара, обучене на огромној количини текста, које предвиђају наставак текста део по део. На њима почивају асистенти као што су ChatGPT (OpenAI), Claude (Anthropic) и Gemini (Google), који разумеју и пишу текст на природном језику, преводе, сумирају, решавају задатке и пишу програмски код. Следећи корак су AI агенти — системи који не само да одговарају на питања, већ сами планирају и изводе низ корака: претражују интернет, покрећу програме, мењају датотеке и проверавају резултат док не заврше задатак. И овде се понавља иста прича: теорија стара деценијама постала је технологија која мења свакодневицу тек када ју је хардвер сустигао. А испод свега тога и даље су нуле и јединице, логичка кола и дискретне структуре којима се бави овај уџбеник.

Примене у савременом рачунарству

Видели смо да се цео дигитални свет, од фотографије до језичких модела, заснива на дискретним вредностима: битовима, бројевима и коначним скуповима стања. Математика која проучава такве објекте назива се дискретна математика, а њене структуре — исказна логика и Булова алгебра, скупови, релације, графови, аутомати и формални језици — предмет су овог уџбеника. Иако на први поглед делују апстрактно, оне су темељ савременог рачунарства: пројектовања процесора, алгоритама, база података, рачунарских мрежа, компресије података и вештачке интелигенције.

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

1. Применом математичке логике, тачније Булове алгебре, можемо конструисати основне компоненте рачунара које изводе прорачуне.

Аритметичко-логичка јединица (АЛУ) је суштински део процесора који обавља основне аритметичке и логичке операције. Полусабирач је део АЛУ и представља основно дигитално логичко коло које изводи сабирање два бинарна бита. Улазни битови су означени као \(A\) и \(B\) а излазне вредности су збир \(S\) и пренос \(C\). Полусабирач се ослања на примењену Булову алгебру, где је логичка операција ексклузивнe дисјункције (\(\veebar\), XOR, \(\oplus\) ) одговорна за одређивање резултата збира, а логичка операција конјункције (\(\wedge\), AND ) за пренос. Полусабирач је приказан на слици 1.5.

Слика 1.5: Полусабирач: збир \(S\) даје XOR коло, а пренос \(C\) AND коло

Кликом на улазе \(A\) и \(B\) мењате њихове вредности; жице и излази са вредношћу 1 истакнути су бојом.

XOR операција за израчунавање збира (S).

  • \(S = A \veebar B\)
  • Операција XOR даје резултат 1 ако је један улаз 1, а други 0. У супротном, резултат је 0.

AND операција за израчунавање преноса (C).

  • \(C = A \wedge B\)
  • Операција AND даје резултат 1 само ако су оба улаза 1. У супротном, резултат је 0.

2. Уз помоћ теорије графова, могуће је анализирати комплексне мреже и открити скривене структуре у подацима.

Tеорија графова се користи у анализи комплексних мрежа, на пример за идентификацију заједница или подгрупа унутар мреже. Заједнице су групе чворова који имају густе везе међу собом, док су везе са другим групама ређе.

Једну од најчешће коришћених мрежа за илустрацију заједница у мрежи представља мрежа под називом Захаријев карате клуб (енгл. Zachary’s karate club), приказана на слици 1.6. Мрежа је настала као резултат Захаријевог надгледања интеракција између чланова једног универзитетског карате клуба у периоду од 1970. до 1972. године. Тада је између 34 члана уочено 78 интеракција ван карате клуба. Сукоб између тренера (чвор 1) и председника (чвор 34) проузроковао је поделу чланова клуба у две групе. Један део чланова формирао је нови клуб са тренером, док су остали чланови окупљени око председника клуба ангажовали новог тренера.

На основу прикупљених података и теорије графова, Захарије је коректно предвидео одлуке свих чланова, осим члана број 9 који се придружио групи окупљеној око тренера уместо групи око председника.

Слика 1.6: Мрежа Захаријевог карате клуба

Упоредите насумичан цртеж мреже са распоредом силама и поделом на две групе; чворове можете превлачити.

3. Теорија графова (конкретно, стабла) и алгоритми дају нам алате попут Хафмановог кодирања за ефикасну компресију података.

Хафманово кодирање је поступак за компресију података који је 1952. године развио Дејвид Хафман. Заснива се на једноставној идеји: знакови који се у поруци појављују чешће добијају краће кодове, а ређи знакови дуже. Кодови се читају са бинарног стабла које се гради на следећи начин:

  1. за сваки знак пребројимо колико се пута појављује у поруци;
  2. два најређа знака (или већ формирана подстабла) спојимо у нови чвор чија је фреквенција збир њихових фреквенција;
  3. корак 2 понављамо док не остане једно стабло;
  4. код знака читамо на путу од корена до тог знака: скретање лево је 0, а десно 1.

Пошто се сви знакови налазе у листовима стабла, ниједан код није почетак неког другог кода, па се низ битова може дешифровати једнозначно, без размака између кодова.

Кодираћемо реченицу:

Човек је као разломак, чији је бројилац оно што он јесте, а именилац оно што мисли о себи. Што је именилац већи разломак је мањи.

Реченица има 129 знакова, а (ако не разликујемо велика и мала слова) 23 различита знака. Када би сваки знак имао код исте дужине, била би потребна 5 бита по знаку (\(2^5 = 32 \geq 23\)), односно укупно 645 бита. Хафманово стабло ове реченице приказано је на слици 1.7: у листовима су знакови са бројем појављивања (размак је приказан посебним знаком), а у унутрашњим чворовима збирови.

Слика 1.7: Хафманово стабло за дату реченицу

Кликом на знак истиче се пут од корена до њега и исписује се његов код. Можете унети и свој текст — стабло се гради поново.

Из стабла читамо кодове. Најчешћи знак, размак, добија код од само 3 бита, а најређи знакови по 7 бита:

Знак Број Код Знак Број Код Знак Број Код
размак 24 111 н 5 11000 . 2 100111
о 14 011 к 4 10001 б 2 101000
и 12 000 т 4 10010 в 2 101001
е 11 1101 с 3 01000 з 2 101010
а 10 1011 ц 3 01001 ч 2 101011
ј 7 0101 ш 3 10000 њ 1 1100100
л 6 0010 р 3 110011 ћ 1 1100101
м 6 0011 , 2 100110

Кодирана реченица има 524 бита уместо 645, што је уштеда од око 19%, односно у просеку око 4,06 бита по знаку уместо 5. Што је расподела знакова неравномернија, уштеда је већа.

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

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

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

Да бисмо пронашли све имејл адресе у неком тексту или верификовали да ли је унети низ валидна имејл адреса, можемо користити регуларни израз приказан на слици 1.8:

Слика 1.8: Регуларни израз за имејл адресу приказан као низ блокова

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

  • ^ и $ означавају почетак и крај низа, обезбеђујући да се цео низ проверава.
  • [a-zA-Z0-9_.+-]+ одговара корисничком имену које може садржати слова, бројеве и одређене специјалне знакове.
  • @ је обавезни симбол који раздваја корисничко име од домена.
  • [a-zA-Z0-9-]+ представља назив домена који може садржати слова, бројеве и минусе.
  • \. је тачка која раздваја домен од наставка.
  • [a-zA-Z0-9-.]+ одговара доменском наставку који може садржати слова, бројеве, тачке и минусе.

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

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

  • Архитектура рачунара
  • Структуре података и алгоритми
  • Базе података
  • Операциона истраживања
  • Конструкција и верификација софтвера