Marialaura NOCE | DISCRETE MATHEMATICS

cod. 0512100040

DISCRETE MATHEMATICS

	0512100040
	COMPUTER SCIENCE
	EQF6
	COMPUTER SCIENCE
	2023/2024

PERCORSO COMUNE

	OBBLIGATORIO
	YEAR OF COURSE 1
	YEAR OF DIDACTIC SYSTEM 2017
	AUTUMN SEMESTER

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
MAT/02	6	48	LESSONS	SUPPLEMENTARY COMPULSORY SUBJECTS
MAT/02	3	24	EXERCISES	SUPPLEMENTARY COMPULSORY SUBJECTS

PROFESSORS

	SERAFINA LAPENTA Curriculum
	MARIALAURA NOCE Curriculum

	Objectives
	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. APPLYING KNOWLEDGE AND UNDERSTANDING: COURSE AIMS 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.

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.
APPLYING KNOWLEDGE AND UNDERSTANDING:
COURSE AIMS 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.

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

	Contents
	THE TOPICS OF THE COURSE ARE GROUPED IN 12 UNITS. TO EACH OF THEM WILL BE DEDICATED ABOUT 6 HOURS OF LESSON AND / OR EXERCISES. 1. SETS. SET OPERATIONS: UNION, INTERSECTION, DIFFERENCE, SYMMETRIC DIFFERENCE, CARTESIAN PRODUCT. THE SET OF SUBSETS OF A SET. PARTITIONS OF A SET. 2. RELATIONS AND MAPS. IMAGES AND INVERSE IMAGES. INJECTIVE, SURJECTIVE, BIJECTIVE MAPS. COMPOSITION OF MAPS. THE INVERSE OF A BIJECTIVE MAP. 3. REAL 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. SUBMATRICES AND MINORS OF A MATRIX. THE KRONECKER THEOREM. 4. EQUIVALENCE RELATIONS. EQUIVALENCE CLASSES. QUOTIENT SET. FUNDAMENTAL THEOREM. 5. 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. EUCLID'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. 6. 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. 7. 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. 8. 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. 9. SYSTEMS OF LINEAR EQUATIONS. BASIC CONCEPTS AND SOLVING METHODS: CRAMER, GAUSS-JORDAN, ROUCHE-CAPELLI. 10. VECTOR SPACES. SUBSPACES AND GENERATORS. LINEAR DEPENDENCE, BASES AND DIMENSION. LINEAR APPLICATIONS. KERNEL AND IMAGE, AND THEIR DIMENSIONS. 11. DIAGONALIZATION OF A SQUARE MATRIX. EIGENVALUES AND EIGENVECTORS OF A SQUARE MATRIX. EIGENSPACES. SIMILAR MATRICES. DIAGONALIZABLE MATRICES. 12. 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 AND INCIDENCE CONDITIONS.

Contents

