General information


Subject type: Basic

Coordinator: Adso Fernández Baena

Trimester: Third term

Credits: 6

Teaching staff: 

Carles Bonet Papell

Skills


Basic skills
  • B1_That students have demonstrated knowledge and understanding in a field of study that is based on general secondary education, and is accustomed to finding at a level that, although with the support of advanced textbooks, also include some aspects that involve knowledge from the forefront of your field of study

     

  • B3_Students have the ability to gather and interpret relevant data (usually within their area of ​​study), to make judgments that include reflection on relevant social, scientific or ethical issues

     

Specific skills
  • EFB1_Ability to solve mathematical problems that may arise in engineering. Ability to apply knowledge about: linear algebra, differential and integral calculus, numerical methods, numerical algorithms, statistics and optimization

     

  • EFB3_Ability to understand and master the basic concepts of discrete mathematics, logic, algorithms and computational complexity, and their application for solving engineering problems

     

Transversal competences
  • T1_That students know a third language, which will be preferably English, with an adequate level of oral and written form, according to the needs of the graduates in each degree

     

Description


Discrete mathematics studies mathematical structures that are intrinsically discrete, that is, they are not continuous. For example the line of real numbers is continuous as they vary smoothly (we can not say which real number comes after another, for example we do not know which number goes after 1,0) whereas the line of integers is discrete already that we can clearly distinguish their values ​​(after 1 comes 2). In this subject we will study propositional logic and graph theory which are two disciplines widely used in the field of computing. Logic is used in programming, in fact there is the paradigm of logical programming in the same way that there is the imperative and functional, in databases, in the design and verification of systems and in artificial intelligence between d others. In the case of graphs they are a mathematical structure widely used in computing (and other disciplines) to represent problems, data, concepts and their interrelationships. They are easily programmable structures of which many mathematical properties are known that can be used to validate the correctness of the proposed solution to computational problems. We will also study integers, congruent integers, and congruent equations that give rise to modern message encoding techniques.

This subject has methodological and digital resources to make possible its continuity in non-contact mode in the case of being necessary for reasons related to the Covid-19. In this way, the achievement of the same knowledge and skills that are specified in this teaching plan will be ensured.

Learning outcomes


At a general level, this subject contributes to the following learning outcomes specified for the subject to which it belongs (Scientific foundations):

  • Get acquainted with the language and mathematical logic and know its applications in the field of computer science. Know how to accurately express mathematical concepts. Be able to understand a demonstration and perform demonstrations using various methods.
  • Know the graphs as an abstract model of binary relationship and their possible applications in the field of computer science
  • Know the properties of integers and modular integers, and know how to operate and solve equations in these sets 

At a more specific level, at the end of the course the student must be able to:

  • LO1: Formalize natural language with sentences 
  • LO2: Solve (in the sense of logic) reasoning using the logic of sentences
  • LO3: Know the properties of congruent integers
  • LO4: Solve congruent linear equations 
  • LO5: Describe graphs as useful mathematical structures for modeling problems
  • LO6: Implement algorithms for graph paths
  • LO7: Solve problems using graph theory
  • LO8: Formally demonstrate the correctness of algorithms on graphs

Working methodology


All the theoretical concepts of the subject will be exposed in theory classes (large groups). In these classes, and at the discretion of the teachers, exercises and problems of a more practical nature will also be solved. Likewise, and always at the discretion of the teachers, students may be asked to solve, individually or in groups, short problems and / or exercises. These activities, brief and optional, will serve the student as a tool for self-assessment of their achievement of the contents of the subject and can be used by the teacher to make decisions about the final grade of the student good and never to the detriment of the numerical grade calculated according to the grading system specified by the subject.

 

Contents


  1. Statement logic
    1. Statement logic and its language.
    2. Formalization Interpretation of statements
    3. Categorization of statements (tautologies, contradictions and contingencies)
    4. Categorization of sets of statements (consistent and inconsistent)
    5. Valid and invalid reasoning.
    6. Counterexamples
    7. Normal forms
    8. The method of resolution
    9. Linear Resolution
  2. Integers
    1. Properties and divisibility
    2. Congruent integers
    3. Linear congruence equations
  3. Graphs and digraphs
    1. Basic definitions
    2. Matrix and list representation
    3. Roads, connectivity and distance
    4. Isomorphism between graphs
    5. Routes in depth and width
    6. Digraphs and DAGs
    7. Topological arrangement
    8. Minimal expansion trees: Prim and Kruskal algorithms
    9. Shorter paths: Dijkstra's algorithm
    10. Shorter paths: Bellman-Ford algorithm

