Logic and Discrete Mathematics

You are here

Credits
7.5
Types
Compulsory
Requirements
This subject has not requirements
Department
MAT
Discrete mathematics is the branch of mathematics with a more direct relationship with the theory of computation; In fact, its great development in the last century is due in large part to the onset of computer science.
The course introduces several interrelated subjects - logic, arithmetic, combinatorics and graph theory -, which are the basis of discrete mathematics. The presentation of the topics will emphasize the algorithmic and computational aspects.

Teachers

Person in charge

  • Enric Ventura Capell ( )

Others

  • Anna De Mier Vinué ( )
  • Juan José Rue Perna ( )
  • Marc Noy Serrano ( )

Weekly hours

Theory
3
Problems
1.5
Laboratory
0.5
Guided learning
0.333
Autonomous learning
5

Competences

Technical Competences

Technical competencies

  • CE1 - Skillfully use mathematical concepts and methods that underlie the problems of science and data engineering.

Transversal Competences

Transversals

  • CT5 - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
  • CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.

Basic

  • CB1 - That students have demonstrated to possess and understand knowledge in an area of ??study that starts from the base of general secondary education, and is usually found at a level that, although supported by advanced textbooks, also includes some aspects that imply Knowledge from the vanguard of their field of study.

Generic Technical Competences

Generic

  • CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.

Objectives

  1. To know the language of mathematical logic
    Related competences: CB1, CT6, CE1,
  2. To understand basic arithmetic of integers and polynomials, specially the computational aspects
    Related competences: CG5, CE1,
  3. To know the basic results of enumerative combinatorics
    Related competences: CE1, CG5,
  4. To know the basics of graph theory, with emphasis on algorithmic problems
    Related competences: CT5, CE1, CG5,

Contents

  1. Sets and proofs
    The language of set theory. Demonstrations in mathematics. The induction method.
  2. Propositional and predicate calculus
    Boolean formulas. Assignment and truth tables. Satisfiability. First-order logic.
  3. Integer arithmetics and polynomials
    Divisibility of integers. Maximum common divisor. Congruences Divisibility and congruence of polynomials. Roots and factorization.
  4. Basic enumeration and recurrences
    Permutations, sets, and multisets. Binomial numbers. The principle of inclusion and exclusion. Recurrence equations. Resolution of linear recurrence equations.
  5. Graphs and trees
    Basic concepts of graph theory. Distances and connectivity. Representation and exploration of graphs. Eulerian graphs. Minimal spanning tree: Kruskal and Prim algorithms.
  6. Planarity and colouring
    Planar graphs. Euler's formula. Graph colouring, algorithms.

Activities

Activity Evaluation act


Problem solving


Objectives: 1 2 3 4
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Teaching methodology

In the theory classes the subject is exposed, complementing it with examples and applications. in the problem sessions we'll discuss problems from a list, encouraging the active participation of students.

Evaluation methodology

Midterm exam (40%) and final exam (60%). On the day of the final exam students have the opportunity to resit the midterm.
There will be a retake exam that will substitute 100% of the original grade.

Bibliography

Basic:

Addendum

Contents

No hi ha canvis respecte la informació publicada a la guia docent.

Teaching methodology

No hi ha canvis respecte la informació publicada a la guia docent.

Evaluation methodology

No hi ha canvis respecte la informació publicada a la guia docent.

Contingency plan

El pla de contingència en cas que la situació sanitària forcés el pas a docència no presencial seria el següent: - Els examens es faran presencials (dividint en subgrups i en varios dies si cal) a menys que hi hagi ordre explícita de les autoritats acadèmiques en sentit contrari. Per les classes de teoria: - videos de tablet+veu gravats i penjats a Atenea, corresponents cronològicament a les classes que hauria tocat fer presencialment, i seguint aproximadament el mateix ritme que si fossin presencials. Aquests videos quedaran tots disponibles acumulativament fins a finals de curs per poder ser consultats en qualsevol moment. - sessions de videoconfrència periòdiques (una cada setmana / 15 dies) amb els estudiants interessats per resoldre dubtes i qüestions sobre el temari de l'assignatura, i per fer exercicis teòrics. - Disponibilitat del professor per resoldre dubtes concrets via e-mail. Per les classes de problemes: - Combinació de videos gravats i de videoconferències per a resoldre problemes de la llista, equivalents també (en quan a hores i a ritme) a les classes que hauria tocat fer presencialment. S'aniran alternant els dos tipus (video gravat, i videoconferències síncrones en l'horari de classe) segons l'evolució de la situació, necessitats puntuals, i preferència dels estudiants. - Disponibilitat del professor per resoldre dubtes concrets via e-mail.