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 will be taught in the classroom for a total of 48 hours.

Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.

The course, for a total of 6 CFU, is divided into 4 parts of equal sizes.

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: 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.

Part III: Combinatorics and Discrete Probability (1.5 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: Graphs and Trees (1.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.

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.