Computer science | DISCRETE MATHEMATICS

Computer science DISCRETE MATHEMATICS

 0512100040 DIPARTIMENTO DI INFORMATICA EQF6 COMPUTER SCIENCE 2017/2018

 OBBLIGATORIO YEAR OF COURSE 1 YEAR OF DIDACTIC SYSTEM 2017 PRIMO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/02 6 48 LESSONS SUPPLEMENTARY COMPULSORY SUBJECTS MAT/02 3 24 EXERCISES SUPPLEMENTARY COMPULSORY SUBJECTS

 GIOVANNI VINCENZI T
Objectives
1.KNOWLEDGE AND UNDERSTANDING: THIS COURSE WILL PROVIDE FUNDAMENTAL CONCEPTS OF THE DISCRETE STRUCTURES, WITH EMPHASYS ON APPLICATIONS. STUDENTS WILL GET USED TO FORMALIZE PROBLEMS PROPERLY AND TO THINK STRICTLY.
2.APPLYING KNOWLEDGE AND UNDERSTANDING: COURSE AIMS IS ALSO TO ENABLE STUDENTS TO SOLVE SIMPLE PROBLEMS AND EXERCISES APPLYING THE ACQUIRED THEORETICAL KNOWLEDGE. IN PARTICULAR, STUDENTS SHOULD BE ABLE TO PERFORM SET AND MATRICES OPERATIONS, TO FIND CORRESPONDENCES, APPLICATIONS, ORDINGS AND LATTICES, EQUIVALENCE RELATIONS, PARTITIONS, ALGEBRAIC STRUCTURES AND SUBSTRUCTURES, TO USE THE EUCLIDEAN ALGORITHM AND THE INDUCTION PRINCIPLE, TO SOLVE SYSTEMS OF LINEAR AND CONGRUENTIAL EQUATIONS, TO DETERMINE BASES AND DIMENSION OF A VECTOR SPACE, CARTESIAN AND PARAMETRIC EQUATIONS OF LINES AND PLANES IN THE EUCLIDEAN SPACE.
3.MAKING JUDGEMENTS: STUDENTS ARE GUIDED TO LEARN IN A CRITICAL AND RESPONSIBLE WAY WHAT IS EXPLAINED IN THEIR CLASS AND TO IMPROVE THEIR SKILLS ASSESSMENT THROUGH THE STUDY OF MATERIALS PROVIDED BY THE TEACHER.
4.COMMUNICATION SKILLS: AT THE END OF THE COURSE STUDENTS MUST BE ABLE TO FORMULATE PROPERLY DEFINITIONS AND THEOREMS CONCERNING THE CONTENTS OF THE COURSE, AND TO USE DEMONSTRATIVE TECHNIQUES OF ELEMENTARY CHARACTER.
5.LEARNING SKILLS: STUDENTS WILL GAIN KNOWLEDGE THAT MAKES IT POSSIBLE TO LEARN MORE ADVANCED MATHEMATICAL ARGUMENTS, POSSIBLY USED BY OTHER SCIENCES.

Prerequisites
THE KNOWLEDGE OF BASIC MATHEMATICAL TOPICS COVERED IN HIGH SCHOOL COURSES IS REQUIRED.

