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

Белешке [радна верзија]

Аутор
Афилација

Душан Џамић

Универзитет у Београду, Факултет организационих наука

Објављено

05.11.2025

Инфорамције о предмету

Назив предмета: Дискретне математичке структуре

Студијски програм: Информациони системи и технологије

Број часова: 2 часа предавања + 2 часа вежби

Број ЕСПБ: 5

Наставник: др Душан Џамић, проф. др Богдана Станојевић

Асистенти: Нада Младеновић, Ђорђе Јовановић

Распоред наставе

Дан В/П Група Време Сала Наставник/Сарадник
Понедељак В Б7 10:15 - 12:00 14 Нада Младеновић
Уторак В Б1 10:15 - 12:00 30 Нада Младеновић
В Б2 10:15 - 12:00 15 Ђорђе Јовановић
Среда В Б4 10:15 - 12:00 18 Нада Младеновић
В Б3 10:15 - 12:00 12 Ђорђе Јовановић
В Б6 12:15 - 14:00 13 Нада Младеновић
В Б5 12:15 - 14:00 30 Ђорђе Јовановић
Четвртак П Б1, Б3, Б4 08:15 - 10:00 Амфитеатар 2 Душан Џамић
Петак В Б8 10:15 - 12:00 20 Ђорђе Јовановић
П Б5, Б6, Б7 10:15 - 12:00 Амфитеатар 5 Душан Џамић
П Б2, Б8 12:15 - 14:00 Амфитеатар 5 Душан Џамић

Распоред консултација

Наставник/ сарадник Дан Време Кабинет
Душан Џамић четвртак 10:30 - 12:00 215
Нада Младеновић среда - 225
Ђорђе Јовановић уторак - 225

Садржај предмета

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

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

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

  • Математичка логика: Исказни и предикатски рачун.
  • Релацијске структуре: Уређени скупови. Релација еквиваленције.
  • Теорија графова: Оријентисани и неоријентисани графови. Стабла и њихова примена.
  • Теорија коначних аутомата: Коначна машина и коначни аутомат.
  • Формални језици: Граматика и језик генерисан граматиком.
  • Тјурингова машина и појам алгоритма: Сложеност алгоритама.

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

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

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

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

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). Мрежа је настала као резултат Захаријевог надгледања интеракција између чланова једног универзитетског карате клуба у периоду од 1970. до 1972. године. Тада је између 34 члана уочено 78 интеракција ван карате клуба. Сукоб између тренера (чвор 1) и председника (чвор 34) проузроковао је поделу чланова клуба у две групе. Један део чланова формирао је нови клуб са тренером, док су остали чланови окупљени око председника клуба ангажовали новог тренера.

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

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

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

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

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

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

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

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

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

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

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

Литература

Основна литература:

  1. М. Чангаловић, В. Тодорчевић, В. Балтић, Дискретне математичке структуре, ФОН, Београд, 2019.
  2. В. Тодорчевић, В. Балтић, М. Чангаловић, Збирка задатака из дискретних математичких структура, ФОН, Београд, 2016.

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

  1. Ј.А. Anderson, Discrete Mathematics with Combinatorics, Pearson Education, 2004.
  2. Д. Стевановић, В. Балтић, С. Симић, М. Ћирић, Дискретна математика - основе комбинаторике и теорије графова, ДМС, Београд, 2008.
  3. Д. Цветковић, С. Симић, Дискретна математика, Либра, Београд, 2000.
  4. K.H. Rosen, Discrete Mathematics and Its Applications, fourth edition, McGraw-Hill, 1999.

Правила полагања

  1. Предиспитне обавезе (60 поена):
    • Домаћи задаци (20 поена):
      • 3 домаћа задатка током семестра, два по 5 и један вредан 10 поена.
    • Колоквијуми (30 поена, минимум у збиру 15 на сваком преко 5):
      • 2 колоквијума током семестра, сваки вредан 15 поена.
    • Активност на предавањима и вежбама (10 поена):
      • Присуство, учешће у дискусијама, кратки квизови на часу, решавање проблема.
  2. Испитне обавезе (40 поена):
    • Завршни испит (40 поена, минимум 20 поена):
      • Обухвата теоријска питања и практичне задатке који покривају целокупно градиво.

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

Скала за оцењивање:

Оцена Број поена
6 [51-60]
7 [61-70]
8 [71-80]
9 [81-90]
10 [91-100]