Matematica Discreta
(A.A. 2011/2012, I semestre)

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 .