63705 Diskretne strukture

63705 Diskretne strukture

  • Vrsta programa: interdisciplinarni univerzitetni študijski program Upravna informatika 1. stopnja
  • 6 ECTS
  • Tip predmeta: izbirni
  • Število ur predavanj: 45
  • Seminarske vaje: 30
  • Samostojno delo: 105
  • Nosilec: dr. Gašper Fijavž

 

 

1. Cilji in kompetence

  • Zmožnost kritičnega razmišljanja.
  • Razvoj veščin kritičnega, analitičnega in sintetičnega razmišljanja.
  • Cilj predmeta je poglobiti študentovo razumevanje matematične logike in formalnega sklepanja ter študenta seznaniti z osnovami kombinatorike in diskretne matematike.

2. Vsebina predmeta

Predavanja:

  • Naravna števila. Indukcija.
  • Izjavni račun. Resničnostna tabela izjavnega izraza. Konstrukcijsko drevo izjavnega izraza. Nabori izjavnih veznikov. Sklepanje v izjavnem računu. Osnovno o predikatnem računu.
  • Množice, moč množic, funkcije. Osnove preštevanja.
  • Relacije. Lastnosti relacij. Graf relacije. Operacije z relacijami in lastnosti. Ekvivalenčna relacija.
  • Osnove teorije števil. Razširjeni Evklidov algoritem. Linearne diofantske enačbe. Modulska aritmetika.
  • Permutacije. Potenciranje permutacij. Zapis permutacije kot produkt transpozicij. Parnost permutacij.
  • Grafi. Izomorfizem, operacije, družine. Podgrafi, vpeti in inducirani podgrafi. Sprehodi v grafih in povezanost, drevesa, gozdovi. Eulerjev in Hamiltonov problem. Barvanja grafov.
  • Linearne rekurzivne enačbe s konstantimi koeficienti. Homogene in nehomogene.

Vaje:

  • Vaje so deloma avditorne in so namenjene skupinskemu utrjevanju obravnavane snovi z računskimi primeri s pomočjo asistenta. Delno vaje potekajo laboratorijsko, s samostojnim delom študentov z računalnikom. Pri laboratorijskih vajah se uporablja programska oprema za simbolično računanje (Mathematica, npr.).

Domače naloge:

  • Domače naloge so predvidene v tedenskem ritmu in obvezne. Vsebine domačih nalog praviloma sledijo temam iz kontaktnih ur.

3. Temeljna literatura in viri

  • G. Fijavž, Diskretne strukture, Ljubljana, 2014, matematika.fri.uni-lj.si/ds/ds.pdf.
  • V. Batagelj, S. Klavžar: DS1, DMFA, Ljubljana, 1997.
  • V. Batagelj, S. Klavžar: DS2, DMFA, Ljubljana, 2000.
  • R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA, 1997.
  • P. Grossman: Discrete mathematics for computing, Macmillan, 2002.
  • J. L. Hein: Discrete Structures, Logic, and Computability, Jones & Bartlett, 2001.

4. Predvideni študijski rezultati

Znanje in razumevanje:

  • Po zaključku tega predmeta bo študent sposoben izkazati znanje in razumevanje osnovnih principov
  • diskretne matematike, matematične logike in njune uporabe v računalništvu.

Uporaba:

  • Uporaba metod matematične logike in diskretne matematike pri načrtovanju računalniških postopkov in programov.

Refleksija:

  • Spoznavanje matematičnega jezika za konsistentno in natančno opisovanje pojavov in razumevanje odnosa med teoretičnim modelom in njegovo implementacijo na različnih področjih računalništva.

Prenosljive spretnosti - niso vezane le na en predmet:

  • Matematična abstrakcija pojmov in problemov je v računalništvu potrebna in pogosto uporabljana.

5. Metode poučevanja in učenja

Predavanja, vaje z ustnimi nastopi in delom z računalniki, domače naloge. Poseben poudarek je na sprotnem študiju z domačimi nalogami, na samostojnem delu z računalnikom in uporabo programske opreme za simbolično računanje.

6. Načini ocenjevanja

Način (pisni izpit, ustno izpraševanje, naloge, projekt):

  • Sprotno preverjanje (domače naloge, kolokviji) (50 %)
  • Končno preverjanje (izpit) (50 %)

Ocene: 6-10 pozitivno, 1-5 negativno
(v skladu s Statutom UL)