THE TOPICS OF THE COURSE ARE GROUPED IN 12 UNITS. TO EACH OF THEM WILL BE DEDICATED ABOUT 6 HOURS OF LESSON AND / OR EXERCISES.
1. SETS. SET OPERATIONS: UNION, INTERSECTION, DIFFERENCE, SYMMETRIC DIFFERENCE, CARTESIAN PRODUCT. THE SET OF SUBSETS OF A SET. PARTITIONS OF A SET.
2. RELATIONS AND MAPS. IMAGES AND INVERSE IMAGES. INJECTIVE, SURJECTIVE, BIJECTIVE MAPS. COMPOSITION OF MAPS. THE INVERSE OF A BIJECTIVE MAP.
3. REAL 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. SUBMATRICES AND MINORS OF A MATRIX. THE KRONECKER THEOREM.
4. EQUIVALENCE RELATIONS. EQUIVALENCE CLASSES. QUOTIENT SET. FUNDAMENTAL THEOREM.
5. 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. EUCLID'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.
6. 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.
7. 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.
8. 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.
9. SYSTEMS OF LINEAR EQUATIONS. BASIC CONCEPTS AND SOLVING METHODS: CRAMER, GAUSS-JORDAN, ROUCHE-CAPELLI.
10. VECTOR SPACES. SUBSPACES AND GENERATORS. LINEAR DEPENDENCE, BASES AND DIMENSION. LINEAR APPLICATIONS. KERNEL AND IMAGE, AND THEIR DIMENSIONS.
11. DIAGONALIZATION OF A SQUARE MATRIX. EIGENVALUES AND EIGENVECTORS OF A SQUARE MATRIX. EIGENSPACES. SIMILAR MATRICES. DIAGONALIZABLE MATRICES.
12. 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 AND INCIDENCE CONDITIONS.

	Teaching Methods
	THIS COURSE CONSISTS ON 6 CFU (48 HOURS) THEORETICAL LESSONS AND 3 CFU (24 HOURS) 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 AND AN ORAL TASK. EVERY WRITTEN TEST CONSISTS OF 4-6 EXERCISES FOR A TOTAL OF 30 POINTS. STUDENTS ARE ADMITTED TO THE ORAL PART IF THEY OBTAIN A SCORE AT LEAST 15 IN THE WRITTEN TEST. THE ORAL PART CONCERNS EVERY TOPIC COVERED IN THE COURSE. STUDENTS MUST DEMONSTRATE FIRST TO KNOW CONCEPTS AND DEFINITIONS INTRODUCED IN THE COURSE AND TO HAVE UNDERSTOOD THEM, BY BUILDING EXAMPLES IN AN INDEPENDENT WAY. THEN, THEY WILL BE ASKED QUESTIONS SO TO UNDERSTAND WHETHER THEY KNOW HOW TO USE CONCEPTS AND DEFINITIONS AND KNOW THE FUNDAMENTAL PROPERTIES TREATED IN THE COURSE (APPLICATION OF DEFINITIONS AND THEOREMS IN PROBLEM SOLVING, PROOF OF THEOREMS). THE FINAL SCORE IS FROM 0/30 TO 30/30 WITH POSSIBLE HONORABLE MENTION. THE EXAM IS SUCCESSFUL FROM 18/30 ON. 18/30 IS GIVEN TO THOSE STUDENTS THAT DEMONSTRATE TO KNOW THE FUNDAMENTAL CONCEPTS AND DEFINITIONS AND TO UNDERSTAND THEM BY MEANS OF EXAMPLES. THE FULL SCORE 30/30 WILL BE GIVEN TO THE STUDENTS THAT SHOW A COMPLETE AND DEEP UNDERSTANDING OF ALL TOPICS OF THE COURSE. THE HONORABLE MENTION CAN BE GIVEN TO THOSE STUDENTS THAT SHOW TO BE ABLE TO APPLY AUTONOMOUSLY KNOWLEDGE AND ABILITY OUTSIDE THE CONTEXTS SEEN IN THE CLASSROOM AND TO BE ABLE TO PROVE THE THEOREMS SEEN IN THE CLASSROOM IN A FORMALLY CORRECT WAY.

Verification of learning

THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL TASK. EVERY WRITTEN TEST CONSISTS OF 4-6 EXERCISES FOR A TOTAL OF 30 POINTS. STUDENTS ARE ADMITTED TO THE ORAL PART IF THEY OBTAIN A SCORE AT LEAST 15 IN THE WRITTEN TEST.

THE ORAL PART CONCERNS EVERY TOPIC COVERED IN THE COURSE. STUDENTS MUST DEMONSTRATE FIRST TO KNOW CONCEPTS AND DEFINITIONS INTRODUCED IN THE COURSE AND TO HAVE UNDERSTOOD THEM, BY BUILDING EXAMPLES IN AN INDEPENDENT WAY. THEN, THEY WILL BE ASKED QUESTIONS SO TO UNDERSTAND WHETHER THEY KNOW HOW TO USE CONCEPTS AND DEFINITIONS AND KNOW THE FUNDAMENTAL PROPERTIES TREATED IN THE COURSE (APPLICATION OF DEFINITIONS AND THEOREMS IN PROBLEM SOLVING, PROOF OF THEOREMS).

THE FINAL SCORE IS FROM 0/30 TO 30/30 WITH POSSIBLE HONORABLE MENTION. THE EXAM IS SUCCESSFUL FROM 18/30 ON. 18/30 IS GIVEN TO THOSE STUDENTS THAT DEMONSTRATE TO KNOW THE FUNDAMENTAL CONCEPTS AND DEFINITIONS AND TO UNDERSTAND THEM BY MEANS OF EXAMPLES.

THE FULL SCORE 30/30 WILL BE GIVEN TO THE STUDENTS THAT SHOW A COMPLETE AND DEEP UNDERSTANDING OF ALL TOPICS OF THE COURSE. THE HONORABLE MENTION CAN BE GIVEN TO THOSE STUDENTS THAT SHOW TO BE ABLE TO APPLY AUTONOMOUSLY KNOWLEDGE AND ABILITY OUTSIDE THE CONTEXTS SEEN IN THE CLASSROOM AND TO BE ABLE TO PROVE THE THEOREMS SEEN IN THE CLASSROOM IN A FORMALLY CORRECT WAY.

	Texts
	C. DELIZIA, P. LONGOBARDI, M. MAJ AND C. NICOTERA, MATEMATICA DISCRETA, MCGRAW-HILL, 2009

	More Information
	FURTHER INFORMATION CAN BE DETECTED ON THE WEB SITE OF THE TEACHER OF EACH CLASS.

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-12-17]

Marialaura NOCE | DISCRETE MATHEMATICS