Stručni nastavni predmeti

Diskretna matematika

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, 7
0 č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.

Skip to toolbar