Discrete Mathematics (MATD)

The overall aim of this subject is to introduce students to the concepts and techniques involved in discrete mathematics and algebra that, due to their ubiquity in the world of new technologies, form part of the basic training of any engineer in information technology.

Knowledges

1. Learn the basic principles of enumeration: principles of identify, product, Pigeon-hole Principle, inclusion-exclusion. Learn the algebra of generating functions.
   
   
   
   Learn how to express recurrences in terms of generating functions.
2. Learn graph and digraph structure as a mathematical model and the various forms that graphs may take.
   
   
   
   Learn tree characterisations and obtain tree generators at minimum cost.
3. Learn the characterisations of Eulerian graphs and, where applicable, how to obtain a Eulerian path where one exists. Learn the problem posed by Hamiltonian circles, and associated difficulties.
4. Learn the concepts of flux, connectivity, and pairing, and the following basic theorems: maximum flow/minimum cut theorem, Menger theorems, Hall theorems.
5. Learn the structure of a field in terms of Z_p (integer module, prime p) and the ring of polynomials with coefficients Z_p. Learn what an irreducible polynomial is and learn the single factorisation theorem. Learn how to construct finite field and ascertain their existence and unicity.

Abilities

1. Ability to apply the basic principles of enumeration. Ability to work with generating functions. Ability to frame enumeration problems in terms of recurrences. Ability to solve recurrences by employing generating functions.
2. Ability to model problems in terms of graphs and digrafs. Learn how to use the relationships linking the parameters of a planar graph in order to deduce the values for some parameters from the values of others.
   
   
   
   Ability to calculate the number of tree generators in a connection graph. Ability to apply research algorithms in depth and breadth to obtain tree generators. Ability to apply Prim algorithms and Kruskal algorithms to obtain tree generators at minimum cost.
3. Ability to apply algorithms to obtain a Eulerian cycle and a Eulerian circuit. Ability to apply sufficient Hamiltonian conditions to simple examples. Ability to operate with cycles.
4. Ability to apply the Ford and Fulkerson to obtain maximum flux.
   
   
   
   Ability to apply Menger theorems and Hall theorems in simple situations.
5. Learn how to operate Z_p with p prime, and in particular, how to calculate inverse matrices.
   
   
   
   Ability to operate with polynomials with Z_p coefficients. Ability to construct finite bodies.
   
   
   
   Ability to operate with finite bodies, using the polynomial form of its elements, and using discrete logarithms. Ability to operate with polynomials in a finite body.

Competences

1. Critical, logical-mathematical reasoning.
2. Ability to apply techniques for constructing logical-mathematical demonstrations.
3. Ability to transform informal problems into formal ones and vice versa.
4. Ability to apply mathematical knowledge and logic in solving problems.
5. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.

Theory classes will take the form of lectures, which may include the use of an overhead slide projector or computer demonstrations.



The classes of problems will be of a participatory nature, with students explaining previously set problems and discussing other previously set problems in class.

The evaluation is continuous, based on the following three exams:

P1: covering the initial part of the course,
P2: covering the middle part of the course,
P3: covering the final part of the course.

The final grade is N= 0.2*P1+0.4*P2+0.4*P3 (where P1,P2,P3
are grades over 10).

The students who do not want to follow the continuous evaluation or wish
to renounce to it, must take an exam covering the whole course, and
their final grade will be the one obtained in this exam. The student
must inform the coordinator about the renounce by the end of the
classes, following the procedure that will be posted on the Raco.

• Francesc Comelles, Josep Fābrega, Anna Sānchez, Oriol Serra. Matemātica Discreta, Edicions UPC, 1994.
• Norman L. Biggs Matemātica Discreta, Vicens-Vives, 1994.
• Ralph P. Grimaldi Matemáticas Discreta y Combinatoria, Addison Wesley Iberoamericana, 1997.

• Josep M. Brunat Combinatōria i teoria de grafs, Edicions UPC, 1997.
• Joan Trias Matemātica Discreta. Problemes resolts., Edicions UPC, 2001.
• Jiri Matousek, Jaroslav Nesetril Invitation to Discrete Mathematics, Clarendon Press, Oxford., 1998.
• Kenneth H. Rosen Matemática discreta y sus aplicaciones, McGraw Hill, 2004.

Understand operations with and relationships in sets: union, intersection, difference, Cartesian product, inclusion.

Understand the various applications of sets.

Ability to count combinations and permutations (with and without repetition).

Understand the basic properties of binomial numbers and how to calculate them.

Know how to calculate the GCD (Greatest Common Denominator) of integers and Bezout identity coefficients using Euclides" algorithm.

Know how to calculate the products of matrices and how to calculate determinants.

AL is a prerequisite for taking this course.