Discrete Structures

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.

Discrete structures are a core subject presenting the necessary mathematical topics that are needed to build on in computer science and engineering. It is highly probable that most of the topics will be new to a typical high school graduate, and also the familiar concepts will be studied in a new setting. 
 
Topics include:
  • Formal logic: reasoning, formal proofs in propositional logic, predicates.
  • Set theory: naive approach, basics of counting.
  • Functions and relations: composition of functions, equivalence relations.
  • Number theory: basics, Diophantine equations.
  • Permutations: a primer of an algebraic structure.
  • Graph theory: basics, walks, paths and connectedness, bipartite graphs, trees, Euler and Hamilton graphs, coloring.
  • Recurrence relations.

Coursework consists of weekly homework assignments, midterms and a final exam.