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. Differenza e differenza simmetrica tra due insiemi. 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. 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 di Induzione completa. Il Principio del Buon Ordinamento. Numeri naturali. Numeri interi. I numeri razionali. I numeri complessi. Parte reale ed immaginaria di un numero complesso. L'unita' immaginaria. Somma, prodotto e quoziente di numeri complessi. Il coniugato ed il modulo di un numero complesso. La forma polare 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. Il Teorema dei Numeri Primi (no dim.). 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. 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. Il Piccolo Teorema di Fermat. Il problema fondamentale della crittografia. Il codice romano. Il codice di Turing, versione aritmetica e modulare. Debolezze di questi codici. L'algoritmo di crittografia RSA. La cardinalita' del prodotto Cartesiano di due insiemi e' il prodotto delle loro cardinalita'. La potenza di due insiemi. 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. Funzioni k-ad-1 con k un intero positivo. La regola della divisione. Il numero di permutazioni. 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. Lo sviluppo in serie di Taylor di (1+x) alla n con n intero. La serie geometrica. Assegnazione di oggetti distinguibili in categorie distinguibili, ognuna di cardinalita' data. Coefficienti multinomiali. La formula per i coefficienti multinomiali. Sequenze con ripetizioni. Permutazioni di una sequenza con ripetizioni. Il numero di permutazioni di una sequenza con ripetizioni. Il Principio di Inclusione-Esclusione. Il Teorema Fondamentale dell'Algebra. Radici di un polinomio in una variabile, e loro molteplicita'. 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 il limite, per n che tende all'infinito, di f(n)/g(n) esiste ed e' finito allora f e' un O-grande di g. Un polinomio di grado k e' un O-grande di x alla k. Omega. f e' un O-grande di g se e solo se g e' un Omega di f. Teta. Grafi. Cammini. Sentieri. Cammini chiusi. Cicli. Grafi vuoti e completi. Grafi connessi. Grafi aciclici. Alberi. Foreste. Il grado di un vertice. Sottoinsiemi indipendenti e completi. La somma dei gradi di tutti i vertici di un grafo e' uguale al doppio del numero dei lati. Isomorfismi tra grafi. Proprieta' invarianti per isomorfismi. 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. Se il grado massimo di un grafo e' k allora il grafo puo' essere colorato con al piu' k+1 colori. Grafi diretti (digrafi). Cammini diretti. Sentieri diretti. Cammini chiusi diretti. Cicli. Raggiungibilita'. Distanza da un vertice ad un altro. Vertici comparabili e incomparabili. Catene e anticatene. Grado interno ed esterno di un vertice. Digrafi aciclici. Orari paralleli. Passi, tempo, e numero di processori di un orario parallelo. Sentieri critici. Profondita' di un elemento in un digrafo aciclico. Un orario parallelo di tempo minimo in un digrafo aciclico e' dato dalla partizione il cui blocco i-esimo consiste di tutti gli elementi di profondita' i. Reti di comunicazione. Terminali. Nodi di input e nodi di output. Switches. 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. La congestione della farfalla. Relazioni antisimmetriche e antiriflessive. Relazioni d'ordine parziale, deboli e forti. Insiemi parzialmente ordinati (poset). Elementi comparabili ed incomparabili. Ordini totali. Il digrafo associato ad un insieme parzialmente ordinato. Il digrafo corrispondente ad un poset non ha cicli di lunghezza maggiore di 1. La chiusura transitiva di un digrafo aciclico. Per ogni digrafo aciclico esiste un poset il cui digrafo associato e' la chiusura transitiva del digrafo dato. Copertura. Il diagramma di Hasse di un poset. Elementi minimali e massimali. Ogni poset finito ammette almeno un elemento minimale e almeno uno massimale. Ordinamenti topologici. Il sottoposet indotto da un sottoinsieme dei vertici di un poset. Ogni poset finito ammette almeno un ordinamento topologico. La relazione prodotto di due relazioni. Se due relazioni sono riflessive anche la relazione prodotto e' riflessiva, e similmente per relazioni antisimmetriche e transitive.