DISCRETE MATHEMATICS

The course is one of the basic activities of the Bachelor's Degree in Informatics and its aim is to present the basic ideas and computational techniques of discrete mathematics, in contraposition to the mathematics of continuum. The student will gently be introduced to the abstract concepts of the discrete mathematics. . In covering the basic ideas of discrete mathematics, the abstract ideas are balanced by considerable emphasis on the algebraic and computational aspects of the subject.
The course finally provides the main notions needed in order to understand the theory of formal languages, in particular the theory of binary strings of the language of computer.

Knowledge and understanding:
- knowledge and understanding of the fundamental concepts of discrete mathematics;
- understanding the feasibility and complexity of solving problems of discrete mathematics;
- knowledge of methodologies to compute with integers, integers modulo, and the cardinality of finite sets.

Ability to apply knowledge and understanding:
- to solve concrete problems;
- to apply the induction principle;
- ability of computing in the finite arithmetics of integers, and the usual arithmetics.

Knowledge of the fundamental notions of discrete mathematics: set theory, arithmetics, induction, combinatory.

Any high school diploma to give access to the University.

Introduction to set theory: union, intersection and complementation of sets. Functions and relations. Posets. Equivalence relations and partitions.

Natural numbers. Order on nat. Induction. Definition and proofs by induction. Inductive data types: proofs by induction.


Integers. The theory of congruences.


Combinatorics: the principle of addition and multiplication. The basic figures of combinatorics. Binomial coefficients: their properties. Fibonacci sequence.

N.L. Biggs, Discrete Mathematics, Oxford University Press

Fabio Bellissima, Franco Montagna, Matematica per l'Informatica, Carocci editore.

David M. Burton Elementary Number Theory, Allyn and Bacon, Inc.

Lecture notes by Prof. Salibra

The exam consists of a written test. The written test lasts three hours and it is composed by four exercises aimed at verifying:
1) the capability to compute with integers and integers modulo;
2) the ability to compute the cardinality of finite sets;
3) the knowledge and the capability to apply the induction principle;
4) the ability to formalise in the mathematical and set-theoretical language.

During the written test is not allowed the use of books, notes, electronic media.

Lessons with the digital and traditional blackboard.
Written home work and exercises in the classroom are able to gently introduce the student to discrete mathematics:
sets and Boolean algebras, Arithmetics of integers and modular arithmetics. Combinatory.

Italian

written