Discrete Mathematics and Optimization

Credits
6
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
MAT
Web
https://atenea.upc.edu/course/view.php?id=100753
Mail
clement.requile@upc.edu
This course introduces discrete mathematical structures, including data structures and graphs, and examines them from the perspectives of probability theory and optimisation. It then focuses on optimisation in continuous settings, presenting fundamental techniques in numerical mathematics for both linear and nonlinear problems, including the Simplex algorithm, the Newton¿Raphson method, and gradient-based optimisation methods.

Teachers

Person in charge

  • Clément Requilé (clement.requile@upc.edu)

Others

  • Richard Coll Josifov (richard.coll@upc.edu)

Weekly hours

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

Competences

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 and discrete optimisation
      Graphs, digraphs and their representations. Trees and DAGs.
      Greedy methods in optimisation.
      The minimum spanning tree problem. Kruskal and Prim's algorithms.
      Max-flow / Min-cut and the Folk-Fulkerson's algorithm.
    3. Linear optimisation
      Linear programming: modelling a problem using a linear program.
      The geometric viewpoint and the simplex algorithm.
    4. 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 and the final exam, and two compulsory tests in the form of small in-class exams to check and orient the learning process of the students.

    The final grade (G) is computed as follows. Both the grade of the partial exam (P) and of the final exam (F) weight 45% of the final grade, and the average of the two in-class exams (C) weights 10% of the final grade. That is:

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

    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 new final grade (G') becomes the maximum between G and 0.9*R + 0.1*C:

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

    If the teaching staff considers it appropriate, an oral examination may be conducted to verify the authorship of any of the assessment tests.

    Bibliography

    Basic

    Previous capacities

    Linear algebra.
    Univariate and multivariate calculus.
    Discrete Probability theory.