Discrete Structures

Weekly outline

• 

  General

  Diskretne strukture VSŠ 63705

  • Osnovni podatki o predmetu Page
  • Obveznosti študenta Page
  • Gradiva Page
  • References in English Page
  • Tutorske ure Page
  • Forum novic
  • Forum vprašanj in odgovorov
  • Izvedba oddaljenih izpitov Page
  • Kako naj skeniram svoj izdelek? Assignment
  • DS VSP izpit, 2.2.2021 (računski del) Assignment
  • DS VSP, računski del izpita, 02.02.2021 - rešitve File Uploaded 7/02/21, 14:43
  • DS VSP izpit, 2.2.2021 (računski del), utemeljene pritožbe Assignment
  • (podaljšan čas) DS VSP predrok, teoretični del Assignment

    Restricted Not available unless any of:

    • Your Email address is al6878@student.uni-lj.si
    • Your Email address is mk8054@student.uni-lj.si
    • Your Email address is jz6085@student.uni-lj.si
  • Vaje DS VSP, torek 8.15 - 10.00, 10.15 - 12.00 ali 12.15 - 14.00 Zoom meeting
  • Vaje DS VSP, sreda 13:15 - 15:00 ali petek 11:15 - 13:00 Zoom meeting
  • Predavanja, petek 13:15-16:00 Zoom meeting
  • Vprašanja za teoretični izpit - 1. del File Uploaded 23/11/20, 10:21
  • Seznam tematik za teoretični del izpita File Uploaded 4/01/21, 08:14
  • Poskusni kolokvij File Uploaded 1/12/20, 18:42
  • Rešitve poskusnega kolokvija File Uploaded 1/12/20, 19:13
  • Rešitve in točkovnik računskega dela predroka File Uploaded 16/01/21, 20:18
  • Rešitve in točkovnik teoretičnega dela predroka File Uploaded 16/01/21, 19:34
  • Rešitve in točkovnik računskega dela prvega izpitnega roka File Uploaded 23/01/21, 18:27
  • Rešitve in točkovnik teoretičnega dela prvega izpitnega roka File Uploaded 23/01/21, 18:25
  • Rešitve in točkovnik računskega dela drugega izpitnega roka File Modified 7/02/21, 14:41
  • Rešitve in točkovnik teoretičnega dela drugega izpitnega roka File Uploaded 7/02/21, 14:31
  • Rezultati drugega roka File Uploaded 7/02/21, 14:34
• 

  5 October - 11 October

  Predavanja: Matematična indukcija. Izjave, izjavni vezniki, izjavni izrazi, resničnostna tabela, enakovredni izjavni izrazi.

  Lectures: Mathematical induction (pages 5-7); Introduction into propositional logic: atoms, logical connectives, logical formulas, truth tables, equivalence of formulas (pages 95-99).
  

  
  

  • 1. predavanja - izročki File Uploaded 6/10/20, 20:51
  • 1. del predavanj: Matematična indukcija URL
  • 2. del predavanj: Izjave in izjavni vezniki URL
  • 3. del predavanj: Izjavni izrazi in enakovrednost URL
• 

  12 October - 18 October

  Predavanja: Zakoni izjavnega računa. DNO in KNO. Polni nabori izjavnih veznikov.
  

  Lectures: Laws of propositional logic (pages 11-15); Disjunctive and conjuctive normal form (pages 4-6); Functionally complete sets of logical operators (pdf; the proof of Theorem 2.7 is not required). 

  • Naloge za vaje, 2. teden File
  • Rešitve (nekaterih) nalog z vaj, 16.10.2020 File Uploaded 17/10/20, 09:38
  • Posnetek vaj, petek 16.10., 11:15-13:00 URL
  • Domača naloga, 2. teden Quiz
  • 2. predavanja - izročki File Uploaded 15/10/20, 17:49
  • Zakoni izjavnega računa File
  • 1. del predavanj: Zakoni izjavnega računa URL
  • 2. del predavanj: Disjunktivna normalna oblika URL
  • 3. del predavanj: Konjunktivna normalna oblika URL
  • 4. del predavanj: Polni nabori izjavnih veznikov URL
