#
Graph Theory, Discrete Mathematics and Optimization

A.Y. 2019/2020

Learning objectives

This course aims at introducing modern and advanced mathematical techniques useful for understanding and modeling big data structures and algorithms.

Expected learning outcomes

At the end of the course the student will be able to formalize real world problems in mathematical terms and to solve simple exercises related with linear algebra, graph theory, Markov Chains, Optimization and Decision Theory.

**Lesson period:** First trimester
(In case of multiple editions, please check the period, as it may vary)

**Assessment methods:** Esame

**Assessment result:** voto verbalizzato in trentesimi

Course syllabus and organization

### Unique edition

Responsible

Lesson period

First trimester

**Prerequisites for admission**

Prerequisites for this course include a good knowledge of the mathematical tools presented in Calculus I and Linear Algebra courses and in an introductory course in Probability and Statistics, with particular reference to the following arguments: real functions of one and two variables; derivatives; partial derivatives; integrals; vectors and matrices; operations between matrices; determinants; eigenvalues and eigenvectors; probability measures; events; random variables; distributions.

**Assessement methods and criteria**

The final examination consists of a written exam during which the student must solve some exercises in the format of open-ended and/or multiple answer questions, with the aim of assessing the student's knowledge and ability to solve problems related with the arguments of the course. The duration of the written exam will be proportional to the number of exercises assigned, also taking into account the nature and complexity of the exercises themselves (however, the duration is usually of 1.5 hours). In place of a single written exam given during the first examination session, the student may choose instead to take 3 midterm exams.

The outcomes of the tests will be available in the SIFA service through the UNIMIA portal and on the web site of the course.

The outcomes of the tests will be available in the SIFA service through the UNIMIA portal and on the web site of the course.

**Module Graph Theory and Discrete Mathematics**

**Course syllabus**

PART 1:

Vectors, Matrices, Vector spaces, Vector equations, Linear systems, Linear models, Row Reduction and Echelon Forms, Linear Independence, Linear Transformations, the Matrix of a Linear Transformation, Matrix algebra, Determinants, Inner Product, norm, Orthogonality, Eigenvectors and Eigenvalues,

Graph theory: definitions and fundamental concepts. Directed and undirected graphs.

PART2:

Probability, events and Combinatorics. Finite and discrete time Markov chains. Random walks. Graph theory: fundamental algorithms. Mining social network graphs.

Vectors, Matrices, Vector spaces, Vector equations, Linear systems, Linear models, Row Reduction and Echelon Forms, Linear Independence, Linear Transformations, the Matrix of a Linear Transformation, Matrix algebra, Determinants, Inner Product, norm, Orthogonality, Eigenvectors and Eigenvalues,

Graph theory: definitions and fundamental concepts. Directed and undirected graphs.

PART2:

Probability, events and Combinatorics. Finite and discrete time Markov chains. Random walks. Graph theory: fundamental algorithms. Mining social network graphs.

**Teaching methods**

Face-to-face lectures, tutorials

**Bibliography**

David C. Lay, Steven R. Lay and Judi J. McDonald, Linear Algebra and Its Applications, Pearson, 2016

K. Ruohonen, Graph Theory, Course notes. http://math.tut.fi/~ruohonen/GT_English.pdf (Chapters 1,2,3)

O. Haggstrom, Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003. (Chapters1,2,3). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.9739&rep=re…

J. Leskovec, A. Rajaraman, J.Ullman, Mining of Massive Datasets, Cambridge University Press, last edition (available online at http://www.mmds.org/ ) - (Chapter 10).

Lecture notes of the teachers on the module 1 web site: https://gtdmo.ariel.ctu.unimi.it/v5/home/Default.aspx

K. Ruohonen, Graph Theory, Course notes. http://math.tut.fi/~ruohonen/GT_English.pdf (Chapters 1,2,3)

O. Haggstrom, Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003. (Chapters1,2,3). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.9739&rep=re…

J. Leskovec, A. Rajaraman, J.Ullman, Mining of Massive Datasets, Cambridge University Press, last edition (available online at http://www.mmds.org/ ) - (Chapter 10).

Lecture notes of the teachers on the module 1 web site: https://gtdmo.ariel.ctu.unimi.it/v5/home/Default.aspx

**Module Optimization**

**Course syllabus**

1.Introduction to complex decision problems: case studies; formal definitions.

2.Mathematical Programming: Karush-Kuhn-Tucker conditions.

3.Multi-objective Programming: Paretian case; Multi-Attribute Utility Theory; Analytic Hierarchy Process; ELECTRE Methods.

4.Uncertain Programming: decision making under ignorance; decision making under risk; decision theory.

2.Mathematical Programming: Karush-Kuhn-Tucker conditions.

3.Multi-objective Programming: Paretian case; Multi-Attribute Utility Theory; Analytic Hierarchy Process; ELECTRE Methods.

4.Uncertain Programming: decision making under ignorance; decision making under risk; decision theory.

**Teaching methods**

face to face lectures

**Bibliography**

Lecture notes on the module 2 web site: https://homes.di.unimi.it/cordone/courses/courses.html

Module Graph Theory and Discrete Mathematics

SECS-S/06 - MATHEMATICAL METHODS OF ECONOMICS, FINANCE AND ACTUARIAL SCIENCES - University credits: 6

Lessons: 40 hours

Professors:
Micheletti Alessandra, Naldi Giovanni

Module Optimization

MAT/09 - OPERATIONS RESEARCH - University credits: 6

Lessons: 40 hours

Professor:
Cordone Roberto

Educational website(s)

Professor(s)