• Šifra predmeta:63705
  • Kreditne točke:6
  • Semester: zimski
  • Vsebina

Z matematiko je križ. Diskretne strukture so matematika. Zato so z Diskretnimi strukturami tudi same sitnosti.

Ah, šalo na stran. Predstavimo raje, kaj bi zamudili, če bi se Diskretnim strukturam izognili. Če vemo, da je 1+1=2 in 2+2=5, potem bi morali verjeti tudi, da je 3+3=7, mar ne? Sešteli bi lahko obe "enačbi", na primer. Toda v tem primeru moramo verjeti tudi, da so vse krave iste barve. Tega pa si najbrž ne bi mislili.

Je težko opravljati posel receptorja v neskončnem hotelu? Tudi če je poln in na obisk pridejo dodatni gosti, jih vedno lahko razporedimo po prostih sobah. Skrbimo lahko tudi, da je hotel polno zaseden, čeprav se lepega dne zaradi slabega vremena (le kako je lahko lepega dne slabo vreme?) domov odpravi neskončno mnogo gostov.

Včasih so v dvornih parkih vrtnarji skrbno prirezovali labirinte iz žive meje (ponekod to počno še danes). Bi se znali iz takšnega labirinta rešiti? Tudi če vas v njegovo sredino spustijo z žerjavom? Pri Diskretnih strukturah se naučimo, kako iz takšnega labirinta pobegnemo. Pa četudi je trda tema. Je Rubikovo kocko težko pravilno sestaviti? Z nekaj vaje se lahko tega naučimo in jo z vrtenjem raznobarvnih kvadratkov vseeno spravimo v red. Kaj pa, če odlepimo dve raznobarvni nalepki na takšni kocki in ju prestavimo? Bi verjeli, da tako "popravljene" kocke nikakor ne morete znova pravilno sestaviti, pa če jo še tako besno vrtite? Pri Diskretnih strukturah bi znali to pokazati, če bi imeli na voljo še kakšno dodatno uro.

Marsikdo med nami ima z matematiko težave, tudi računalniki. Če računski stroj dovolj dolgo sešteva enice, se bo slej ko prej začel motiti. Diskretne strukture predstavljajo tisti del matematike, ki se zelo dobro razume z računalniki. Ponudile mu bodo različne načine računanja, pri katerih se ne bo nikoli zmotil, kljub vsemu pa bo znal kaj uporabnega izračunati.

Pa še bolj zares.

  • Matematična logika: sklepanje v izjavnem računu, osnove predikatnega računa.
  • Množice: osnove kombinatoričnega preštevanja
  • Relacije in funkcije: ekvivalenčne relacije, komponiranje funkcij.
  • Relacije: ozadje, ekvivalenčne relacije.
  • Teorija grafov: osnovne definicije, sprehodi, poti in povezanost, dvodelni grafi, drevesa, Eulerjevi grafi, barvanje grafov.
  • Osnove teorije števil: razširjeni Evklidov algoritem, diofantske enačbe.
  • Linearne rekurzivne enačbe: osnove

Študenti opravljajo domače naloge v tedenskem ritmu, kolokvije iz praktičnih nalog in končni izpit iz teorije.

  • Študijski programi
  • Porazdelitev ur na semester
45
ur
predavanj
30
ur
avditornih vaj
  • Izvajalci
Nosilec predmeta
Prostor:R3.09 - Kabinet
Asistent
Prostor:R3.26 - Laboratorij LMMRI