Learning activities


A series of activities of an eminently practical nature (short exercises, problems ...) are made available to students, which are the basis of the learning activities of the subject. These activities will have to be solved by the students, often in a non-contact way, following the instructions of the teachers and will also be worked on in class. Although these activities will be optional (teachers will not individually verify the performance by students), they will be essential to achieve the theoretical and practical knowledge of the subject.

In order to gather evidence of the achievement of the expected learning outcomes, the following evaluative activities will be carried out:

Written test 1: Individual test of practical application (solution of exercises and problems) of the theoretical concepts and practical procedures of logic of statements and predicates and of integers. (Evidence of learning outcomes RA1 - RA4 and related to competences EFB1, EFB3, B1 and B3)

Written test 2: Individual test of practical application (solution of exercises and problems) of the theoretical concepts and practical procedures of the theory of graphs (Evidence of the learning results RA5 - RA8 and related to the competence EFB3)

Problem solving types: Students will perform exercises proposed by the teacher. These exercises can be presented in class and will be done individually or in groups according to the teacher's instructions. These problems aim to help the student to understand the basic concepts of discrete mathematics, and to detect deficiencies in one's own knowledge to overcome them with the help of classmates and the teacher. (Related to all EFB1, EFB3, B1 and B3 learning outcomes and competencies)

Implementation of algorithms on graphs: Students will perform algorithm programming exercises on graphs. The aim is to consolidate knowledge of graph theory, recognize the link between graph theory and its practical application, as well as detect gaps in one's own knowledge to overcome them with the help of classmates and the teacher. (Related to RA5 - RA8 and competences EFB1, EFB3, B1 and B3)

The following are the most important aspects of each competence assigned to the subject:

  • B1: problem solving within their area of ​​study.
  • B3: gather and interpret information relevant to the subject
  • EFB1: solving mathematical problems 
  • EFB3: master basic concepts of discrete mathematics, logic, algorithms and computational complexity 
  • T1: third language

In order to pass (pass) the assessment activities, students will have to demonstrate

  • That they have acquired the theoretical knowledge related to the contents of the subject and that their understanding allows them to put them into practice [MECES-2 point a, point c]
  • That they can develop solutions to problems that, although they are similar to others seen above, present aspects that are new [MECES- 2 point f]

Evaluation system


The final grade is the weighted sum of the grades of the activities:

ACTIVITY and WEIGHT

  1. Written Test I 45% - 50%
  2. Written Test II 45% - 50%
  3. Problem solving type 0% - 5%
  4. Implementation of algorithms on graphs 0% - 5%

In order to pass the subject, the mark of the two written tests will not be less than 3

Problem solving and implementation of algorithms will be voluntary. They will count on average only in case it benefits the student. 

Recovery

  • Only the Written Test I and II activities can be retaken. 
  • If a student has not taken any of the written tests he / she will not be able to take the retake.

Rules for carrying out the activities

For each activity, teachers will be informed of the particular rules and conditions that govern them.

One-on-one activities presuppose the student's commitment to carry them out individually. All activities in which the student does not comply with this commitment will be considered suspended, regardless of their role (sender or receiver). Likewise, the activities to be carried out in groups presuppose the commitment on the part of the students who make it up to carry them out within the group. All activities in which the group has not respected this commitment regardless of its role (sender or receiver) will be considered suspended.

In group activities, the teacher can, based on the information available, customize the grade for each member of the group.

It is optional for teachers to accept or not deliveries outside the deadlines indicated. In the event that these late deliveries are accepted, it is up to the teacher to decide whether to apply a penalty and the amount thereof.

REFERENCES


Basic

Enric Sesa and Josep Roure, "Propositional logics: class notes". TCM internal publication

Josep Roure, "Graphs class notes". TCM internal publication

Josep Roure, "Congruent integers and equations". Class notes. TCM internal publication

Complementary

Robert Sedgewick and Kevin Wayne (2011), "Algorithms", Fourth Edition, Addison-Wesley.