Matematica Discreta
(A.A. 2011/2012, I semestre)
Il corso e' inteso principalmente per studenti del primo anno del corso
di studi in informatica.
Programma del corso:
-
La nozione di insieme e di appartenenza di un elemento ad un insieme.
Sottoinsiemi di un insieme: inclusione di un
insieme in un altro. L'insieme vuoto. Intersezione e unione di due insiemi.
Proprieta' associativa e distributiva dell'unione e dell'intersezione.
Diagrammi di Venn. L'insieme complementare di un insieme. Leggi di De Morgan.
Il prodotto cartesiano di due insiemi e sue proprieta'. Funzioni tra insiemi.
Funzioni iniettive, suriettive, e biunivoche. Composizione di funzioni. Associativita'
della composizione. La
composizione di due funzioni iniettive e' iniettiva, e similmente per funzioni
suriettive e biunivoche. L'inversa di una funzione biunivoca. La funzione identita'.
La composizione di una funzione e della sua inversa e' la funzione identita'.
L'immagine e controimmagine di un sottoinsieme tramite una funzione. La controimmagine
di una intersezione e' l'intersezione delle controimmagini, e similmente per l'unione.
Relazioni su insiemi. Relazioni simmetriche, riflessive, e transitive. Relazioni di
equivalenza. Classi di equivalenza. Due classi di equivalenza o coincidono o sono
disgiunte. L'insieme quoziente di un insieme rispetto ad una relazione di equivalenza.
Dimostrazioni dirette. Dimostrazioni per assurdo. Il Principio di
Induzione Matematica. Numeri naturali. Numeri interi. I numeri
razionali sono un insieme quoziente (no dim.). I numeri complessi.
L'unita' immaginaria. Somma e prodotto di numeri complessi. Il
coniugato e la norma di un numero complesso. Divisibilita' tra
numeri interi. Numeri primi e composti. Numeri coprimi. Ogni numero
>1 e' prodotto di numeri primi. L'infinita' dei numeri primi.
L'Algoritmo Euclideo per la
determinazione del massimo comun divisore di due interi positivi.
L'identita' di Bezout. Se un numero primo divide un prodotto allora
divide uno dei fattori. Il Teorema Fondamentale dell'Aritmetica
(no dim.). Numeri irrazionali. Le radici di un polinomio monico a
coefficienti interi che non sono intere sono irrazionali.
Equazioni Diofantee lineari. Un'equazione Diofantea lineare a due
incognite ha soluzione se e solo se il massimo comun divisore dei
due coefficienti divide il termine noto. La soluzione generale di
un'equazione Diofantea lineare a due incognite (no dim.). La
relazione di congruenza. La relazione di congruenza e' una relazione
di equivalenza (no dim.). Le classi di resto. Somma e prodotto di
due classi di resto. La legge di cancellazione tra classi di resto.
La risoluzione di equazioni lineari in una incognita tra classi di resto (no dim.).
Il Teorema Cinese dei Resti (no dim.).
La funzione di Eulero. La funzione di Eulero del prodotto di due numeri coprimi e'
il prodotto delle funzioni di Eulero dei due numeri. La formula chiusa per la
funzione di Eulero. La somma delle funzioni di Eulero dei divisori di un numero
e' il numero stesso. Il Teorema di Fermat-Eulero (no dim.). Il Teorema di Fermat.
L'algoritmo di crittografia RSA.
Polinomi in una variabile a coefficienti razionali, reali, o complessi. Polinomi
irriducibili. Il resto e quoziente della divisione tra due polinomi. Il resto della
divisione tra un polinomio ed un polinomio di grado uno coincide con il polinomio
valutato nella radice del polinomio di grado uno. Un polinomio e' divisibile per
un polinomio lineare se e solo se si annulla nell'unica radice del polinomio lineare.
Il numero di radici di un polinomio non eccede il suo grado. Il Teorema Fondamentale dell'Algebra (no dim.).
L'Algoritmo Euclideo per la determinazione di un massimo comun divisore tra due
polinomi. Il massimo comune divisore tra due polinomi e' determinato a meno di una
costante moltiplicativa. Un polinomio e' esprimibile come combinazione lineare,
a coefficienti polinomiali, di due polinomi dati se e solo se e' divisibile per
il loro massimo comun divisore. La cardinalita' del prodotto Cartesiano di due insiemi
e' il prodotto delle loro cardinalita'. La cardinalita'
della potenza di due insiemi e' la potenza delle loro cardinalita'. La cardinalita' dell'unione
di due insiemi e' uguale alla somma delle loro cardinalita' meno la cardinalita' dell'intersezione.
Il problema fondamentale della combinatoria enumerativa e sue possibili soluzioni. Formule,
ricorsioni, funzioni generatrici. Ci sono 2 alla n sottoinsiemi di un insieme di cardinalita' n.
Coefficienti binomiali. Il numero di sottoinsiemi di cardinalita' k di un insieme di cardinalita' n
e' n binomiale k. Il coefficiente di x alla k in (1+x) alla n e' n binomiale k. In un insieme finito
ci sono tanti sottoinsiemi di cardinalita' pari quanti di cardinalita' dispari. Partizioni insiemistiche.
Blocchi di una partizione insiemistica. C'e' una biezione esplicita tra partizioni insiemistiche di un
insieme e le relazioni di equivalenza sulla stesso insieme. Numeri di Stirling di II specie. La ricorsione
per i numeri di Stirling di II specie. Fattoriali discendenti. I numeri di Stirling di II specie sono i
coefficienti che si ottengono scrivendo una potenza come combinazione lineare di fattoriali discendenti.
Composizioni. Parti di una composizione. Il numero di composizioni di un intero n in k parti e' n-1 binomiale
k-1. Composizioni deboli. Il numero di composizioni deboli di un intero n in k parti e' n+k-1 binomiale k-1.
Permutazioni. Prodotto tra permutazioni. Il periodo di una permutazione. La rappresentazione di una permutazione
come prodotto di cicli disgiunti. Numeri di Stirling di I specie, con e senza segno. La ricorsione per i
numeri di Stirling di I specie. La funzione generatrice per i numeri di Stirling di I specie. La relazione
tra numeri di Stirling di I e II specie (no dim.). Inversioni. Il numero delle inversioni di una permutazione.
La tabella delle inversioni. La biezione tra permutazioni e tabelle delle inversioni.
Assegnazione di oggetti distinguibili in categorie distinguibili, ognuna di cardinalita' data.
Coefficienti multinomiali. La formula per i coefficienti multinomiali. Multinsiemi. Cardinalita' di un multinsieme.
La funzione generatrice del numero di multinsiemi su {1,...,n} di cardinalita' k. Permutazioni di multinsiemi.
Il numero di permutazioni di un multinsieme.
Il Principio di Inclusione-Esclusione. Deragliamenti. Il numero di deragliamenti di Sn.
La risoluzione delle ricorsioni lineari a coefficienti costanti.
Il numero di funzioni suriettive dai primi n interi ai primi k interi positivi e' k! per il numero di Stirling
di II specie S(n,k). Il numero di funzioni iniettive dai primi n interi ai primi k interi positivi e' il
fattoriale discendente n-esimo calcolato in k. Grafi. Cammini. Circuiti. Grafi connessi. Alberi. Il grado di
un vertice. Cammini Euleriani. Circuiti Euleriani. Grafi Euleriani. Caratterizzazione dei grafi che ammettono
un circuito Euleriano (no dim.). Caratterizzazione dei grafi che ammettono un cammino Euleriano. Accoppiamenti.
Grafi bipartiti. Accoppiamenti di un grafo bipartito. La caratterizzazione dei grafi bipartiti che ammettono
un accoppiamento (no dim.).
Bibliografia .
Obiettivi Previsti di Apprendimento .