logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 093269 - DISCRETE MATHEMATICS
Docente Zagaglia Norma
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 (434) INGEGNERIA INFORMATICA* AZZZZ093269 - DISCRETE MATHEMATICS
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

Programma dettagliato e risultati di apprendimento attesi

AIMS AND LEARNING OUTCOMES

The course is an introduction to the fundamental notions of  Discrete Mathematics,

one of the fasts growing areas of modern mathematics.

PROGRAM OF THE COURSE: DISCRETE MATHEMATICS

 

MODULAR ARITHMETIC: Divisibility and prime numbers; Congruences; Integers modulo $m$; Euler's theorem; Fermat's little theorem. Elements of finite fields. Chinese remainder theorem; Primality test: Wilson's theorem and its converse.

ENUMERATIVE COMBINATORICS: Basic counting principles; binomial numbers; Stiefel's formula; permutations of a set, selections from a set. Binomial theorem. Generating functions; Fibonacci numbers, 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. Bipartite graphs. Eulerian graphs. Hamiltonian graphs. Trees. Binary trees.
Vertex Colorings. Chromatic number. Planarity of graphs. Euler's formula. Edge colorings. Chromatic index. K\"{o}nig's theorem. Adjacency matrix, incidence matrix with respect to an orientation, Laplacian matrix. Theorem of Poincare'. Spectrum of a graph.
Matchings in bipartite graphs. Hall's theorem.

MATROIDS: Independent sets. Base, circuit, closed set, rank function.
Graphic matroids, uniform matroids

 

Familiarity with the language of functions and sets and basic knowledge of

linear algebra


Note Sulla Modalità di valutazione

The final evaluation consists of an oral exam on the topics presented in the course. 


Bibliografia
Risorsa bibliografica facoltativaN. Biggs, Discrete Mathematics, Editore: Clarendon Press, Oxford, Anno edizione: 1985
Risorsa bibliografica facoltativaP. Cameron, Combinatorics: Topics, Techniques, Algorithms, Editore: Cambridge University Press, Anno edizione: 1994
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

Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
34.0
esercitazione
12.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

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.1 / 1.6.1
Area Servizi ICT
19/11/2019