• 

  19 October - 25 October

  Predavanja: Sklepanje v izjavnem računu. Formalizacija sklepov, definicija pravilnega sklepa, pravila sklepanja, dokaz pravilnosti sklepa, pomožni sklep - sklep s protislovjem. 

  Lectures: Logical inference - formalization, rules of inferece, derivation of rules (pages 100-104), proof by contradiction (section 8 - on this link you can freely download the book).

  • Naloge za vaje, 3. teden File
  • Rešitve (nekaterih) nalog z vaj, 20.10.2020 File Uploaded 24/10/20, 06:16
  • Rešitve (nekaterih) nalog z vaj, 23.10.2020 File Uploaded 24/10/20, 08:03
  • Posnetek vaj, torek 20.10. URL
  • Posnetek vaj, petek 23.10., 11:15-13:00 URL
  • Domača naloga, 3. teden Quiz
  • 3. predavanja - izročki File Uploaded 22/10/20, 16:12
  • Posnetek predavanj, 23.10.2020 URL
  • Neobvezen kviz: Izjavni račun Quiz
• 

  26. oktober - 1. november

  Predavanja: Pogojni sklep, sklep z analizo primerov. Predikatni račun - jezik predikatnega računa, izjavne formule, doseg kvantifikatorjev, vezane in proste spremenljivke.

  Lectures: Proof by conditional derivation (section 6.2), proof by cases (explained at the bottom of section 3.2). Predicate logic: predicates (link); universe of discourse, universal and existential quantifier, free and bound variables, scope of quantifier, order of quantifiers (link to all afforementioned topics), well-formed formula (link).

  
  

  • Naloge za vaje, 4. teden File
  • Pravila sklepanja File
  • Domača naloga, 4. teden Quiz
  • Rešitve nalog z vaj, 27.10.2020 File Uploaded 28/10/20, 17:31
  • Posnetek vaj, 27.10.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 28.10.2020 File Uploaded 31/10/20, 15:16
  • Posnetek vaj, sreda 28.10., 11:15-13:00 URL
  • 4. predavanja - izročki File Uploaded 17/11/20, 16:32
  • Posnetek predavanj, 30.10.2020 URL
  • Neobvezen kviz: izjavni in predikatni račun Quiz
• 

  2 November - 8 November

  Predavanja: Interpretacija izjavne formule, enakovrednost izjavnih formul, preimenovanje spremenljivk, zakoni predikatnega računa, preneksna normalna oblika.

  Lectures: Interpretation of the formula (link), equivalence of formulas (link), renaming of variables, laws of predicate logic, prenex normal form (link to the notes for the last three topics).

  • Pomožni sklepi File
  • Naloge za vaje, 5. teden File
  • Domača naloga, 5. teden Quiz
  • Rešitve nalog z vaj, 3.11.2020 File Uploaded 4/11/20, 17:54
  • Posnetek vaj, 3.11.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 04.11.2020 File Uploaded 7/11/20, 22:52
  • Posnetek vaj, sreda 04.11., 11:15-13:00 URL
  • 5. predavanja - izročki File Uploaded 6/11/20, 12:50
  • Posnetek predavanj, 06.11.2020 URL
  • Predavanja 06.11.2020, zapiski File Uploaded 6/11/20, 19:28
  • Neobvezen kviz: predikatni račun Quiz
• 

  9 November - 15 November

  Predavanja: Množice, Russellov paradoks, univerzalna množica, enakost množic, podmnožice, osnovne operacije z množicami ($\cap, \cup, +, \setminus, ^c$), lastnosti komplementiranja, prednostni red operacij, lastnosti operacij z množicami, potenčna množica, kartezični produkt.
  

  Lectures: Sets, Russell's paradox, equality and inclusion of sets, basic operations with sets ($\cap, \cup, +, \setminus, ^c$), order of operations, laws for operations with sets, cartesian product and properties. (notes, laws of set theory, on this link there are some proof of some laws of set theory).

   
  

  • Zakoni predikatnega računa. File
  • Naloge za vaje, 6. teden File
  • Rešitve nalog z vaj 10.11.2020 File Uploaded 13/11/20, 18:05
  • Posnetek vaj, 10.11.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 11.11.2020 File Uploaded 22/11/20, 07:00
  • Posnetek vaj, petek 13.11., 11:15-13:00 URL
  • Domača naloga, 6. teden Quiz
  • 6. predavanja - izročki File Uploaded 13/11/20, 12:33
  • Posnetek predavanj, 13.11.2020 URL
  • Zapiski predavanj File Uploaded 13/11/20, 18:58
