Discrete Mathematics and Optimization

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Bioinformatics » Curriculum » Syllabus » Discrete Mathematics and Optimization
Credits
6
Types
Compulsory
Requirements
This subject has not requirements
Department
MAT
Web
https://requile.github.io/dmo.html
Mail
This course looks at the main optimisation tools used in numerical mathematics, from the point of view of both continuous and discrete problems. This calls for a deep understanding of graphs and combinatorial problems in the discrete setting, as well as linear and non-linear problems in the continuous setting.

Teachers

Person in charge

  • Clément Requilé ( )

Others

  • Jorge Delgado Rodríguez ( )
  • Tabriz Arun Avery Popatia ( )

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
6

Learning Outcomes

Learning Outcomes

Knowledge

  • K2 - Identify mathematical models and statistical and computational methods that allow for solving problems in the fields of molecular biology, genomics, medical research, and population genetics.
  • K3 - Identify the mathematical foundations, computational theories, algorithmic schemes and information organization principles applicable to the modeling of biological systems and to the efficient solution of bioinformatics problems through the design of computational tools.

Skills

  • S3 - Solve problems in the fields of molecular biology, genomics, medical research and population genetics by applying statistical and computational methods and mathematical models.

Competences

  • C3 - Communicate orally and in writing with others in the English language about learning, thinking and decision making outcomes.
  • C6 - Detect deficiencies in the own knowledge and overcome them through critical reflection and the choice of the best action to expand this knowledge.

Objectives

  1. Acquisition of the basic knowledge of combinatorics, of linear programing and of multivariate calculus
    Related competences: K3, C3, C6,
  2. Using combinatorics, linear programing and mutlivariate calculus for solving mathematical problems and apply it to discrete, linear and non-linear optimisation problems, especially in the field of bioinformatics.
    Related competences: K2, K3, S3,

Contents

  1. Enumerative combinatorics
    Basic counting. Selections, sets and words. Combinatorial numbers. Recurrences. Solving linear recurrences with constant coefficients.
  2. Graph theory
    Graphs, digraphs and their representations. Trees and Prüfer codes. Exploring graphs with breadth and depth-first search.
  3. Discrete optimisation
    The minimum spanning tree problem. Kruskal and Prim's algorithms. The Travelling Salesman problem.
  4. Linear optimisation
    Linear programming: modelling a problem using a linear program (LP). The geometric viewpoint and the simplex algorithm. Duality and exception handling.
  5. Multivariate calculus
    The gradient and the Hessian. Extrema of functions. Convexity.
  6. Non-linear optimisation
    Convex optimisation. Iterative methods: Newton and Raphson method, gradient descent.

Activities

Activity Evaluation act


Theoretical expository lectures and problem sessions


Objectives: 1 2
Contents:
Theory
30h
Problems
30h
Laboratory
0h
Guided learning
0h
Autonomous learning
90h

Teaching methodology

The course will be divided between the lectures, that will be of the expository type, and problem sessions in smaller groups solved together, with one typical problem to solve individually and at home for every part of the course.

Evaluation methodology

The subject will be assessed by means of compulsory assessment elements which will consist of individual exams, the partial exam (P) and the final exam (F), and six compulsory tests in the form of homeworks (H) to check and orient the learning process of the students. The final grade (G) is computed as follows. Each of the two exams weights 35% of the final grade, and the average of the homeworks weights 30% of the final grade. That is:

G = 0.35*P + 0.35*F + 0.3*H.

A student is considered to have taken the subject if he/she takes the final exam. If the student has taken the subject but has failed, then the student may take the re-
evaluation exam (R). In this case the grade for the re-evalution exam will substitute both the grades of the partial and of the final exams. That is:

G* = 0.70*R + 0.3*H.

Bibliography

Basic: