Mathematics I

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » Mathematics I
Credits
7.5
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
MAT
Web
https://mat-web.upc.edu/fib/matematiques1/
This course further develops the concepts of reasoning that are introduced in the course Mathematical Foundations (FM); this is done through the study of two subjects with which every computing engineer must be familiar: graph theory and linear algebra.

Teachers

Person in charge

  • Anna De Mier Vinué ( )

Others

  • Carlos Seara Ojea ( )
  • Eric López Platón ( )
  • Fabian Maximilian Klute ( )
  • Fernando Martínez Sáez ( )
  • Gemma Alsina Ruiz ( )
  • Jordi Massó Cuscó ( )
  • Jose Luis Ruiz Muñoz ( )
  • Josep Elgueta Monto ( )
  • Mariona González Esteve ( )
  • Mercè Mora Giné ( )
  • Montserrat Maureso Sánchez ( )
  • Núria Mira Gómez ( )
  • Rafel Farré Cirera ( )
  • Rodrigo Ignacio Silveira ( )
  • Tabriz Arun Avery Popatia ( )

Weekly hours

Theory
3
Problems
0
Laboratory
2
Guided learning
0
Autonomous learning
7.5

Competences

Technical Competences

Common technical competencies

  • CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
    • CT1.2A - To interpret, select and value concepts, theories, uses and technological developments related to computer science and its application derived from the needed fundamentals of mathematics, statistics and physics. Capacity to solve the mathematical problems presented in engineering. Talent to apply the knowledge about: algebra, differential and integral calculus and numeric methods; statistics and optimization.
    • CT1.2C - To use properly theories, procedures and tools in the professional development of the informatics engineering in all its fields (specification, design, implementation, deployment and products evaluation) demonstrating the comprehension of the adopted compromises in the design decisions.

Transversal Competences

Reasoning

  • G9 [Avaluable] - Capacity of critical, logical and mathematical reasoning. Capacity to solve problems in her study area. Abstraction capacity: capacity to create and use models that reflect real situations. Capacity to design and perform simple experiments and analyse and interpret its results. Analysis, synthesis and evaluation capacity.
    • G9.1 - Critical, logical and mathematical reasoning capacity. Capacity to understand abstraction and use it properly.

Objectives

  1. To know and understand the concept of graph as a model of a binary relationship. To be able to work with different representations of a graph, in particular, finding the main parameters of a graph and deciding whether two given graphs are isomorphic.
    Related competences: G9.1, CT1.2C,
  2. To know the definitions concerning walks, connectivity and distance in graphs, and being able to work with these concepts and their relationships, at the theoretical and practical level. To understand and apply algorithms to determine whether a graph is connected and to compute distances in graphs.
    Related competences: G9.1, CT1.2C,
  3. To know the concepts of Eulerian and Hamiltonian graph, and to be able to decide if a graph is Eulerian or Hamiltonian. To be aware that these two problems look very similar but are very different from the theoretical and computational point of views.
    Related competences: G9.1, CT1.2C,
  4. To know what a tree is and to be able to work with its different equivalent definitions. To understand the concept of a spanning tree and its relationship to connectivity. To know and apply algorithms to find a spanning tree. To know how to codify a tree with a Prüfer sequence.
    Related competences: G9.1, CT1.2C,
  5. To know how to perform matrix operations. To know the elementary matrix transformations (by rows), and to use them to find the rank of a matrix and to decide whether a matrix is invertible. To know the basic properties of determinants, and how to apply them to simplify computations.

    Related competences: G9.1, CT1.2A,
  6. To understand and apply Gauss-Jordan elimination to discuss and solve linear systems, and to calculate the inverse of a matrix.
    Related competences: CT1.2A,
  7. To know and understand the concepts of a vector space, of subspace, linear dependence and independence, and basis. To be able to prove basic properties about these concepts and their relationships.
    Related competences: G9.1, CT1.2A,
  8. To know how to do computations in a vector space, that is, to be able to work in practice with the concepts of vector subspace, linear combination, generators, linear dependence and bases. To know how to find the matrix of a change of basis.
    Related competences: CT1.2A,
  9. To know and understand the concepts of linear map, kernel, image, isomorphism, endomorphism. To be able to prove basic properties involving these concepts and their relationships.
    Related competences: G9.1, CT1.2A,
  10. To be able to decide whether a map is linear. To work in practice with the concepts of kernel, image, endomorphism and isomorphism. To know how to find the matrix associated to a linear map in in a basis.
    Related competences: CT1.2A,
  11. To know what are eigenvalues, eigenvectors and the characteristic polynomial of an endomorphism. To be able to prove basic properties concerning the concepts above. To discuss whether an endomorphism is diagonalisable or not.
    Related competences: G9.1, CT1.2A,

