MATEMATICA DISCRETA
1° modulo nel secondo semestre
A.A. 1998/99
Dott. Domenico Luminati
1. I numeri interi
-
induzione
-
divisibilità, massimo comun divisore e minimo comune multiplo, fattorizzazione
unica
-
scrittura b-adica dei numeri
-
congruenze, classi di resto modulo un intero
-
equazioni alle ricorrenze
2. Calcolo combinatorio
-
contare gli elementi di particolari insiemi (prodotto cartesiano, applicazioni,
sottinsiemi, k-sottin-siemi, applicazioni iniettive, permutazioni)
-
principio di inclusione ed esclusione (applicazioni surgettive)
3. Permutazioni
-
composizione di permutazioni
-
decomposizione in cicli disgiunti
-
decomposizione in prodotto di trasposizioni, segno di una permutazione.
4. Strutture algebriche
-
Insiemi parzialmente ordinati, reticoli
-
semigruppi, monoidi, gruppi, anelli
-
quozienti, omomorfismi, primo teorema di omomorfismo
-
azioni
-
polinomi, teorema di Ruffini, molteplicità di una radice
-
ancora sulle equazioni alle ricorrenze
-
nozioni elementari di algebra universale: un inquadramento generale delle
strutture esaminate
5. Grafi
-
alberi e foreste, alberi generatori
-
grafi pesati
-
grafi euleriani e grafi hamiltoniani
-
grafi diretti, reti
Testi consigliati
1. P. J. Cameron, Combinatorics: Topics, tecniques, algorithms, Cambridge
University Press
2. A. Facchini, Algebra per informatica, Decibel-Zanichelli
3. I. N. Herstein, Algebra, Editori Riuniti
4. N. Jacobson, Basic Algebra I, W. H. Freeman and Company
5. B. Scimemi, Algebretta, Decibel