63705 Discrete Structures

63705 Discrete Structures

  •  Study programme and level: Interdisciplinary University Study Programme in Administrative Information Science - 1st Cycle
  • 6 ECTS
  • Course type: Elective
  • Lectures: 45
  • Tutorial: 30
  • Individual work: 105
  • Lecturer: Gašper Fijavž, PhD

 

 

1. Objectives and competences

  • Ability of critical thinking.
  • Developing skills in critical, analytic and synthetic thinking.
  • The object of the course is to deepen student’s understanding of mathematical logic and formal reasoning, together with the basics of discrete mathematics.

2. Content

Lectures:

Natural numbers: induction principle.

  • Propositional calculus: truth tables, construction trees, complete sets of connectives, formal reasoning, basics of predicate calculus.
  • Naive set theory: operations, mappings, basics of counting.
  • Relations: properties and operations, equivalence relations, partial orders. Graph of relation.
  • Number theory: extended Eucledian algorithm, linear Diophantine equations, modular arithmetic.
  • Permutations: computing with permutations, parity, conjugate permutations.
  • Graph theory: isomophism, operations, graph families, vertex degrees, subgraphs, connectivity, trees and forests, Euler and Hamilton graphs, graph colorings.
  • Linear recurrence relations with constant coefficients. Homogeneous and nonhomogeneous.

Exercise groups:

  • Exercise group time is in part devoted to the classical blackboard approach; the students solve computational problems with some help of TA. In part of the exercise groups the students individually solve computerized versions of problems using symbolic computation software.  

Homework:

  • Homework assignments are distributed on a weekly basis. The assignments are obligatory. Their purpose is to prepare the students for continuously working on the DS topics.

3. Readings

  • 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. Intended learning outcomes

Knowledge and understanding:

  • After successfully finishing the course a student will master the basic principles of discrete mathematics, mathematical logic and their application in CS.

Application:

  • Using mathematical logic and discrete mathematics in algorithm design.

Reflection:

  • Using mathematical formalization to accurately and consistently describe the relation between a theoretical model and its implementation.

Transferable skills:

  • Mathematical abstraction is frequently needed in all areas of computer and information science.

5. Learning and teaching methods

Lectures, exercise groups, homework assignments. The focus lies in continuous work with home assignments, using computer and symbolic computation software.

6. Assessment

Type (examination, oral, coursework, project):

  • Continuing (homework, midterm exams) (50 %)
  • Final (written exam) (50 %)

Grading: 6-10 pass, 1-5 fail.