logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 093269 - DISCRETE MATHEMATICS
Docente Notari Roberto
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ093269 - DISCRETE MATHEMATICS
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ093269 - DISCRETE MATHEMATICS

Obiettivi dell'insegnamento

The course is an introduction to the fundamental notions of Discrete Mathematics, one of the fastest growing areas of modern mathematics. These notions are nowadays more and more used in the development, analysis and comprehension of mathematical models in every area of engeneering. The course is an introduction to the various topics that go under the name of discrete mathematics, and they range from graph theory, to elementary number theory and modular arithmetics, to abstract algebra, and to enumerative combinatorics.


Risultati di apprendimento attesi

The classes and the exercise sessions will allow students to get acquaintance with the topics of the course and with some applications of the topics to the resolution of practical problems. In more details, students will learn how to:
• use formal rules for computations on symbols, independently from the meaning of the symbols;
• solve equations over the integers or over the integers modulo m;
• compute the number of elements of sets defined by a property;
• analyze graphs.

Students will be able to justify the effectiveness of mathematical procedures used to solve the problems presented in the course and to properly use the mathematical language while arguing.


Argomenti trattati

ELEMENTARY NUMBER THEORY AND MODULAR ARITHMETIC: Basic notions of set theory. Natural numbers and the induction principle. Integers. Divisibility and prime numbers. Euler's function. Congruences. Integers modulo m. Euler's theorem. Fermat's little theorem. Elements of group, rings and fields. Finite fields. Chinese remainder theorem. Primality test: Wilson's theorem and its converse.

ENUMERATIVE COMBINATORICS: Cardinality of a set. Basic counting principles. Binomial numbers, Stiefel's formula and other identities on binomial numbers. Permutations and selections from a set. Binomial theorem. Formal power series. Partial fractions. Generating functions. Linear homogeneous recursions. Fibonacci and Lucas numbers. Closed form of the Fibonacci numbers. Stirling numbers of the second kind. Partitions of a natural number. Ferrers diagrams. The Tower of Hanoi problem. Principle of inclusion and exclusion. Formulas of Sylvester and Da Silva. Derangements.

GRAPHS: Basic definitions. Planarity of graphs. Euler's formula. Bipartite graphs. Eulerian graphs. Hamiltonian graphs. Trees. Binary trees. Spanning trees. Vertex colorings. Chromatic number. Edge colorings. Chromatic index. K\"{o}nig's theorem. Matchings in bipartite graphs. Hall's theorem. Adjacency matrix, incidence matrix with respect to an orientation, Laplacian matrix. Theorem of Poincare'. Spectrum of a graph.


Prerequisiti

Students are required to have basic knowledge of mathematical analysis and linear algebra.


Modalità di valutazione

The final evaluation consists of an oral exam on the topics presented in the course. The aim of the exam is to verify if the student has got the following expertises: knowledge of the definitions and results on the topics of the course and ability both of applying that knowledge to solve exercises and of proving mathematical results presented in the course.


Bibliografia
Risorsa bibliografica facoltativaN. Biggs, Discrete Mathematics, Editore: Clarendon Press, Oxford, Anno edizione: 1985
Risorsa bibliografica facoltativaR. Graham, D. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Editore: Addison-Wesley, Anno edizione: 1989
Risorsa bibliografica facoltativaF. S. Roberts, Applied Combinatorics, Editore: Prentice-Hall, Anno edizione: 1984

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
32:30
48:45
Esercitazione
17:30
26:15
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
03/12/2020