Home page del corso
Matematica Discreta (parte 1)
Docente Prof. Giuseppe Lancia

Programma

-Cenni di algebra booleana, logica, teoria degli insiemi e funzioni. Relazioni e equivalenze. Aritmetica modulare. Sommatorie e loro manipolazioni. Il principio di induzione. Ricorrenze e formule ricorsive. Cenni di teoria delle probabilita'.
-Aritmetica intera, quoziente e resto, scomposizione in fattori primi. MCD e mcm. Algoritmo di Euclide. Cenni di teoria dei numeri. Numeri primi e fattorizzazione. Il piccolo teorema di Fermat. Argomenti di parita' e di simmetria. Il segno delle permutazioni.
-Elementi di Combinatorica. Disposizioni, permutazioni, sequenze (stringhe). Coefficiente binomiale e triangolo di Pascal. Il principio della piccionaia. Tecniche per contare. Numeri di Fibonacci. Il principio di inclusione-esclusione. Gli spiazzamenti. Generazione di tutti i sottoinsiemi/permutazioni e di sottoinsiemi/permutazioni casuali.
-Teoria dei grafi. Definizioni fondamentali. Grafi euleriani e hamiltoniani. Grafi bipartiti. Connessione. Alberi. Grafi orientati. Grafi pesati. Cliques e insiemi indipendenti. Problemi combinatorici su grafi. Il minimo albero di supporto.

APPELLI: 1'APPELLO : XX/XX (14:00). 2'APPELLO : XX/XX (14:00). AULA DA COMUNICARSI - DATE ORALI (EVENTUALI) DA STABILIRSI

ORARIO DEI CORSI: MAR, GIO, VEN 14:30-16:30, aula I

ORARIO RIC. GIO H 17:00 (previa comunicazione, via email: giuseppe.lancia@uniud.it)

Dispensa

Premere qui per scaricare la parte introduttiva (logica, insiemi, funzioni, relazioni, somme...)

Premere qui per scaricare la parte su teoria dei numeri e parita'

Premere qui per scaricare la parte sulla combinatorica

Premere qui per scaricare la parte sulla teoria dei grafi

Ultimo aggiornamento : 17-10-12

Ulteriore dispensa (in Inglese):

- "Discrete Mathematics"
L. Lovasz e K. Vesztergombi
(download)

Ulteriori link utili (dispense MD presso altri atenei):

Corso Baratter /Genova

corso Niesi /Genova

Corso Albano-Burzio /Torino

Altri testi consigliati:

- Parti di "Mathematical Thinking - Problem solving and proofs"
di J. P. D'Angelo e D. B. West
Prentice Hall

Consultazione

- "Introductory Combinatorics"
di  A. Brualdi
North Holland

- Parti di "Introduction to Algorithms"
di T. Cormen, C. Leiserson, R. Rivest
MIT press


Programma dettagliato day by day

GIORNO 1

Introduzione. Problemi con un gruppo di persone a un party. Quante strette di mano, quanti modi di sedersi, quante coppie per ballare... Primi ragionamenti e prime formule. Permutazioni.La crescita delle funzioni esponenziale e fattoriale. Ordini di grandezza e potenze di 10.

GIORNO 2

Elementi di logica e algebra booleana. Gli operatori AND, OR e NOT. Implicazioni logiche, premesse e conclusioni. Sillogismi. Le dimostrazioni, le dimostrazioni per assurdo. Teoremi "se e solo se". Esempi.

GIORNO 3

Insiemi e loro proprieta'. Diagrammi di Venn. Cardinalita' e inclusione. Complementare e leggi di De Morgan. Insieme delle parti. Insieme prodotto. Vettori (n-ple). Esercizi ed esempi.

GIORNO 4

Relazioni binarie e loro pincipali proprieta'. Esempi. Equivalenze e insieme quoziente. Divisione intera e congruenza modulo n. Aritmetica modulare.

GIORNO 5

Applicazioni (funzioni) e loro proprieta' (iniettive, suriettive, biiettive). Immagine e contro-immagine. Composizione di funzioni. Esempi ed esercizi.

GIORNO 6

Principio di induzione matematica. Formulazioni alternative del principio. Esempi: Somma dei primi n dispari e dei primi n naturali. Esempi di errori nell'applicazione dell'induzione. Esercizi.

GIORNI 7 e 8

Somme e loro manipolazioni. Sostituzione di indici. Somme multiple. Spezzare e raggruppare le somme. Esempi di somme importanti: la somma di primi n naturali e dei primi n quadrati. Metodo "geometrico" e "analitico" per la loro determinazione. Somma delle prime n potenze. Esercizi. Cenni di teoria delle probabilita'. Variabili casuali e valor medio.

GIORNO 9

Argomenti di parita' e di simmetria. La parita' degli interi. Problemi di tiling con tasselli quadrati e rettangolari. Il giro del cavallo e condizioni necessarie alla sua esistenza. Il segno delle permutazioni: inversioni di elementi e trasposizioni. Il gioco del 15 e configurazioni irraggiungibili.