Cilj nastave predmeta Diskretna matematika je ovladavanje konceptima, znanjima i tehnikama koje pripadaju diskretnoj matematici, osposobljavanje da se naučeno primeni u računarstvu i u rešavanju praktičnih problema, razvijanje apstraktnog i kritičkog mišljenja, sposobnosti komunikacije matematičkim pismom i formalnim matematičkim jezikom, povezivanje stečenih znanja i veština sa novim saznanjima i primenama u daljem školovanju.
III razred
(2 časa nedeljno, 74 časa godišnje)
SADRŽAJI PROGRAMA
Logika i skupovi
Iskazi, osnovne logičke operacije. Iskazne formule, iskazna valuacija, tautologije (važni primeri i metode dokazivanja). Potpun sistem veznika, primeri. Disjunktivna normalna forma (DNF) i konjunktivna normalna forma (KNF). Skupovi, jednakost i inkluzija, skupovne operacije. Partitivni skup. Dekartov proizvod. Dokazivanje skupovnih relacija pomoću tautologija. Relacije: graf binarne relacije; relacija poretka (inkluzija); relacija ekvivalencije i klase ekvivalencije (jednakost, logička ekvivalentnost). Bulove algebre, aksiome i primeri (dvočlana, Bulova algebra partitivnog skupa, klase ekvivalencije iskaznih formula sa konačno mnogo iskaznih slova).
Elementarna teorija brojeva
Relacija deljivosti, prosti brojevi (osnovna teorema aritmetike). Euklidov algoritam. Diofantske jednačine. Kongruencije (jednakost ostataka), svojstva, račun ostataka i primene. Sistem linearnih kongruencija.
Kombinatorika
Predmet kombinatorike, pravilo zbira i pravilo proizvoda, formula uključenja i isključenja. Varijacije i permutacije. Kombinacije, binomna formula i binomni koeficijenti. Permutacije sa ponavljanjem. Rekurentne formule i nizovi, jednostavnije diferencne jednačine i njihova primena u kombinatorici.
Grafovi
Pojam, odrednice (čvorovi, grane; petlje) i tipovi grafova (prost, multigraf sa petljama, orjentisan); podgraf, izomorfizam. Stepen čvora, regularani i kompletni grafovi, cikli. Kompletni bipartitni grafovi. Putevi, povezanost; šume, stabla. Šetnje, Ojlerovi grafovi. Planarni grafovi. Problem najkraćeg puta i Dijkstra algoritam. Minimalni skelet i Kraskalov algoritam. Bojenje grafova. Predstavljanje grafa matricama: matrica susedstva i matrica incidencije.