Scheda insegnamento
Matematica Discreta
| anno accademico: | 2013/2014 |
| docente: | Claudia Malvenuto |
| corso di laurea: | Matematica per le Applicazioni (magistrale), I anno |
| tipo di attività formativa: | caratterizzante |
| crediti formativi: | 6 (48 ore di lezione) |
| raggruppamento disciplinare: | MAT/02 Algebra |
| lingua di insegnamento: | italiano |
| periodo: | II sem (06/03/2014 - 13/06/2014) |
Aula ed orario di lezione
Frequenza: consigliata
Obiettivi del corso: Il corso ha lo scopo di presentare i principi generali e alcuni dei metodi fondamentali della Matematica Discreta, quali il principio di inclusione-esclusione e il metodo della relazioni di ricorrenza. Essi saranno usati per la risoluzione di problemi in diverse aree (polinomi e funzioni simmetriche, insiemi ordinati e teoria dei grafi), con lulteriore intento (più ambizioso!) di evidenziare come lapproccio combinatorio possa risultare chiarificatore e unificante e sia possibile coglierne il fascino nel perenne intrecciarsi di finito e infinito.
Programma di massima del corso:
Programma del corso: Concetti fondamentali. Relazioni dordine. Regole di base per il conteggio. Principio dei cassetti - Strutture combinatorie e successioni fondamentali di interi. Numero delle funzioni tra due insiemi finiti, funzioni iniettive e fattoriale decrescente, coefficiente binomiale come numero degli n-sottoinsiemi e fattoriale decrescente, proprietà dei coefficienti binomiali e teorema binomiale, numero degli n-multinsiemi e fattoriale crescente, numero delle r-scomposizioni di un intero, numero delle partizioni ordinate di un intero. Scomposizioni di un insieme e coefficienti multinomiali, teorema multinomiale. Permutazioni. Il gruppo simmetrico di grado n. Rappresentazione standard di una permutazione attraverso la sua decomposizione in cicli, numero delle permutazioni dello stesso tipo.
Relazioni ricorsive. Relazioni ricorsive delle seguenti successioni: fattoriali decrescenti e crescenti, coefficienti binomiali, cammini crescenti e coefficienti binomiali, numeri di Stirling di I e II specie, partizioni di un intero, permutazioni con k cicli. I numeri di Fibonacci: relazione ricorsiva e forma chiusa, proprietà. Numero dei sottoinsiemi dellinsieme [1,2...,n] che non contengono due interi consecutivi. Relazioni ricorsive lineari omogene.
Il metodo delle funzioni generatrici. Lalgebra delle serie formali. La funzione generatrice di una successione che soddisfa ad una relazione lineare omogenea di ordine k è una funzione razionale p(x)/q(x) dove q(x) ha grado k e p(x) ha grado minore di k e viceversa, calcolo della forma chiusa per la successione di Fibonacci Relazioni ricorsive di successioni di polinomi e funzionali. Successioni polinomiali ed esempi fondamentali. I numeri di Stirling di I e II specie, i numeri di Bell. Successioni polinomiali di tipo binomiale.
Reticoli e principio di inclusione-esclusione. Principio di inclusione esclusione, applicazioni: determinazione della funzione di Eulero, calcolo del numero delle permutazioni senza punti fissi e delle funzioni suriettive (forma chiusa per la successione dei numeri di Stirling).
Testo consigliato:
- J. H. van Lint and R.M. Wilson, A course on Combinatorics. Cambridge University Press, (2001).
- P.J. Cameron: Combinatorics: Topics, Techiques, Algorithms, Cambridge University Press, (1991)
- J.Matousek, J.Nesetril: Invitation to Discrete Mathematics. Clarendon Press (1998).
Modalità di erogazione: convenzionale
Link utile: http://www1.mat.uniroma1.it/people/malvenuto/MatDiscreta/index.html
Risultati di apprendimento - Conoscenze acquisite: Gli studenti conosceranno le principali tecniche usate in Matematica Discreta (regole di conteggio, principio di inclusione-esclusione, relazioni ricorsive, serie formali). Avranno inoltre una conoscenza dei reticoli fondamentali in Combinatoria e delle loro proprietà e più in generale conosceranno la teoria dei reticoli nella quale saranno in grado di inquadrare il principio di inclusione -eslusione.
Risultati di apprendimento - Competenze acquisite: Gli studenti saranno in grado di risolvere semplici problemi di Combinatoria enumerativa. sapranno inoltre risolvere relazioni ricorsive lineari omogene anche usando le funzioni generatrici. Le competenze acquisite permetteranno di affrontare problemi riguardanti le principali strutture discrete.
Studio personale: la percentuale prevista di studio personale sul totale dell'impegno richiesto è del 65%