• Šifra predmeta:63203
  • 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 bomo pokazali, zakaj je to res tako. 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 zares.

  • Izjavni račun: sklepanje v izjavnem računu.
  • Predikatni račun: osnove.
  • Množice: osnove kombinatoričnega preštevanja.
  • Funkcije: komponiranje funkcij.
  • Relacije: delna in linearna urejenost, ekvivalenčne relacije.
  • Osnove teorije števil: razširjeni Evklidov algoritem, diofantske enačbe, Eulerjeva funkcija, kongruence in modularna aritmetika.
  • Permutacije: osnovni zgled algebrske strukture.
  • Teorija grafov: osnovne definicije, sprehodi, poti in povezanost, dvodelni grafi, drevesa, Eulerjevi grafi, Hamiltonovi grafi in barvanja.

Študenti opravljajo kolokvije iz praktičnih nalog in končni izpit iz teorije. Domače naloge, enakomerne časovne zahtevnosti, so objavljene tedensko.

  • Š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
Asistent
Prostor:R3.26 - Laboratorij LMMRI