Дискретне математичке структуре
Белешке [радна верзија]
О предмету и уџбенику
Назив предмета: Дискретне математичке структуре
Студијски програм: Информациони системи и технологије
Број часова: 2 часа предавања + 2 часа вежби
Број ЕСПБ: 5
Наставник: проф. др Душан Џамић
Асистенти: Нада Младеновић, Ђорђе Јовановић
| Дан | В/П | Група | Време | Сала | Наставник/сарадник |
|---|---|---|---|---|---|
| Понедељак | В | Б3 | 08:15 – 10:00 | 16 | Нада Младеновић |
| В | Б1 | 10:15 – 12:00 | 16 | Нада Младеновић | |
| В | Б7 | 12:15 – 14:00 | 15 | Нада Младеновић | |
| В | Б4 | 16:15 – 18:00 | 16 | Ђорђе Јовановић | |
| Уторак | П | Б7, Б8 | 14:15 – 16:00 | Амф 4 | Душан Џамић |
| П | Б1, Б2, Б3, Б4 | 16:15 – 18:00 | Амф 4 | Душан Џамић | |
| Петак | В | Б6 | 08:15 – 10:00 | 14 | Нада Младеновић |
| В | Б5 | 08:15 – 10:00 | 15 | Ђорђе Јовановић | |
| П | Б5, Б6 | 10:15 – 12:00 | Амф 5 | Душан Џамић | |
| В | Б2 | 14:15 – 16:00 | 16 | Ђорђе Јовановић | |
| В | Б8 | 16:15 – 18:00 | 16 | Ђорђе Јовановић |
| Наставник/сарадник | Дан | Време | Кабинет |
|---|---|---|---|
| Душан Џамић | петак | 12:00 – 14:00 | А219 |
| Нада Младеновић | понедељак | 10:00 - 12:00 | А218 |
| Нада Младеновић | среда | 16:00 - 17:00 | А218 |
| Ђорђе Јовановић | понедељак | 15:00 - 16:00 и 18:00 - 19:00 | А218 |
| Ђорђе Јовановић | петак | 13:00 - 14:00 | А218 |
Правила полагања
| Део | Обавеза | Макс. поена | Услов | Период |
|---|---|---|---|---|
| Предиспитне обавезе | Домаћи задаци (5 + 5 + 10) |
20 | - | током семестра |
| Активност на предавањима и вежбама | 10 | - | током семестра | |
| Писмени део | Два колоквијума (15 + 15) или писмени испит (30) |
30 | ≥ 15 укупно код колоквијума ≥ 5 на сваком |
колоквијуми током семестра писмени у испитном року |
| Усмени део | Завршни испит | 40 | ≥ 20 | испитни рок |
| Укупно | 100 | ≥ 51 |
Активност обухвата присуство, учешће у дискусијама, кратке квизове на часу и решавање проблема. Завршни испит обухвата теоријска питања и задатке из целокупног градива.
| Оцена | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|
| Број поена | 0–50 | 51–60 | 61–70 | 71–80 | 81–90 | 91–100 |
Литература
Основна литература:
- М. Чангаловић, В. Тодорчевић, В. Балтић, Дискретне математичке структуре, ФОН, Београд, 2019.
- В. Тодорчевић, В. Балтић, М. Чангаловић, Збирка задатака из дискретних математичких структура, ФОН, Београд, 2016.
Допунска литература:
- K. H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019.
- J. A. Anderson, Discrete Mathematics with Combinatorics, Pearson Education, 2004.
- Д. Стевановић, В. Балтић, С. Симић, М. Ћирић, Дискретна математика — основе комбинаторике и теорије графова, ДМС, Београд, 2008.
- Д. Цветковић, С. Симић, Дискретна математика, Либра, Београд, 2000.
Предговор
Док се многе природне науке баве континуалним величинама попут времена и простора, рачунарство је у својој сржи свет дискретних корака, података и стања: свет нула и јединица, пиксела на екрану и корака у алгоритму.
Да бисмо разумели, описали и контролисали тај дигитални свет, потребна нам је посебна математичка дисциплина. Управо то су дискретне математичке структуре: формални алати за рад са објектима који не подржавају или не захтевају појам непрекидности. Оне су језик и темељ на којем почива целокупно савремено рачунарство.
Уџбеник прати градиво предмета Дискретне математичке структуре и упознаје вас са појмовима који вам омогућавају да размишљате као инжењер софтвера, аналитичар података или стручњак за вештачку интелигенцију:
- Дискретно и континуално: зашто је рачунарски свет дискретан и где се дискретне структуре срећу у пракси;
- Скупови: основне операције, партитивни скуп и Декартов производ;
- Исказни рачун: искази, формуле, таутологије, логичко закључивање, нормалне форме, Булове функције, Карноове мапе и Булове алгебре као заједничка структура исказног и скуповног рачуна;
- Дигитална логика: NAND и NOR као универзална кола, логичка кола од прекидача до сабирача и меморије;
- Предикатски рачун: квантификатори и формализација математичких тврђења;
- Релације: својства релација, релације еквиваленције и уређења;
- Графови: повезаност, класе графова, оријентисани графови, Ојлерови графови и стабла;
- Коначни аутомати и формални језици: модели израчунавања и опис језика граматикама.
Како користити уџбеник
Градиво је подељено у поглавља која се надовезују једно на друго. Кључни делови текста издвојени су у блокове, тако да се лако уочавају при читању и понављању:
- Теорема и Доказ формулишу и образлажу тврђење,
- Пример показује појам или поступак на конкретном случају,
- Задатак служи за самосталну вежбу; сви задаци, са решењима, сабрани су у делу Збирка задатака,
- Напомена скреће пажњу на важан детаљ или честу грешку,
- Python показује како се појам користи у програмском језику Python,
- Из историје даје кратак осврт на порекло појма.
Теореме и примери нумерисани су по поглављима (нпр. Пример 3.2 је други пример у трећем поглављу). Коришћене ознаке сабране су на крају књиге (Додатак A — Ознаке), где се налази и индекс појмова.
Многе слике у веб издању су интерактивне: логичким колима можете мењати улазе, чворове графа померати, а Хафманово стабло и аутомат за имејл адресе раде над текстом који сами унесете. Уз уџбеник постоје и алати за исказне формуле (таблице истинитости, нормалне форме, Карноове мапе) и за коначне аутомате.
Уочене грешке и предлоге можете пријавити преко формулара. Ваши коментари су драгоцени за унапређење уџбеника!