• 

  16 November - 22 November

  Predavanja: Lastnosti kartezičnega produkta, družina množic, unija in presek družine, pokritje in razbitje množice. Definicija relacije, grafična predstavitev relacij, lastnosti relacij, operacije z relacijami.
  

  Lectures: Properties of cartesian product (link), family of sets, union and intersection of the family, covering of a set. (link to last three topics) Relations: definition and examples, graphical representation (link to last two topics), properties of relations (link), operations with relations (link).
  

  
  

  • Naloge za vaje, 7. teden File
  • Rešitve nalog z vaj 17.11.2020 File Uploaded 20/11/20, 14:46
  • Posnetek vaj, 17.11.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 18.11.2020 File Uploaded 22/11/20, 07:02
  • Posnetek vaj, sreda 18.11., 13:15-15:00 URL
  • Domača naloga, 7. teden Quiz
  • Enakosti z množicami. File
  • 7. predavanja: izročki File Uploaded 20/11/20, 13:03
  • Posnetek predavanj, 20.11.2020 URL
  • Zapiski predavanj File Uploaded 23/11/20, 10:13
• 

  23 November - 29 November

  Predavanja: Potence relacij, tranzitivna in tranzitivno-refleksivna ovojnica relacije, ekvivalenčna relacija, ekvivalenčni razredi, faktorska množica.
  

  Lectures: Powers of relations, transitive closure and reflexive-transitive closure (pages 28-30), equivalence relation (link), equivalence classes, factor set. (link)

  • Naloge za vaje, 8. teden File
  • Rešitve nalog z vaj, 24.11.2020 File Uploaded 27/11/20, 08:11
  • Posnetek vaj, 24.11.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 25.11.2020 File Uploaded 30/11/20, 23:06
  • Posnetek vaj, sreda 25.11., 13:15-15:00 URL
  • Domača naloga, 8. teden Quiz
  • 8. predavanja: izročki File Modified 27/11/20, 19:24
  • Posnetek predavanja, 27.11.2020 URL
  • Zapiski predavanj File Uploaded 27/11/20, 20:14
  • Kolokvij 1, 2013, 3. naloga File Uploaded 30/11/20, 08:55
  • Naloge za vajo Quiz
• 

  30 November - 6 December

  Predavanja: Preslikave, lastnosti preslikav, inverzna preslikava, kompozitum preslikav.

  Lectures: Mappings (link), properties (link), inverse mapping (link), composition of functions and properties (link).

  • Naloge za vaje, 9. teden File
  • Rešitve nalog z vaj, 1.12.2020 File Uploaded 4/12/20, 15:04
  • Posnetek vaj, 1.12.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 4.12.2020 File Uploaded 5/12/20, 07:19
  • Posnetek vaj, petek 4.12., 11:15-13:00 URL
  • Domača naloga, 9. teden Quiz
  • Deveti sklop izročkov File Modified 4/12/20, 20:57
  • Posnetek predavanj, 04.12.2020 URL
  • Zapiski predavanj File Uploaded 4/12/20, 21:00
• 

  7 December - 13 December

  Predavanja: Moč končnih množic. Dirichletov princip. Načelo vključitev in izključitev. Definicija grafa, stopnja točke, lema o rokovanju, grafična zaporedja, požrešna metoda, izomorfizem grafov.
  
  Lectures: Cardinality of finite sets. (link) Pigeonhole principle. (link) Principle of inclusion and exclusion. (link) Definition of a graph (link), degree of a vertex, handshaking lemma (Theorem 5.1.1), graphical sequences (link), isomorphism of graphs (link)
  

  • Naloge za vaje, 10. teden File
  • Rešitve nalog z vaj, 8.12.2020 File Uploaded 11/12/20, 17:06
  • Posnetek vaj, 8.12.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 9.12.2020 File Uploaded 15/12/20, 22:59
  • Posnetek vaj, sreda 9.12., 13:15-15:00 URL
  • Domača naloga, 10. teden Quiz
  • Deseti sklop izročkov File Modified 11/12/20, 18:42
  • Posnetek predavanj, 11.12.2020 URL
  • Zapiski predavanj File Uploaded 11/12/20, 18:49
