Cilj nastave predmeta Diskretna matematika je: usvajanje osnovnih matematičkih znanja koja omugućavaju praćenje razvoja računarstva, kao i šematizacija situacija koje se rešavaju na efikasan način pomoću grafova.
III razred
(2 časa nedeljno, 70 časova godišnje)
SADRŽAJI PROGRAMA
UVOD (6 časova):
- skupovi i operacije sa skupovima , podskupovi, određivanje podskupova,
- preslikavanja,
- operacije, relacije, relacija ekvivalencije, relacija poretka, klase ekvivalencije, proširivanje relacija do relacije ekvivalencije;
OSNOVI MATEMATIČKE LOGIKE (14 časova):
- Iskazi, iskazne formule, interpretacija iskaznih formula, tautologije
- Konjuktivna i disjunktivna normalna forma, minimizacija formi
- Logičke posledice
- Metod rezolucije
- DPLL algoritam
- Bulova algebra
- Termi, predikati, predikatske formule, modeli i kontramodeli formula, valjane formule
TEORIJA BROJEVA (8 časova):
- Prosti brojevi, provera da li je broj prost, određivanje prostih brojeva (Eratostenovo sito)
- NZD i NZS, Euklidov algoritam
- Faktorizacija broja, Fermaova metoda faktorizacije
- Celobrojna rešenja jednačine Ax+By=C
- Kongruentne jednačine
- Sistemi kongruentnih jednačina, Kineska teorema o ostacima
- Verižni razlomci
ELEMENTI KOMBINATORIKE (8 časova)
- Principi prebrojavanja, princip proizvoda i zbira, princip uključenja – isključenja
- Permutacije, generisanje permutacija, određivanje sledeće permutacije
- Kombinacije sa i bez ponavljanja, generisanje kombinacija zadate dužine
- Varijacije sa i bez ponavljanja, generisanje varijacija zadate dužine
MATRICE I DETERMINANTE (8 časova):
- Pojam, operacije sabiranje, množenje skalarom, množenje matrica
- Determinante, računanje, Sajrusovo pravilo, razvoj po kofaktorima
- Primena matrica i determinanti, određivanje inverzne matrice, rešavanje sistema jednačina
GRAFOVI: (20 časova)
- Definicija grafa, osnovni pojmovi
- Šematizacija situacije, uređenost, stepen čvora, orijentacija grafa, put i ciklični put u grafu, komponente povezanosti grafa, težinski graf
- Načini predstavljanja grafa
- Problem bojenja grafova: hromatski polinom i hromatski broj
- Pretraga grafa: pretraga u dubinu i pretraga u širinu
- Određivanje najkraćeg puta
- Dijkstrin algoritam
- Flojd Varšalov algoritam
- Minimalno drvo razapinjanja (Primov algoritam)
- Primeri primene grafa
NAPOMENA: Za ovaj predmet predviđena je izrada dva pismena zadatka (po jedan u svakom polugodištu) u trajanju od po dva časa. Po jedan čas je predviđen za ispravak pismenih zadataka.