DISCRETE MATHEMATICS
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
2. Combinatorics
-
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)
3. Permutations
-
composition of permutations
-
decomposition as product of disjoint cycles
-
decomposition as product of transpositions, sign of a permutation
4. Algebraic structures
-
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
5. Grafi
-
trees and foresta, spanning trees
-
weighted graphs
-
eulerian and hamiltonian graphs
-
directes graphs and networks
Suggested references
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.