DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCES
Bachelor's Degree in Computer Science
Academic Year 2019/2020 - 1° Year - Elaborazione Dati e Applicazioni Curriculum and Sistemi e Applicazioni Curriculum

MATEMATICA DISCRETA M - Z

Teaching Staff

Learning Objectives

• ALGEBRA LINEARE E GEOMETRIA
  
  • Knowledge and understanding: The aim of the course is to give the basics of linear algebra and analytic geometry that are useful to interpret and describe problems in computer science.
  • Applying knowledge and understanding: the student will acquire the skills necessary to deal with typical issues of discrete mathematics, solving classical problems where standard techniques are required.
  • Making judgements: the student will be able to independently develop solutions to the main problems of the course by choosing the most convenient strategy based on the learning outcomes.
  • Communication skills: the student will acquire the necessary communication skills by acquiring the specific language of linear algebra and geometry.
  • Learning skills: The aim of the course is to provide the study method to the students, the forma mentis and the logical rigor that will be needed in order to solve autonomously new problems that may arise during a work activity.
• STRUTTURE DISCRETE
  

  Knowledge and understanding: Studenta will acquire the basic notions of discrete mathematical structures that are at the basis of computer science, and that are used to interpret and describe the relative problems.

  Applying knowledge and understanding: Students will acquire the necessary skills to tackle and analyze, from a theoretical point of view, typical problems in computer science and, in particular, in the design of algorithms, and in solving problems in which the application of standard techniques is required.

  Making judgements: students will be able to independently develop solutions to the main problems covered in the course, by choosing the most convenient strategy based on the results learned.

  Communication skills: students will acquire the necessary communication skills and the specific language of discrete mathematics, and its use in computer science.

  Learning skills: the aim of the course is to provide students with the study method, the mindset and the logical rigor that will be necessary for them to be able to face and solve new problems that may arise during their work as computer scientists.

Course Structure

• ALGEBRA LINEARE E GEOMETRIA
  

  Traditional (teacher up front) lessons.

• STRUTTURE DISCRETE
  

  The course will be taught in the classroom for a total of 48 hours.

Detailed Course Content

• ALGEBRA LINEARE E GEOMETRIA
  
  1. Calculation of matrix algebra and linear systems. Matrices. Matrix operations. Linear systems *. Calculating the inverse matrix. Determinant of a square matrix and its properties. Rank of a matrix. Cramer's theorem and Rouche-Capelli.
  2. Vector spaces. Subspaces and transactions between them. Subspace sum. Linear independence and linear dependence. Bases and dimension of a vector space. Eigenvalues and eigenvectors. Characteristic polynomial. Research of the eigenvalues and eigenspaces associated with them. Similarity between matrices. Diagonalizable matrices.

  1. Vector Calculus. Applied vectors. Decomposition theorem. Scalar product and cross product. Mixed product. Free vectors.
  2. Linear geometry in the plane. Lines in the plane and their equations. Parallelism and squareness. Intersection between plane and lines. Homogeneous coordinates in the plane. Bundles of straight.
  3. Isometries. Translation, rotation around a point. Reflection.
  4. Linear geometry in space. Planes and lines in space and their equations. Parallelism and squareness. Intersection between planes, between a plane and a straight line and between lines. homogeneous coordinates in space. Improper points and lines in space. Bundles of plans.
  5. Conics and their associated matrices. Orthogonal Invariants. Irreducible and degenerate conics. Discriminant of a conic. Canonical reduction of a conic. Parabolas, Ellipses, Hyperbolas equations, center and axis. Circumferences, Tangents of conics.
• STRUTTURE DISCRETE
  

  The course, for a total of 6 CFU, is divided into 4 parts of different sizes, as outlined below.

  Each of the parts ends with one or more case studies of particular importance.

  Part I: Sets and Relations (1 CFU):

  Preliminaries. Sets and operations between them. Venn diagrams, power set, Cartesian product, set partition. Set relationships. Reflexive, symmetrical, transitive relations. Equivalence relations.

  Case Study: Families of closed sets and the Union-Closed conjecture

  Part II: Graphs and Trees (2.5 CFU):

  Basic definitions. Complete graphs. Complement of a graph. Bipartite graphs. Graph representations. Isomorphisms. Eulerian graphs and Hamiltonian graphs. The problem of the traveling salesman and the weighted graphs. is. Coloring of graphs and chromatic number. f. Definition of Tree and characterization. Binary trees and their properties. d. Planar graphs, Euler formula and characterization of flatness.

  CASE STUDIES: The problem of Crossing Number. Examples of combinatorial problems on computationally complex graphs and their characterization as an optimal permutation search.

  Part III: Combinatorics and Discrete Probability (1 CFU):

  Permutations, combinations, arrangements (simple and with repetition). Discrete probability. Definition of probability. Uniform probability and relative properties. Conditional probability. Stochastic independence.

  Case Study: The Monty Hall Paradox

  Part IV: Fundamentals of Number Theory and Demonstration Methods (1.5 CFU):

  Natural numbers, relative integers, rational. Divisibility and Prime Numbers. Unique factorization theorem of integers. Theorem of the rest. Direct and indirect demonstrations. Examples of classical theorems and numerical algorithms. Numerical, summation and production sequences. Principle of mathematical induction and proof of fundamental properties. Modular arithmetic. Congruences.

  CASE STUDIES: The 3x + 1 problem and Goldbach's Conjecture.

Textbook Information

• ALGEBRA LINEARE E GEOMETRIA
  
  1. Appunti in rete alla pagina web https://andreascapellato.wordpress.com/didattica-2/
  2. S. Giuffrida, A. Ragusa, Corso di Algebra Lineare, Il Cigno Galileo Galilei Roma.
  3. G. Paxia, Lezioni di Geometria, Cooperativa Universitaria Libraria Catanese.
  4. S. Greco, B. Matarazzo, S. Milici, Matematica Generale, G. Giapichelli Editore, 2016.
• STRUTTURE DISCRETE
  

  No specific reference text. The teacher will provide students with the slides of the course and anything else necessary and sufficient to complete and deepen the topics discussed in class.

  All teaching material will be published on Studium.