Contents
SETS. SET OPERATIONS: UNION, INTERSECTION, DIFFERENCE, SYMMETRIC DIFFERENCE, CARTESIAN PRODUCT. THE SET OF SUBSETS OF A SET. PARTITIONS OF A SET. RELATIONS AND MAPS. IMAGES AND INVERSE IMAGES. INJECTIVE, SURJECTIVE, BIJECTIVE MAPS. COMPOSITION OF MAPS. THE INVERSE OF A BIJECTIVE MAP. EQUIVALENCE RELATIONS. EQUIVALENCE CLASSES. QUOTIENT SET. FUNDAMENTAL THEOREM. NATURAL NUMBERS AND INTEGER NUMBERS. THE PRINCIPLE OF MATHEMATICAL INDUCTION. DIVISIBILITY. EUCLIDEAN DIVISION. REPRESENTATION OF NATURAL NUMBERS IN A FIXED BASE. PRIME NUMBERS. THE FUNDAMENTAL THEOREM OF ARITHMETIC. EULER'S THEOREM ON THE EXISTENCE OF INFINITE PRIME NUMBERS. THE GREATEST COMMON DIVISOR AND THE LEAST COMMON MULTIPLE. EXTENDED EUCLIDEAN ALGORITHM. BEZOUT'S THEOREM. CONGRUENCES. LINEAR CONGRUENTIAL EQUATIONS. THE CHINESE REMAINDER THEOREM. MATRICES. MATRIX OPERATIONS: MATRIX SUM, SCALAR MULTIPLICATION, MATRIX PRODUCT, POWERS OF A MATRIX. TRANSPOSE OF A MATRIX. SCALING MATRIX. EQUIVALENT MATRICES. TRIANGULAR MATRIX. INVERTIBLE MATRICES. DETERMINANT OF A SQUARE MATRIX AND ITS REMARKABLE PROPERTIES. THE BINET'S THEOREM. CALCULATION OF THE INVERSE MATRIX OF AN INVERTIBLE MATRIX. THE RANK OF A MATRIX. ALGEBRAIC STRUCTURES. BINARY OPERATIONS IN A SET. MULTIPLICATION TABLE. STABLE SUBSETS AND INDUCED OPERATION. ASSOCIATIVE OPERATIONS. COMMUTATIVE OPERATIONS. IDENTITY ELEMENT. INVERTIBLE ELEMENTS. HOMOMORPHISMS. FUNDAMENTAL CONCEPTS ABOUT SEMIGROUPS, MONOIDS, GROUPS. THE GROUP OF UNITS OF A MONOID. MODULAR ARITHMETIC. FUNDAMENTAL CONCEPTS ABOUT RINGS, INTEGRAL DOMAINS, FIELDS. VECTOR SPACES. SUBSPACES AND GENERATORS. LINEAR DEPENDENCE, BASES AND DIMENSION. LINEAR APPLICATIONS. ISOMORPHIC VECTOR SPACES. SYSTEMS OF LINEAR EQUATIONS. BASIC CONCEPTS AND SOLVING METHODS: CRAMER, GAUSS-JORDAN, ROUCHE-CAPELLI.
DIAGONALIZATION OF A SQUARE MATRIX. EIGENVALUES AND EIGENVECTORS OF A SQUARE MATRIX. EIGENSPACES. SIMILAR MATRICES. DIAGONALIZABLE MATRICES. COMBINATORIAL CALCULUS. THE PRINCIPLE OF ADDITION. THE PRINCIPLE OF INCLUSION-EXCLUSION. THE PRINCIPLE OF MULTIPLICATION. FACTORIAL OF A NATURAL NUMBER. BINOMIAL COEFFICIENTS. DISPOSITIONS. DISPOSITIONS WITH REPETITIONS. PERMUTATIONS. PERMUTATIONS WITH REPETITIONS. COMBINATIONS. ORDER RELATIONS. MINIMAL ELEMENTS AND MAXIMAL ELEMENTS. MINIMUM AND MAXIMUM. UPPER BOUNDS AND LOWER BOUNDS. LEAST UPPER BOUND AND GREATEST LOWER BOUND. HASSE DIAGRAMS. TOTALLY ORDERED SETS. WELL-ORDERED SETS. SUBSETS OF AN ORDERED SET AND INDUCED ORDER. LATTICES. THE LATTICE OF SUBSETS OF A SET. THE LATTICE OF NON-NEGATIVE INTEGERS. SUBLATTICES. DISTRIBUTIVE LATTICES. LATTICES WITH COMPLEMENT. BOOLEN LATTICES. ELEMENTS OF ANALYTICAL GEOMETRY IN THE PLANE AND IN THE SPACE. APPLIED VECTORS AND RELATED OPERATIONS. AFFINE COORDINATES. PARAMETRIC AND CARTESIAN STRAIGHT LINE EQUATIONS IN THE PLANE AND IN THE SPACE. PARAMETRIC AND CARTESIAN PLANE EQUATIONS IN THE SPACE. PARALLELISM, INCIDENCE AND PERPENDICULARITY CONDITIONS.

Teaching Methods
THIS COURSE CONSISTS ON THEORETICAL LESSONS AND EXERCITATIVE LESSONS. DURING THEORETICAL LESSONS STUDENTS LEARN BASIC NOTIONS AND SEVERAL TECHNIQUES TO PROVE RESULTS. DURING EXERCITATIVE LESSONS STUDENT LEARN HOW THE GAINED THEORETICAL KNOWLEDGE MAY BE USED TO SOLVE SIMPLE PROBLEMS.

Verification of learning
THE EXAM CONSISTS OF A WRITTEN TEST, AFTER WHICH STUDENTS CAN GO TO AN ORAL EXAMINATION. A PASSED WRITTEN TEST GIVES ACCESS TO THE ORAL EXAMINATIONS FOR THE WHOLE ACADEMIC YEAR. THE WRITTEN TEST MAY BE REPLACED BY 2 COURSE TESTS, WHICH TAKE PLACE AFTER 6 WEEKS AND AT THE END OF THE COURSE.

Texts
TITLE: ALGEBRA FOR INFORMATIC.
AUTHOR. GIOVANNI VINCENZI
EDITOR: ARACNE, ROME, 2015