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=92262
Mail
clement.requile@upc.edu
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

Others

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
      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