**1st module**

**A.A. 1998/99**

**Dott. Domenico Luminati**

1. The integers

- induction
- division, greatest common divisor and least common multiple, unique factorization
- b-adic expression of an integer
- congruence modulo n and congruence classes
- recurrence relations

- counting the number of elements of some simple sets (cartesian product, subsets, maps, k-sub-sets,injective maps, permutations)
- the principle of inclusion and exclusion (surjective maps)

- composition of permutations
- decomposition as product of disjoint cycles
- decomposition as product of transpositions, sign of a permutation

- partially ordered sets and lattices
- semigroups, monoids, groups, rings
- quotients, morphisms, fundamental theorem of homomorphism
- actions polynimials, remainder theorem, multyplicity of a root
- more recurrence relations
- basic notion in universal algebra: a general setting for the studied structures

- trees and foresta, spanning trees
- weighted graphs
- eulerian and hamiltonian graphs
- directes graphs and networks

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 ed.