Graph theory, discrete mathematics and optimization
A.A. 2020/2021
Obiettivi formativi
This course aims at introducing modern and advanced mathematical techniques useful for understanding and modeling big data structures and algorithms.
Risultati apprendimento attesi
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.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
The lessons will take place online in synchronous way on the platforms MSTeams or Zoom during the timetable fixed by the faculty. The lectures will also be registered and made available to the students to be followed in an asynchronous way.
The program of the course will remain unchanged.
The written exams during the emergency will maintain the same structure of the usual ones and will be organized through the platform Exam.net, with an external supervision by Zoom or MSTeams.
The program of the course will remain unchanged.
The written exams during the emergency will maintain the same structure of the usual ones and will be organized through the platform Exam.net, with an external supervision by Zoom or MSTeams.
Prerequisiti
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.
Modalità di verifica dell’apprendimento e criteri di valutazione
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 examination sessions, the student may choose instead to substitute the part of exam of the module on Graph Theory and Discrete Mathematics by solving a set of homeworks and small projects, that will be assigned by the teachers during the course. The homeworks are reserved to the students who follow the course in real time. The students who get a positive evaluation in the homeworks will have to pass a reduced written test only on the module of Optimization. The final grade will be the mean of the grades of the two modules.
The outcomes of the exams will be available in the SIFA service through the UNIMIA portal and on the web site of the course.
The outcomes of the exams 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
Programma
Recall of Vectors, Matrices, Vector spaces, Vector equations, Linear systems, Linear models, Linear Independence, Linear Transformations, Matrix algebra, Determinants, Inner Product, norm, Orthogonality, Eigenvectors and Eigenvalues.
Singular Value Decomposition. Dimensionality reduction: Principal Components Analysis.
Graph theory: definitions and fundamental concepts. Directed and undirected graphs.
Probability, events and Combinatorics. Finite and discrete time Markov chains. Random walks. Graph theory: fundamental algorithms. Mining social network graphs.
Singular Value Decomposition. Dimensionality reduction: Principal Components Analysis.
Graph theory: definitions and fundamental concepts. Directed and undirected graphs.
Probability, events and Combinatorics. Finite and discrete time Markov chains. Random walks. Graph theory: fundamental algorithms. Mining social network graphs.
Metodi didattici
Lezioni frontali, tutorials
Materiale di riferimento
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=rep1&type=pdf
J. Leskovec, A. Rajaraman, J.Ullman, Mining of Massive Datasets, Cambridge University Press, last edition (available online at http://www.mmds.org/ ) - (Chapters 9-10-11).
Lecture Notes of the teachers on the module 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=rep1&type=pdf
J. Leskovec, A. Rajaraman, J.Ullman, Mining of Massive Datasets, Cambridge University Press, last edition (available online at http://www.mmds.org/ ) - (Chapters 9-10-11).
Lecture Notes of the teachers on the module web site: https://gtdmo.ariel.ctu.unimi.it/v5/home/Default.aspx
Module Optimization
Programma
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.
Metodi didattici
Lezioni frontali
Materiale di riferimento
Appunti del docente sul sito web del modulo 2: https://homes.di.unimi.it/cordone/courses/courses.html
Moduli o unità didattiche
Module Graph Theory and Discrete Mathematics
SECS-S/06 - METODI MATEMATICI DELL'ECONOMIA E DELLE SCIENZE ATTUARIALI E FINANZIARIE - CFU: 6
Lezioni: 40 ore
Docente:
Micheletti Alessandra
Module Optimization
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 40 ore
Docente:
Cordone Roberto
Docente/i
Ricevimento:
Su appuntamento per email
studio o online (videoconferenza)