Discrete mathematical structures F - N

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.

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,5 CFU):

Introduction to Propositional Logic and basic operators.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.

1. What is the maximum number of edges that a bipartite graph with a total of 10 vertices can have?
   
2. A connected planar graph with 6 vertices and 7 arcs, how many faces does it contain?
3. The following congruence is true or false: 115 ≡ 1 (mod 7)
4.  In an urn there are 5 white balls and 10 red balls. We take out two balls. What is the probability that there are only 3 white balls left in the urn?