CORSO CHIUSO
Nell'anno 2015-16 il corso sara' tenuto dal prof. Gavarini
ORARIO
1o semestre: 6 ottobre 2014 - 30 gennaio 2015.
LUNEDI
MARTEDI
MERCOLEDI
GIOVEDI
VENERDI
ore 9 - 11
Lezione Aula T5
Lezione Aula T5
ore 11-13
Lezione Aula T5
Ricevimento: su appuntamento, Ufficio Geatti (Studio 0122, tel.72594628 -Edificio Sogene,
qui ) o per posta elettronica.
PROGRAMMA
Obiettivi formativi: Introdurre lo studente alle strutture matematiche discrete usate in informatica.
Programma sintetico: Insiemi e operazioni sugli insiemi. Funzioni iniettive, suriettive, invertibili. Permutazioni di un insieme.
Relazioni. Relazioni di ordine. Relazioni di equivalenza su un insieme, classi di equivalenza, insieme quoziente. Relazioni di equivalenza e partizioni.
Aritmetica sui numeri interi: divisione con resto, massimo comun divisore, algoritmo euclideo. Numeri primi, Teorema Fondamentale dell'Aritmetica. Congruenze e sistemi di congruenze. Teorema cinese del resto. Aritmetica modulare. L'anello Zn, il campo Zp, con p primo. Teorema di Lagrange, Piccolo Teorema di Fermat. Applicazioni: sistema crittografico a chiave pubblica RSA.
Numeri naturali, interi, razionali, reali. I numeri complessi:
somma, prodotto e quoziente di numeri complessi. Il
coniugato e la norma di un numero complesso.
Il Principio di
Induzione Matematica. Funzioni ricorsive.
Equazioni alle differenze finite lineari a coefficienti costanti.
Cardinalita' di un insieme. Insiemi finiti, insiemi infiniti numerabili e non numerabili. Cardinalita' del continuo.
Calcolo combinatorio: permutazioni di un insieme di n elementi, sviluppo del binomio di Newton e coefficienti binomiali, identita' di Tartaglia. Principi di conteggio: regola della somma e del prodotto (cardinalita' dell'unione disgiunta e del prodotto cartesiano), principio di inclusione esclusione. Pigeon hole principle. k-sottoinsiemi ordinati e k-sottoinsiemi non ordinati di un insieme di n elementi; k-stringhe ordinate e k-stringhe non ordinate di n simboli con ripetizioni. Partizioni di un unsieme di n elementi: numeri di Bell e numeri di Stirling di seconda specie. La relazione di ricorrenza soddisfatta numeri di Bell e dai numeri Stirling di seconda specie.
Grafi e multigrafi, grafi e multigrafi diretti, grado di un vertice, lemma delle strette di mano. Sottografi. Isomorfismi di grafi. Cammini e circuiti su un grafo. Grafi connessi: esistenza di un cammino semplice fra due vertici in un grafo connesso. Circuiti e cammini euleriani. Caratterizzazione dei grafi che ammettono un circuito o un cammino euleriano (senza dim.). Condizioni sufficienti all'esistenza di circuiti hamiltoniani su un grafo: teoremi di Ore e Dirac (senza dim.). Alberi. Albero generatore in un grafo connesso. Grafi bipartiti e accoppiamenti. Teorema di Hall. Colorazioni di un grafo e numero cromatico. Polinomio cromatico di un grafo. Il Teorema di Cancellazione-Contrazione.
Diario settimanale e Programma dettagliato.
Riferimenti bibliografici:
K. Rosen, Discrete mathematics and its applications,
McGraw-Hill International Editions
E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science,
pdf
S. Lipschutz, M. Lipson, Matematica discreta,
Etas Libri, Milano 1985.
S. Lipschutz, M. Lipson, Discrete Mathematics,
Schaum's Outlines, McGraw-Hill 1997.
Registrazioni video delle lezioni del corso di Elementi di Algebra e Logica, tenute dal prof. Giuseppe Pareschi: su YouTube (corso quasi completo) link
Videolezioni Prof. Pareschi (n.15 & n.19) su GoogleDrive Lez.15 Lez.19
Mathematics for Computer Science, MIT-OPEN-COURSEWARE link al corso
Discrete Mathematics for Computer Science, Univ. of California Berkeley link al corso
PARI/GP
computer algebra system for doing fast computations in number theory.
L'esame consiste in un compito scritto.
Per superare l'esame e'
necessario fare un compito scritto sufficiente (voto almeno 18)
Per partecipare agli scritti, è necessario iscriversi mediante il sito Delphi.
Presentarsi con un documento di
riconoscimento.
Non e' consentito uscire durante gli scritti.
Non sono consentiti libri, appunti, ne' alcun tipo di apparecchio on-off. Gli studenti possono partecipare a tutti gli appelli.
Partecipare ad un appello annulla i voti precedenti. Chi entra consegna.
Diario settimanale e Programma dettagliato. 
