MATEMATICA DISCRETA
$\bf 1^o$ modulo nel secondo semestre

Domenico Luminati

a.a. 1998/99

Questo è il programma di massima del corso. Alcune parti potranno essere eventualmente cambiate e/o tagliate per esigenze di tempo.

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 n
• equazioni alle ricorrenze finite (caso del polinomio caratteristico con radici distinte)

2.

Calcolo combinatorio

• contare gli elementi di particolari insiemi (prodotti cartesiani, applicazioni, parti)
• combinazioni, disposizioni, permutazioni
• principio di inclusione ed esclusione

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
• equazioni alle ricorrenze finite (caso del polinomio caratteristico con radici multiple)
• nozioni elementari di algebra universale: inquadramento generale delle varie 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 $\times$ 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 ed.