Obiettivi formativi
OBIETTIVI FORMATIVI:
L’insegnamento si propone di fornire agli studenti le nozioni fondamentali di teoria degli insiemi,
teoria dei numeri, combinatoria enumerativa, analisi asintotica, e teoria dei grafi. Tutte queste discipline
giocano un ruolo fondamentale nell’informatica, e sono importanti per la programmazione.
CONOSCENZA E CAPACITÀ DI COMPRENSIONE:
Al termine del processo di apprendimento ci si aspetta che lo studente abbia memorizzato il contenuto del
corso, e che lo abbia compreso.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE:
Al termine del processo di apprendimento ci si aspetta che lo studente sia in grado di applicare le tecniche
imparate nel corso alla risoluzione di problemi simili a quelli visti nel corso. In particolare, lo studente sarà
in grado di calcolare l'inversa moltiplicativa di una classe di resto, di risolvere ricorsioni lineari a coefficienti
costanti, di codificare e decodificare messaggi tramite il protocollo RSA, usare ed
applicare il Principio di Inclusione-Esclusione, stimare asintoticamente somme
singole e multiple, colorare un grafo in modo relativamente efficiente, calcolare i
parametri fondamentali di una rete di comunicazione.
AUTONOMIA DI GIUDIZIO:
Al termine del processo di apprendimento lo studente sara’ in grado di individuare all’interno di problemi
pratici derivanti dallo svolgimento della professione di informatico i problemi matematici studiati nel corso.
ABILITÀ COMUNICATIVE:
Al termine del processo di apprendimento lo studente sara’ in grado di comunicare in modo efficiente con
matematici che lavorano in Matematica Discreta.
CAPACITÀ DI APPRENDIMENTO:
Al termine del processo di apprendimento lo studente sara’ in grado di leggere e comprendere libri
professionali di Matematica Discreta.
Programma
Teoria degli Insiemi (12 ore):
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. L'insieme quoziente di un insieme rispetto ad una relazione di equivalenza. Partizioni di un insieme. L'insieme quoziente di un insieme rispetto ad una relazione di equivalenza e' una partizione.
Teoria dei Numeri (22 ore):
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, 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 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 risoluzione di equazioni lineari in una incognita tra classi di resto. 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 formula chiusa per la funzione di Eulero. 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 Fermat-Eulero. Il Teorema di Fermat. L'algoritmo di crittografia RSA. Numerazioni in basi diverse.
Combinatoria Enumerativa (18 ore):
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. Sequenze con ripetizioni. 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.
Somme ed asintotica (10 ore):
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. 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.
Teoria dei Grafi (10 ore):
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. 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. Orari paralleli. Passo, tempo, e numero di processori di un orario. 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. Il tempo minimo per un orario parallelo e' uguale alla cardinalita' massima di un sentiero critico. 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.
Modalità d'esame
Lo studente dovrà dimostrare di ricordare il contenuto del corso, di averne
compreso il significato, e di saper applicare le tecniche studiate nel corso per
saper calcolare l'inversa moltiplicativa di una classe di resto, risolvere ricorsioni
lineari a coefficienti costanti, codificare e decodificare messaggi tramite il
protocollo RSA, usare ed applicare il Principio di Inclusione-Esclusione, stimare
asintoticamente somme singole e multiple, colorare un grafo in modo relativamente
efficiente, calcolare i parametri fondamentali di una rete di comunicazione. La
valutazione dello studente prevede una prova scritta in cui vengono proposti 8
quesiti con domande aperte. 3 di queste domande riguardano: inverse moltiplicative
di classi di resto, codifica e decodifica RSA, e ricorsioni lineari a coefficienti costanti.
E’ condizione necessaria, ma non sufficiente, per ottenere una valutazione sufficiente
allo scritto, risolvere queste 3 domande correttamente. Le altre domande possono
includere una dimostrazione di un teorema fatto a lezione, ed altri esercizi simili
ad esercizi svolti nel corso. La valutazione delle risposte
degli studenti alle domande d’esame dipende dalla correttezza della procedura
individuata per la soluzione del quesito, dall’adeguatezza della soluzione proposta
in relazione alle competenze che lo studente si presuppone abbia acquisito alla fine
del corso, e dalla correttezza della risposta fornita. Peso diverso viene assegnato ad
errori di conto, ed ad errori di concetto. Viene valutata anche la chiarezza espositiva.
La valutazione finale dello scritto viene espressa attraverso un voto da 0 a 32
ottenuto sommando il punteggio ottenuto dallo studente in ogni domanda. Ogni
domanda vale 4 punti. I risultati di ogni prova scritta vengono pubblicati, anonimamente
tramite numero di matricola, sul Canale Teams del corso. Lo studente e' ammesso
ala prova orale se ha ottenuto un punteggio maggiore od uguale a 18 nell'esame
scritto. La prova orale e' volta a confermare, ed eventualmente modificare
opportunamente, il voto ottenuto nella prova scritta, e puo' includere esercizi e
dimostrazioni.
Testi di riferimento
E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science,
(ocw.mit.edu/courses/electrical-engineering-and-computer-science/
6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf)
Appunti del docente (in Italiano).
Codice insegnamento 8068745