Unit DISCRETE MATHEMATICS
- Course
- Informatics
- Study-unit Code
- GP004143
- Location
- PERUGIA
- Curriculum
- In all curricula
- Teacher
- Giuliana Fatabbi
- CFU
- 12
- Course Regulation
- Coorte 2017
- Offered
- 2017/18
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa integrata
DISCRETE MATHEMATICS - MOD. I
| Code | GP004150 |
|---|---|
| Location | PERUGIA |
| CFU | 6 |
| Teacher | Daniele Bartoli |
| Teachers |
|
| Hours |
|
| Learning activities | Base |
| Area | Formazione matematico-fisica |
| Academic discipline | MAT/02 |
| Type of study-unit | Obbligatorio (Required) |
| Language of instruction | Italian |
| Contents | Sets and mappings. Equivalence relations, partitions. Induction. Combinatorial Analysis. Ordered sets. Integers: divisors, Euclid's division. Bezout's identity. Congruence mod n. Chinese Remainder Theorem. An introduction to Graph theory: degree, walks, connectedness. Polynomials. FiniteFields. |
| 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 |
| Learning verification modality | 6 partial exams and one final exam. |
| 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. 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 |
|---|---|
| Location | PERUGIA |
| CFU | 6 |
| Teacher | Giuliana Fatabbi |
| Teachers |
|
| Hours |
|
| Learning activities | Base |
| Area | Formazione matematico-fisica |
| Academic discipline | 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. In each lesson about half of the time will be devoted to solving problems and exercises |
| Learning verification modality | The exam includes a written test and an oral exam.The written test consists of two separate parts, each relating to one of the two modules. Each part consists in solution of 3/4 exercises and in the answers to some theoretical questions. The test has a duration not exceeding 240 minutes. It is designed to test the ability to solve problems related to the topics of the course and the ability to communicate in writing.The oral exam consists of a discussion of the written test lasting up to 20 minutes. In the event that the result of the written test is not fully sufficient, the oral test ensures the level of knowledge and understanding achieved by students on the theoretical and methodological implications mentioned in the program.The exam as a whole allows us to ensure both the ability of knowledge and understanding, the ability to apply the acquired skills, the ability to display, and the ability to learn and develop solutions for independent judgment. |
| 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. |