• 

  14 December - 20 December

  Predavanja: Družine grafov (polni in prazni grafi, polni dvodelni grafi, cikli, poti). Podgrafi. Sprehod, pot, obhod, cikel. Povezanost in komponente za povezanost. Razdalja v grafu. Karakterizacija dvodelnih grafov. Eulerjev problem.
  
  Lectures: Families of graphs (complete and empty graphs, complete bipartite graphs, cycles, paths). (Definition 4) Subgraphs. (link) Walk, path, closed walk, cycle. Connected graphs and components. Distance in graphs. (Definition 3) Characterization of bipartite graphs. (link) Euler's problem (link).
  

  • Naloge za vaje, 11. teden File
  • Rešitve (nekaterih) nalog z vaj, 16.12.2020 File Uploaded 16/12/20, 18:36
  • Posnetek vaj, sreda 16.12., 13:15-15:00 URL
  • Rešitve nalog z vaj, 15.12.2020 File Uploaded 18/12/20, 06:47
  • Posnetek vaj, 15.12.2020 URL
  • Domača naloga, 11. teden Quiz
  • Enajsti sklop izročkov File Modified 18/12/20, 20:14
  • Posnetek predavanj, 18.12.2020 URL
  • Zapiski predavanj File Uploaded 21/12/20, 07:51
• 

  21 December - 27 December

  Predavanja: Hamiltonovi grafi, barvanja grafov.
  

  Lectures: Hamiltonian graphs (link), chromatic number (link).

  • Naloge za vaje, 12. teden File
  • Rešitve nalog z vaj, 22.12.2020 File Uploaded 23/12/20, 17:23
  • Posnetek vaj, 22.12.2020 URL
  • Rešitve (nekaterih) nalog z vaj, 23.12.2020 File Uploaded 3/01/21, 22:35
  • Posnetek vaj, sreda 23.12., 13:15-15:00 URL
  • Bonus domača naloga, 12. teden Quiz
  • 12. sklop izročkov File Uploaded 24/12/20, 14:13
  • 1. del predavanj: Hamiltonovi grafi URL
  • 2. del predavanj: (Ne)hamiltonskost Grotzschevega in Petersenovega grafa URL
  • 3. del predavanj: Barvanje grafov URL
  • 4. del predavanj: Kromatično število Petersenovega in Grotzschevega grafa URL
• 

  4 January - 10 January

  Srečno Novo leto!

  Predavanja: Razširjeni Evklidov algoritem, linearne diofantske enačbe.

  Lectures: Extended Euclidean algorithm (link), linear diophantine equations (link).

  • Naloge za vaje, 14. teden File
  • Domača naloga, 14. teden Quiz
  • Posnetek vaj, 5.1.2021 URL
  • Rešitve nalog z vaj, 5.1.2021 File Uploaded 7/01/21, 20:20
  • Rešitve (nekaterih) nalog z vaj, 6.1.2021 File Uploaded 7/01/21, 19:11
  • Posnetek vaj, sreda 6.1., 13:15-15:00 URL
  • 13. sklop izročkov File Modified 9/01/21, 00:24
  • Posnetek predavanj, 08.01.2021 URL
• 

  11 January - 17 January

  
  

  • Naloge za vaje, 15. teden File
  • Rešitve nalog z vaj, 12.1.2021 File Uploaded 14/01/21, 08:20
  • Posnetek vaj, 12.1.2021 URL
  • Rešitve (nekaterih) nalog z vaj, 13.1.2021 File Uploaded 15/01/21, 22:48
  • Posnetek vaj, sreda 13.1., 13:15-15:00 URL
  • Bonus domača naloga, 15. teden Quiz
  • Kviz za vajo Quiz