TecnoCampus Foundation
eCampus
University Business
eCampus

What are you looking for?

General information

Subject type: Basic

Coordinator: Ana Beatriz Pérez Zapata

Trimester: Third term

Credits: 6

Teaching staff: 

Alfonso Palacios González
Carles Bonet Papell 

Teaching languages

  • Catalan

This subject is taught in Catalan, but the bibliography and documentation is mostly in English. 

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 cannot tell which real number comes after another, for example we do not know which number comes after 1,0) on the other hand 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 among 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. 

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.

Contents

  1. Propositional logic
    1. Reasoning, natural language and propositional language
    2. The language of propositional logic, CP0
    3. Formalization of sentences and interpretation of statements
    4. Theory of models (tautologies, contradictions and contingencies)
    5. Demonstration theory
    6. Valid and invalid reasoning, consistency and inconsistency, counterexamples
    7. Normal forms
    8. The method of resolution
    9. Linear Resolution
  2. Graph theory
    1. Basic definitions: paths, connectivity and distance, Isomorphism between graphs
    2. Representation of graphs
    3. Algorithms on graphs: paths in depth and width (DFS, BFS)
    4. Digraphs and DAGs
    5. Topological arrangement
    6. Minimal expansion trees: Prim and Kruskal algorithms
    7. Shorter paths: Dijkstra's algorithm

Evaluation system

The final grade is the average grade of the two parts of the subject

ACTIVITY and WEIGHT

  1. Logic Exam 45% - 50%
  2. Graphs Exam 45% - 50%
  3. Solving logic problems in class 0% - 5%
  4. Class Graphing Problem Solving 0% - 5%

In order to pass the subject, the grades for both parts of the subject must be equal to or greater than 5

Problem solving is voluntary

Recovery

  • Only exams can be made up, not class participation
  • The student can only appear for the recovery if he has appeared for the ordinary exam. 

 

REFERENCES

Basic

K. Erciyes, "Discrete Mathematics and Graph Theory, a concise study companion and guide (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-61114-9

Kenneth H. Rosen, "Discrete Mathematics and its Applications." Eighth Edition. McGraw-Hill-Education, 2019. ISBN 978-1-260-09199-1.

Complementary

Robert Sedgewick and Kevin Wayne, "Algorithms", Fourth Edition, Addison-Wesley, 2011. ISBN 978-0321573513.

Gabriel Valiente, "Algorithms on Trees and Graphs: With Python Code (Texts in Computer Science)". Second Edition. Springer, 2021. ISBN 

978-3030818845

K. Erciyes, "Algebraic Graph Algorithms, a practical guide using Python (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-87885-6