ECTS credits ECTS credits: 6
ECTS Hours Rules/Memories Hours of tutorials: 1 Expository Class: 30 Interactive Classroom: 20 Total: 51
Use languages Spanish, Galician
Type: Ordinary Degree Subject RD 1393/2007 - 822/2021
Departments: Mathematics
Areas: Algebra
Center Higher Technical Engineering School
Call: First Semester
Teaching: With teaching
Enrolment: Enrollable | 1st year (Yes)
Discrete mathematics helps to understand computation as topics such as logic, proofs, proofs by induction, set theory, algorithms, graph theory, counting techniques, etc., are studied.
The connection to artificial intelligence is that AI relies heavily on digital computation, and discrete mathematics can reveal how AI can infer certain behaviours. Also, discrete mathematics provides a way to encode and describe AI problems (machine learning, decision making, natural language processing, question answering, information retrieval).
With this subject, it is intended:
- to contribute to the education of future graduates in Artificial Intelligence, enabling robust and appropriate training in discrete mathematics skills.
- to promote the use of different representations (symbolic, graphical, matrix) and a variety of methods of reasoning (induction, recursion, deduction) as a means to promote the integration of concepts and procedures derived from the contents of the material.
- to know the basic concepts of set theory.
- to become familiar with the mathematics involved in algorithmic thinking (specification, verification and complexity).
- understand and be able to use Boolean algebras.
- to encourage attitudes of criticism when confronted with different types of solutions, search, effort and perseverance in the face of difficulties and communication using the appropriate terminology.
In the labs, we will be using SageMath, a free, open-source CAS, to begin programming different algorithms related to the matter.
TOPIC 1. Introduction to set theory.
Sets: elements and membership. Subsets: subsets of a set. Representation of sets: Venn diagrams. Operations with sets: properties. Cartesian product of sets. Maps between sets: composition. Types of maps: injective, surjective and bijective.
Teaching
Hours lecture / practices: 3 / 2
Independent / supervised learning activities
Hours of study / problem solving / computer practice / tutorial: 3 / 1 / 1 / 1 / 0,5
TOPIC 2. Mathematical reasoning and induction.
Demonstration strategies. Mathematical induction.
Teaching
Hours lecture / practices: 2 / 2
Independent / supervised learning activities
Hours of study / problem solving / computer practice / tutorial: 3 / 1 / 1 / 1 / 0,25
TOPIC 3. Algorithms and numbers
Algorithms: complexity. The Integers and division. Euclid's algorithm. Congruence. Representation of numbers. Arithmetic with big integers. Public key Cryptography.
Teaching
Hours lecture / practices: 7 / 6
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 5 / 2 / 2 / 0.5
TOPIC 4. Combinatorics.
Basic counting techniques. Addition and multiplication principles. The pigeonhole principle. Permutations and combinations. The binomial theorem. The inclusion-exclusion principle.
Teaching
Hours lecture / practices: 6 / 3
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2 / 2 / 0.5
TOPIC 5. Recursion
Recursive definitions. Recursive algorithms. Structural induction. Program verification. Advanced enumeration techniques: recurrence relations. Solving recurrence relations. Generating functions.
Teaching
Hours lecture / practices: 5 / 3
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2/ 2 / 0.5
TOPIC 6. Graphs
Types of graphs. Representation of graphs. Connectedness. Euler and Hamilton paths. Planar graphs. Graph colouring. Trees.
Teaching
Hours lecture / practices: 5 / 2
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 3 / 1 / 1 / 0.5
TOPIC 7. Boolean algebras
Boolean functions and switching functions. Disjunctive and conjunctive normal forms. Logic gates. Circuit minimisation.
Teaching
Hours lecture / practices: 2 / 2
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 3 / 1 / 1 / 0.25
BASIC:
Aguado, F., Gago, F. et al., Problemas resueltos de Combinatoria. Laboratorio con SageMath, Paraninfo, 2018.
Rosen, K. H., Matemática Discreta y sus Aplicaciones, McGraw-Hill (5ª ed.) 2004.
Vieites, A.M., Aguado, F. et al., Teoría de Grafos: Ejercicios resueltos y propuestos. Laboratorio con Sage, Paraninfo, 2014.
COMPLEMENTARY:
Bard, G. V., SageMath for Undergraduates. http://www.gregorybard.com/SAGE.html
García Merayo, F., Matemática discreta, Paraninfo, Thomson Learning, 2001.
García Merayo, F., Hernández, G., Nevot, A., Problemas resueltos de Matemática discreta, 2ª edición ampliada, Paraninfo, 2018.
Grimaldi, R. P., Matemáticas Discreta y Combinatoria, Addison-Wesley Iberoamericana, 1997.
Johnsonbaugh, R., Matemáticas Discretas, Pearson Prentice Hall (6ª ed.) 2005.
Lipschutz, S., Lipson, M., 2000 Solved Problems in Discrete Mathematics, Schaum, Mc-Graw-Hill, 1992.
http://doc.sagemath.org/
To contribute to achieving the basic, general, transversal and specific competencies included in the Report of the Degree in Artificial Intelligence of the University of A Coruña, the University of Santiago de Compostela and the University of Vigo and, in particular, the following (CG2, CG4, CB2, CB3, CB5, TR3, CE1 and CE3):
TRANSVERSAL
Within what is included in TR3:
Ability to create new models and solutions autonomously and creatively, adapting to new situations. Initiative and entrepreneurial spirit.
SPECIFIC
Within what is included in CE1 and CE3:
- Ability to use mathematical concepts and methods that may arise in the modelling, approach and resolution of artificial intelligence problems.
- Ability to solve artificial intelligence problems that require algorithms, from their design and implementation to their evaluation.
In addition to the above competencies, students should achieve the following skills:
- Cognitive (to know):
Acquisition of the basic concepts of the subject: algorithms, the integers, counting methods, theory of graphs and Boole algebras. Know applications of discrete mathematics to artificial intelligence.
- Procedures/instrumental (to know-how):
To manage modular arithmetic and apply it in different number representation systems, computation with big integers and public-key cryptography. To know how to apply the basic techniques to count in diverse problems. To learn some recursive algorithms and apply them in concrete situations. Apply graph theory in areas related to artificial intelligence. To manage the software Sage and apply the learning algorithms to solve the problems treated in the course.
- Attitudinal (to be):
Rigour and clarity, oral and written expression. Logical reasoning and identification of errors in procedures. Adaptability. Abstraction. Organization and planning skills. Criticism when confronted with several types of solutions. Analysis capacity in problem-solving.
We will devote the expository class time to presenting the essential elements that make up this subject. In the practical classes in small groups, we will carry out exercises and computer practices.
Also, we will hand out study topics and problems for the students to solve and submit/present the results in the tutorial classes in very small groups, where we will provide support.
There will be open two online courses: one in the Virtual Campus in which, in addition to having various support materials, we will keep a daily record of what is treated in each class session, along with the programming of activities, some of which will be carried out in groups, and another one at CoCalc that will serve as support and control for lab interactive classes.
There is a call with two opportunities.
The students’ grade, including repeaters, will be based on the evaluation of two tests (P1) and (P2).
Test (P1) will take place approximately halfway through the semester, and test (P2) on the day of the final exam listed in the School’s calendar.
The student who wishes may choose to retake test (P1) on the same day as test (P2), thereby canceling the grade from the first attempt.
The grade for the subject will be the arithmetic mean of the two grades, provided that the grade in both tests is equal to or greater than 3.
If in one of the tests the student obtains less than a 3, their final grade will never exceed 4.
In cases of fraudulent completion of exercises or exams, the provisions of the Regulations on the evaluation of academic performance of students and grade review will apply.
If the subject is not passed in the first opportunity, a final exam covering the entire content of the subject will be held in the second opportunity.
Regarding point 1 of the USC’s regulations on class attendance in official undergraduate and master's studies, it is indicated that class attendance will not be assessed.
The final theoretical-practical exam will be in-person and written.
If the tests cannot be carried out in person, they will be conducted online using the Moodle and MS Teams tools.
Class meeting:
30 hours of lectures (theory, exercises or problems)
20 hours of practical and laboratory sessions in small groups
3 hours of tutoring in very small groups
2 hours of partial tests
3 hours final written exam
2 hours final exam on the computer
Total (Face-to-face): 60 hours
Independent work:
45 hours of self-study related to classes (25 hours for theory, 10 hours for problems, 10 hours for computer practice)
30 hours to work on the proposed bulletins of problems
18 hours to program computer solutions to problems set
6 hours of evaluation activities on the virtual campus
Total (Non-attendance): 99 hours
Total workload: 159 hours
Regular attendance and participation in class and lab are expected. Moreover, each student should work out, by him/herself or with others, every single question left out in the lectures.
The student must understand the proofs of theory relating them to the techniques of resolution of practical problems (use of inference rules to prove theorems, application of the properties of Boolean algebras to minimisation of circuits, use of Euclid's algorithm, use of basic techniques to count and distribute objects, to program several recursive algorithms, application of graph theory to represent data or network design).
Efforts must be made to apply the reasoning of the theoretical proofs to the resolution of problems and implement these methods of solution in the established package of symbolic computation.
Students are advised to take advantage of the tutorials to delimit the work to be done in the assignments and in the practices, to work out the exams along with the classes and to exploit the possibilities of the online course (self-evaluation tools, commented online exams, frameworks of the several home assignments, past courses exams with solutions, etc.).
Xabier Garcia Martinez
Coordinador/a- Department
- Mathematics
- Area
- Algebra
- xabier.garcia [at] usc.es
- Category
- Professor: University Lecturer
| Tuesday | |||
|---|---|---|---|
| 10:00-11:00 | Grupo /CLE_01 | Galician | IA.11 |
| 12:00-14:00 | Grupo /CLIL_01 | Galician | IA.12 |
| Wednesday | |||
| 10:00-11:00 | Grupo /CLE_01 | Galician | IA.11 |
| 12:00-14:00 | Grupo /CLIL_02 | Galician | IA.13 |
| Friday | |||
| 10:00-11:00 | Grupo /CLE_01 | Galician | IA.11 |
| 12:00-14:00 | Grupo /CLIL_03 | Galician | IA.12 |
| 01.13.2026 09:15-14:00 | Grupo /CLE_01 | IA.01 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_01 | IA.01 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_02 | IA.01 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_03 | IA.01 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_01 | IA.02 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_02 | IA.02 |
| 01.13.2026 09:15-14:00 | Grupo /CLIL_03 | IA.02 |
| 01.13.2026 09:15-14:00 | Grupo /CLE_01 | IA.02 |
| 06.22.2026 09:30-14:00 | Grupo /CLE_01 | IA.01 |
| 06.22.2026 09:30-14:00 | Grupo /CLIL_01 | IA.01 |
| 06.22.2026 09:30-14:00 | Grupo /CLIL_02 | IA.01 |
| 06.22.2026 09:30-14:00 | Grupo /CLIL_03 | IA.01 |