Matematica Discreta 2023/2024

Proposizioni. Proposizioni composte. La negazione di una proposizione. La congiunzione, disgiunzione, e disgiunzione esclusiva, di due proposizioni. L'implicazione da una proposizione ad un'altra. L'equivalenza di due proposizioni. Proposizioni composte e programmazione. Predicati e quantificatori. La negazione di un quantificatore. La proprieta' distributiva della disgiunzione rispetto alla congiunzione, e della congiunzione rispetto alla disgiunzione. Le Leggi di De Morgan: la negazione di una congiunzione e' la disgiunzione delle negazioni, e la negazione di una disgiunzione e' la congiunzione delle negazioni. 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 la controimmagine di un sottoinsieme mediante una funzione. La controimmagine di una unione e' l'unione delle controimmagini, e similmente per l'intersezione. Permutazioni. Calcolo del prodotto di due permutazioni, e dell'inversa di una permutazione, usando la notazione unilinea. Relazioni su insiemi. Relazioni simmetriche, riflessive, e transitive. Relazioni di equivalenza. Classi di equivalenza. Due classi di equivalenza o coincidono o sono disgiunte. Partizioni di un insieme. Le classi di equivalenza di un insieme rispetto ad una relazione di equivalenza sono una partizione. Dimostrazioni dirette. Dimostrazioni per assurdo. Il Principio di Induzione Matematica. Il Principio del Buon Ordinamento. Numeri naturali. Numeri interi. I numeri razionali sono classi di equivalenza (no dim.). I numeri complessi. L'unita' immaginaria. Somma, prodotto e quoziente di numeri complessi. Il coniugato e la norma di un numero complesso. Divisibilita' tra numeri interi. Numeri perfetti. 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. 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 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. L'inversa moltiplicativa di una classe di resto. La funzione di Eulero. La formula chiusa per la funzione di Eulero. La funzione di Eulero del prodotto di due numeri e' il prodotto delle funzioni di Eulero dei due numeri se questi sono coprimi. La moltiplicazione per la classe di resto di un numero k modulo n e' una biezione delle classi di resto modulo n che sono coprime con n, se k ed n sono coprimi. Il Teorema di Eulero. L'algoritmo di crittografia RSA. Numerazioni in basi diverse. 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. Assegnazione di oggetti distinguibili in categorie distinguibili, ognuna di cardinalita' data. Coefficienti multinomiali. La formula per i coefficienti multinomiali. Multinsiemi. Cardinalita' di un multinsieme. Permutazioni di multinsiemi. Il numero di permutazioni di un multinsieme. 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. Il Principio di Inclusione-Esclusione. La risoluzione delle ricorsioni lineari a coefficienti costanti. Formule chiuse. La formula chiusa per la somma geometrica. Somme polinomiali. La formula chiusa per una somma polinomiale. Somme non polinomiali. Se f e' una funzione reale continua e monotona crescente allora la somma, per i=1,..,n, di f(i) e' limitata superiormente (rispettivamente, inferiormente) da f(n) + l'integrale di f(x) da 1 ad n (rispettivamente, f(1) +  l'integrale di f(x) da 1 ad n). Similmente se f e' una funzione reale continua e monotona decrescente. Somme doppie. La tecnica di inversione dell'ordine di sommatoria per il calcolo e la stima di una somma doppia. Prodotti. La tecnica del logaritmo per il calcolo e la stima di prodotti. La formula di Stirling (no dim.). Notazioni asintotiche. Successioni e funzioni asintoticamente piu' piccole di altre. Successioni e funzioni asintoticamente equivalenti. x alla a e' asintoticamente piu' piccola di x alla b se 0 < a < b. Il logaritmo di x e' asintoticamente piu' piccolo di qualsiasi potenza positiva di x. Qualsiasi potenza di x e' asintoticamente piu' piccola di a alla x se a>1. o-piccolo. O-grande. Se f e' un o-piccolo di g allora f e' un O-grande di g. Se f e' asintoticamente equivalente a g allora f e' un O-grande di g. Un polinomio di grado k e' un O-grande di x alla k. Se f e' un o-piccolo di g allora g non e' un O-grande di f. Omega. f e' un O-grande di g se e solo se g e' un Omega di f. Teta. Insiemi infiniti. La cardinalita' di un insieme infinito. Non esiste una biezione tra un insieme ed il suo insieme delle parti. Un insieme ha cardinalita' strettamente piu' piccola del suo insieme delle parti. Grafi. Cammini. Sentieri. Cammini chiusi. Circuiti. Grafi connessi. Alberi. Il grado di un vertice. Sottoinsiemi indipendenti e completi. Isomorfismi tra grafi. Accoppiamenti. Grafi bipartiti. Accoppiamenti di un grafo bipartito. La caratterizzazione dei grafi bipartiti che ammettono un accoppiamento. Grafi bipartiti costretti nei gradi. Se un grafo bipartito e' costretto nei gradi in un senso allora ammette un accoppiamento nello stesso senso. Grafi bipartiti regolari. Colorazioni di un grafo. Il numero cromatico di un grafo. Grafi vuoti e completi. Se il grado massimo di un grafo e' k allora il grafo puo' essere colorato con k+1 colori. Il numero cromatico di un grafo e' limitato superiormente dal massimo, su tutti i vertici v del grafo, di d(v)+1. Grafi diretti (digrafi). Cammini diretti. Sentieri diretti. Cammini chiusi diretti. Cicli. Raggiungibilita'. Distanza da un vertice ad un altro. Vertici comparabili e incomparabili. Catene. Grado interno ed esterno di un vertice. Digrafi aciclici. Reti di comunicazione. Terminali. Nodi di input e nodi di output. Diametro di una rete di comunicazione. Problemi di smistamento. Smistamenti. La latenza e congestione di uno smistamento. La congestione di una rete di comunicazione. L'albero binario completo, suo diametro e congestione. La griglia. La congestione della griglia e' 2. La farfalla e la sua congestione.