Contents

  1. Basic concepts of graphs
    Definition of graph, adjacency and incidence matrices, the handshake lemma and its consequences; isomorphism of graphs; families of graphs, subgraphs, graph operations.
  2. Walks, connectivity and distance
    Definitions of walk, cycle, path; some properties of walks; definition of connected graph and connected components; DFS algorithm; inequality m>=n-1; definitions of cut vertices and bridges, and their characterization; definitions of distance and diameter; BFS algorithm; characterization of bipartite graphs.
  3. Eulerian and Hamiltonian graphs
    Definitions of Eulerian circuit, trail and graph; characterization of Eulerian graphs; definition of Hamiltonian cycle, path and graph; necessary conditions for being Hamiltonian; the theorems of Dirac and Ore.
  4. Trees
    Definitions of forest, tree and leaf; equivalent characterizations and their corollaries; definition of spanning tree; review of DFS and BFS; Cayle's theorem.
  5. Matrices and systems of linear equations
    Definition of matrix, families of matrices; linear operations and their properties; product of matrices and matrix inverse; matrix transpose and relationship to the operations; elementary row transformations, elementary matrices, row-echelon form; rank of a matrix; computing the matrix inverse; systems of linear equations, equivalent systems; discussion and solution using Gauss-Jordan; recursive definition of determinant, properties of determinants, minors of a matrix and relationship to the rank.
  6. Vector Spaces
    Definition of vector space; definition of subspace and its equivalent characterization; subspace spanned by a set of vectors, linear combinations, systems of generators; linear independence and its properties; bases and coordinates; dimension; basis changes and the change of basis matrix.
  7. Linear maps
    Definition of linear map and basuc properties; linear map defined by a matrix; matrix of a linear map; kernel and image, the dimension theorem; characterization of one-to-one and onto linear maps; isomorphism of vector spaces, isomorphic spaces; composition of maps; change of basis; geometric interpretation of linear maps on the plane and the space.
  8. Diagonalization
    Eigenalues and eigenvectors; diagonalization of endomorphisms; symmetric matrices.

Activities

Activity Evaluation act


Introduction to Graph Theory

Theory and practice of Chapters 1 and 2 of the syllabus.
Objectives: 1 2
Contents:
Theory
9h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
21h

Main families of graphs.

Theory and practice of Chapters 3 and 4 of the syllabus.
Objectives: 3 4
Contents:
Theory
9h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
21h

Matrices and systems of linear equations

Theory and practice of Chapter 5 of the syllabus.
Objectives: 5 6
Contents:
Theory
4h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
14h

Vector Spaces

Theory and practice of Chapter 6 of the syllabus.
Objectives: 7 8
Contents:
Theory
9h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
14h

Linear maps and diagonalization

Theory and practice of Chapters 7 and 8 of the syllabus.
Objectives: 9 10 11
Contents:
Theory
9h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
21h

Exam about the first part of the course (theory and problems)

The goals 1-4 will be evaluated.
Objectives: 1 2 3 4
Week: 7 (Outside class hours)
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
9h

Final exam for the course (theory and problems)

The exam will have two parts. In the first (F1) the course objectives 1-4 will be evaluated, and in the second (F2), the objectives 5-11.
Objectives: 1 2 3 4 5 6 7 8 9 10 11
Week: 15 (Outside class hours)
Type: theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
12.5h

Teaching methodology

In the theory classes the teacher explains the subject accompanying it with some examples and solving problems of the list.

During the practical classes students solve problems under the supervision of the teacher; some of these problems must be prepared prior to the class.

Evaluation methodology

The grade for the course will be obtained from:

-a mid-term exam P, on the first part of the syllabus;
-the T assessment of the work and the achievement of objectives in workshop sessions, which may include, among others, tests during class hours, solving online questionnaires and participation in the EngiMath project;
-a final exam F, which will have two parts, F1 and F2.


The grade on the evaluation report will be:
0.2 * T +0.35 * MAX (P, F1) * F2 +0.45

Students who wish to take the exam F1 will have to let this know to the coordinator of the course (the deadline for doing so will be announced accordingly).

The grade NP will be given to those students not showing up at any of the tests of the part corresponding to items 5,6,7,8 in the syllabus.

There will be a part of the examination devoted to the evaluation of generic competition.

Bibliography

Basic:

Complementary:

Web links

Previous capacities

Those supposed to students who have successfully passed their pre-university education.

The material corresponding to the course "Fonaments Matemàtics" (FM), in particular the part about mathematical reasoning.

In particular, we advise you strongly against taking M1 if your grade in FM is less than 4.