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.
Continuous evaluation will be followed, through directed academic activities, taking into account the work done, both individually and in groups, especially the one done with the computer. Students must demonstrate their knowledge of the subject; and a final exam.
Assessment of competencies:
In the group work the competences CB3, CE1 and CE3 will be evaluated.
In individual problem solving and computer practices the competences CG2, CB5 and TR3 will be evaluated.
In the questionnaires in class or in the virtual course the competences CG2, CB5, CE1, CE3 and TR3 will be evaluated.
In the final exam the competences CG2, CG4, CB2 and CB5 will be evaluated.
First opportunity (January / February)
Realizaranse dúas probas durante o cuadrimestre, ademais de diferentes entregas de exercicios. Tamén se terá en conta a participación nas clases. Os estudantes repetidores deberán realizar tódalas actividades convocadas a través do campus virtual.
• Final theoretical-practical exam: 35%
• Final exam of practices in the computer: 25%
• Continuous assessment: 40%. Two tests will be conducted during the semester, along with various exercise submissions. Class participation will also be considered.
Second chance (June / July)
The evaluation of the students will be based on a final exam with the following percentages:
• Final theoretical-practical exam: 35%
• Final exam of practices in the computer: 25%
• Continuous evaluation: 40%
Those who take one of the final exams or participate in at least 75% of the continuous assessment activities will be considered presented.
In the case of fraudulent behaviour in assignments, tests, or exams, the provisions of the "Regulations for the evaluation of the academic performance of students and grades review" will apply, in particular, those in Article 16:
Committing fraud in any assignment or test required in the evaluation of the subject will imply the qualification of fail in the corresponding call, regardless of the disciplinary process that may be followed against the offender.
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.).
Oscar Rivero Salgado
Coordinador/a- Department
- Mathematics
- Area
- Algebra
- oscar.rivero [at] usc.es
- Category
- Professor: LOU (Organic Law for Universities) PhD Assistant Professor
| 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.14.2025 09:00-14:00 | Grupo /CLE_01 | IA.01 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_02 | IA.01 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_03 | IA.01 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_01 | IA.01 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_01 | IA.11 |
| 01.14.2025 09:00-14:00 | Grupo /CLE_01 | IA.11 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_02 | IA.11 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_03 | IA.11 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_02 | IA.12 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_03 | IA.12 |
| 01.14.2025 09:00-14:00 | Grupo /CLE_01 | IA.12 |
| 01.14.2025 09:00-14:00 | Grupo /CLIL_01 | IA.12 |
| 06.25.2025 09:00-14:00 | Grupo /CLIL_03 | IA.11 |
| 06.25.2025 09:00-14:00 | Grupo /CLE_01 | IA.11 |
| 06.25.2025 09:00-14:00 | Grupo /CLIL_01 | IA.11 |
| 06.25.2025 09:00-14:00 | Grupo /CLIL_02 | IA.11 |