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://atenea.upc.edu/course/view.php?id=92262
Mail
This course introduces the study of discrete structures in mathematics, like data structures or graphs, in the frameworks of probability theory and optimisation. Then in the continuous setting, we discuss some of the main optimisation tools used in numerical mathematics, from the point of view of both linear and non-linear problems.

Teachers

Person in charge

  • Clément Requilé ( )

Others

  • Richard Coll Josifov ( )
  • 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: C3, C6, K3,
  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. Permutations, sets and words. Combinatorial numbers.
    Applications to discrete probabilities.
    Recurrences. Solving linear recurrences with constant coefficients.
  2. Graph theory
    Graphs, digraphs and their representations.
    Trees and DAGs.
    Graph exploration.
  3. Discrete optimisation
    The shortest path problem
    The minimum spanning tree problem.
    Introduction to the Travelling Salesman problem.
  4. Linear optimisation
    Linear programming: modelling a problem using a linear program.
    The geometric viewpoint and the simplex algorithm.
  5. Non-linear optimisation
    Recall of multivariate calculus and 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 four compulsory tests in the form of small in-class exams (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 45% of the final grade, and the average of the homeworks weights 10% of the final grade. That is:

G = 0.45*P + 0.45*F + 0.1*H.

A student is considered to have taken the subject if he/she takes the final exam. In that case, and if G< 5, the student can take the recuperaction exam (R), and the final grade becomes the maximum between G and 0.9*R + 0.1*H:

G' = max ( G , 0.9*R + 0.1*H ).

Bibliography

Basic: