Università degli Studi di Perugia

Skip to content

Study-unit DISCRETE MATHEMATICS

Course name Informatics
Study-unit Code GP004143
Curriculum Comune a tutti i curricula
Lecturer Daniele Bartoli
CFU 12
Course Regulation Coorte 2019
Supplied 2019/20
Supplied other course regulation
Type of study-unit Obbligatorio (Required)
Type of learning activities Attività formativa integrata
Partition

DISCRETE MATHEMATICS - MOD. I

Code GP004150
CFU 6
Lecturer Daniele Bartoli
Lecturers
  • Daniele Bartoli - Didattica Ufficiale
Hours
  • 42 Hours - Didattica Ufficiale - Daniele Bartoli
Learning activities Base
Area Formazione matematico-fisica
Sector MAT/02
Type of study-unit Obbligatorio (Required)
Language of instruction Italian
Contents Sets and mappings. Equivalence relations, partitions. Induction. Combinatorial Analysis. Ordered sets.
Algebraic Structures.
Integers: divisors, Euclid's division. Bezout's identity.
Congruence mod n. Chinese Remainder Theorem.
An introduction to Graph theory: degree, walks, connectedness. Polynomials. Finite Fields.
Reference texts G.M. Piacentini Catteneo, "Matematica Discreta e applicazioni", Zanichelli
Educational objectives The module is the first course in Discrete Mathematics.
The main goal of the course is to provide students with the basics of discrete mathematics that will be useful for studying computer science subjects in the subsequent years of the course.
The main knowledge gained will be:
-Familiarity with the language of propositional logic
-Familiarity with different types of proofs
-Familiarity with modular arithmetic
-Familiarity with the language of graph theory
The main skills (ie the ability to apply their knowledge) will be:
- Performing simple proof by induction
- Solving equations and linear systems in modular arithmetic
- Solving counting problems in combinatorics
- Factoring polynomials defined over finite fields
- Recognizing the main properties of a graph
Prerequisites None
Teaching methods The course consists of classroom lectures on all topics of the course. In each lesson about half of the time will be devoted to solving problems and exercises
Other information http://www.unipg.it/disabilita-e-dsa
Learning verification modality The final mark is obtained summing the marks of 4 partial exams (30 minutes each) on
- Induction and relations
- Combinatorial calculation
- Systems of equations in Zn
- Graphs


a final exam which consists of 5 exercises and a theoretical exercise.¿Each of the 4 partial exams can be repeated once per week and only the best score for each type is considered. Each of the partial exams gives between 0 and 10 points, the final exam from 0 to 60. Also, at most five extra points are given to the students for their active participation. Before the final exam the student must pass a test consisting of 10 questions about definitions and stametents of theorems. The student must answer correctly at 8 questions at least in 20 minutes and the questions will be taken from an online database of roughly 70 questions availlable in advance for the students.¿The final mark is the scaled between 0 and 30.
Extended program Sets, inclusion, set operations. Power set. Complement. De Morgan's laws.
Mappings. Injective and surjective mappings. Bijections. Inverse mapping. Product of mappings.
Binary relations. Equivalence relations. Partitions.
Order relations. Total and partial order.

Natural numbers: order and operations. Divisibility. Prime numbers. Induction.
Finite cardinals. Combinatorial Analysis, Newton's binomial theorem.


Definitions of semigroup, monoid, ring, fields. Cancellative and invertible elements. Definition of group, ring, field.
Ring of integers. Divisibility. Euclidean division. Greatest common divisor and least common multiple.
Euclidean Algorithm. Bézout's identity.

Congruence modulo n. Rings of congruence classes: 0-divisors, invertible elements, modular inversion.
Solution of linear congruence equations. Chinese Remainder Theorem.

Graphs, subgraphs, isomorphisms of graphs. Degree. Adjacency matrix.
Walks and their classification. Eulerian paths and circuits.Graph coloring, bipartite graphs, complete bipartite graphs.
Polynomials. Polynomials over the rationals, the reals and over the complex numbers. Finite Fields.

DISCRETE MATHEMATICS - MOD. II

Code GP004151
CFU 6
Lecturer Daniele Bartoli
Lecturers
  • Daniele Bartoli - Didattica Ufficiale
Hours
  • 42 Hours - Didattica Ufficiale - Daniele Bartoli
Learning activities Base
Area Formazione matematico-fisica
Sector MAT/03
Type of study-unit Obbligatorio (Required)
Language of instruction ITALIAN
Contents Matrices. Vector spaces and linear maps. Eigenvectors and eigenvalues. Permutations
Reference texts M.C. Vipera, Matematica discreta, Margiacchi-Galeno editore Serge Lang, Introduction to Linear Algebra, Springer
Educational objectives The students should become familiar with the basic concepts and notions of algebra and linear algebra in order to use them either in theoretical informatic or in applications.
Prerequisites The course is held in the first semester of the first year. There are not any prerequisites with the exception of some interest in mathematical investigations
Teaching methods The course consists of classroom lectures on all topics of the course.Some time will be devoted to solving problems and exercises
Other information http://www.unipg.it/disabilita-e-dsa
Learning verification modality The final mark is obtained summing the marks of 4 partial exams (30 minutes each) on
- Linear Systems,
- Matrices,
- Homomorphisms,
- Diagonalization of Matrices
and a final exam which consists of 5 exercises and a theoretical exercise.¿Each of the 4 partial exams can be repeated once per week and only the best score for each type is considered. Each of the partial exams gives between 0 and 10 points, the final exam from 0 to 60. Also, at most five extra points are given to the students for their active participation. Before the final exam the student must pass a test consisting of 10 questions about definitions and stametents of theorems. The student must answer correctly at 8 questions at least in 20 minutes and the questions will be taken from an online database of roughly 70 questions availlable in advance for the students.¿The final mark is the scaled between 0 and 30.
Extended program Vector spaces. Matrices over a field. Linear systems: elimination theory, Cramer theorem.Linear maps. Linear maps and matrices. Eigenvectors and eigenvalues. Groups. Permutations.
Go top
Table of content
×