ECTS credits ECTS credits: 6
ECTS Hours Rules/Memories Student's work ECTS: 99 Hours of tutorials: 3 Expository Class: 24 Interactive Classroom: 24 Total: 150
Use languages Spanish, Galician, English
Type: Ordinary Degree Subject RD 1393/2007 - 822/2021
Center Higher Technical Engineering School
Call: First Semester
Teaching: Sin Docencia (En Extinción)
Enrolment: No Matriculable (Sólo Planes en Extinción)
Discrete mathematics is now a day a substantial part of the theoretical and practical knowledge of future computer engineers both abstract and instrumental. Abstract as it feeds on the roots of applied abstract algebra, and instrumental in the use of algorithmic and procedural aspects of that in relation to the real world: work planning, program design, use of counting techniques, control and detection of errors in the transmission of information, security of computer systems, software engineering, etc.
With this subject it is intended:
- to contribute to the education of the future graduates in engineering, enabling a robust and appropriate training in skills of discrete mathematics.
- 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 become familiar with the mathematics involved in algorithmic thinking (specification, verification and complexity).
- to encourage attitudes of criticism when confronted with different types of solutions, of search, of effort and perseverance in the face of difficulties and of communication using the appropriate terminology.
In the labs we will be using SageMath, a free open-source CAS to begin in the programming of different algorithms related to the matter.
1. Algorithms and numbers
Algorithms: complexity. The Integers and division. The Euclid's algorithm. Congruence. Representation of numbers. Arithmetic with big integers. Public key Cryptography.
Teaching
Hours exhibition / interactive / practices: 5 / 4 / 4
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 5 / 2 / 5 / 0.75
2. Basic counting techniques
Addition and multiplication principles. The pigeonhole principle. Permutations and combinations. The binomial theorem.
Teaching
Hours exhibition / interactive / practices: 5 / 3 / 4
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 3 / 4 / 0.5
3. Recursion
Recursive definitions. Recursive algorithms. Program verification. Enumeration techniques: recurrence relations. Solving recurrence relations. Generating functions. The inclusion-exclusion principle.
Teaching
Hours exhibition / interactive / practices: 5 / 2 / 2
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2 / 3 / 0.75
4. Graphs
Types of graphs. Representation of graphs. Connectedness. Euler and Hamilton paths. Dijkstra's shortest path algorithm. Planar graphs. Graph coloring. Trees. Spanning trees and shortest paths.
Teaching
Hours exhibition / interactive / practices: 5 / 2 / 2
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2 / 2 / 0.5
5. Boolean algebras
Boolean functions and switching functions. Disjunctive and conjunctive normal forms. Logic gates. Circuit minimization.
Teaching
Hours exhibition / interactive / practices: 3 / 1 / 1
Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 2 / 1 / 1 / 0.5
BÁSICA:
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.
COMPLEMENTARIA:
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. e 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. e Lipson, M., 2000 Solved Problems in Discrete Mathematics, Schaum, Mc-Graw-Hill, 1992.
http://doc.sagemath.org/
TRANSVERSAL/GENERIC
Within TR1, TR2 and TR3:
Problem solving capacity. Analysis and synthesis capacity. Organizing and planning capacity. Information managing capacity (collect and analyze the information). Problem solving. Decision making. Critical reasoning. Adaptability to new situations. Putting knowledge into practice. Ability to do independent and collaborative work. Creativity.
SPECIFIC
On top of its contribution to CG5, CG8, CG9 and CG10,
- Cognitive (to know):
Within RI6:
Acquisition of the basic concepts of the subject: algorithms, the integers, counting methods, theory of graphs and Boole algebras. To know applications of discrete mathematics to computation.
- Procedures/instrumental (to know how):
Within FB1 and FB3:
To manage modular Arithmetic and to apply it in different number representation systems, computation with big integers and in public key cryptography. To know how to apply the basic techniques to count in diverse problems. To know some recursive algorithms and to apply them in concrete situations. To apply the theory of graphs in areas relating to computation. To manage the software Sage and to apply the learned algorithms to solve the problems treated in the course.
- Attitudinal (to be):
Rigor 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.
The expository class time will be devoted to the presentation of the basic elements that make up this subject (FB3, CG8). The interactive classes, conducted in small groups, will be used to solve exercises (TR1, TR3, FB1, FB3, CG8, CG9, CG10) and to do computer work (TR1, TR3, FB1, FB3, CG5, CG8, CG9, RI6). Also study topics and problems will be handed out for the students to solve (TR1, TR2, TR3, CG8, CG9, CG10) and to submit/present the results in the tutorial classes in very small groups (TR2, CG9), where also support will be provided.
In any of the foreseen scenarios, we will open a course 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 (TR1, TR3, CG9), some of which will be carried out in groups (TR2), and another course at CoCalc that will serve as support and control for lab interactive classes.
Scenario 1: Adapted normality
Teaching will be essentially face-to-face, always in accordance with the formula defined by ETSE, and option will be given to follow the interactive lab classes online, through a combination of MS Teams and CoCalc. Tutorials and communication with students can be face-to-face or virtual. In the virtual case they can be asynchronous, through the virtual course forums or e-mail, or synchronous, through the MS Teams platform.
Scenario 2: distancing
According to the ETSE guidelines, expository teaching will be non-contact while the interactive classes will be face-to-face, giving the option to follow the interactive laboratory classes online, through a combination of MS Teams and CoCalc. The tutorials will be exclusively virtual and the communication with the students will realize through the forums of the virtual course, of the email or through the platform Microsoft Teams.
Scenario 3: Closure of facilities
Teaching will be completely virtual. There will be synchronous teaching through the Microsoft Teams platform, with CoCalc support for interactive lab classes, and asynchronous teaching with Moodle (using material that complements synchronous teaching) through the Virtual Campus. Communication with students will be through the virtual course forums, email or through the MS Teams platform.
There is a call with two opportunities.
A method of continuous evaluation will be followed, through directed academic activities, taking into account the work done, both individually (TR1, TR3, CG8, CG9, CG10) and in groups (TR2), and especially the one done with the computer (FB1 , FB3, RI6, CG5), in which students must demonstrate their knowledge of the subject; and a final exam (TR1, FB1, FB3, RI6, CG9).
In any of the foreseen scenarios, for the cases of fraudulent realization of exercises or proofs will be of application what is in the Rule of evaluation of the academic performance of the students and of review of qualifications.
The percentages assigned to each of the parties in each opportunity are as follows:
Scenario 1: Adapted normality
• Final theoretical-practical exam: 45%
• Final exam of practices in the computer: 25%
• Continuous assessment (virtual course, problems and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 30%
In order to pass the subject, it will be essential to carry out the practical works, take the exams and obtain a total of 5 points on average, with a minimum of 40% both in the final theoretical-practical exam and in the final exam of practices in the computer.
Second chance (July)
The evaluation of the students will be based on a final exam with the following percentages:
• Final theoretical-practical exam: 50%
• Final exam of practices in the computer: 30%
• Continuous evaluation: 20%
Those who take one of the final exams or take part in at least 75% of the activities of the continuous assessment will be considered presented.
Scenario 2: distancing
The same pattern will be followed as in scenario 1, but in the case that the final tests cannot be taken face-to-face, the percentages assigned will be as follows:
First chance (January / February)
• Final theoretical-practical exam virtual campus + MS Teams: 38%
• Final exam of computer practices in CoCalc + MS Teams: 22%
• Continuous assessment (virtual course, problems and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 40%
Second chance (July)
• Final theoretical-practical exam: 45%
• Final exam of practices in the computer: 25%
• Continuous evaluation: 30%
Those who take one of the final exams or take part in at least 75% of the activities of the continuous assessment will be considered presented.
Scenario 3: Closure of facilities
The same scheme of scenario 1 is maintained with telematic final tests via virtual course and CoCalc with MS Teams and both in the first opportunity (January / February) and in the second (July) the percentages will be as follows:
• Final theoretical-practical exam virtual campus + MS Teams: 38%
• Final exam of computer practices in CoCalc + MS Teams: 22%
• Continuous assessment (virtual course, problems and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 40%
Class meeting:
23 hours of theory classes
9 hours of problems in small groups (seminars)
15 hours work in small groups (laboratories)
2 hours tutoring in very small groups
3 hours final written exam
2 hours final exam computer
Independent work:
45 hours self-study related to classes (20 hours for theory, for problems 10, 15 computer practice)
25 hours to work on the proposed bulletins of problems
15 hours to program computer solutions to problems set
7 hours evaluation activities in the virtual campus
Total workload: 150 hours
Regular attendance and participation in class and lab is 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 proof theorems, application of the properties of Boolean algebras to minimization of circuits, use of Euclid 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 be able to apply the reasoning of the theoretical proofs to the resolution of problems and to implement these methods of resolution in the established packages of symbolic calculation.
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 on-line course (self-evaluation tools, commented on-line exams, frameworks of the several home assignments, past courses exams with solutions, etc.).
In accordance with the "Guidelines for the development of a safe face-to-face teaching, Course 2020-2021" of the University of Santiago de Compostela, the adaptations corresponding to the sections of teaching methodology and assessment system provided for scenarios 2 and 3 are included:
Contingency plan
Teaching methodology
Scenario 2: distancing
According to the ETSE guidelines, expository teaching will be non-contact while the interactive classes will be face-to-face, giving the option to follow the interactive laboratory classes online, through a combination of MS Teams and CoCalc. The tutorials will be exclusively virtual and the communication with the students will realize through the forums of the virtual course, of the email or through the platform Microsoft Teams.
Scenario 3: Closure of facilities
Teaching will be completely virtual. There will be synchronous teaching through the Microsoft Teams platform, with CoCalc support for interactive lab classes, and asynchronous teaching with Moodle (using material that complements synchronous teaching) through the Virtual Campus. Communication with students will be through the virtual course forums, email or through the Microsoft Teams platform.
Evaluation system
Scenario 2: distancing
The same pattern will be followed as in scenario 1, but in the case that the final tests cannot be taken face-to-face, the percentages assigned will be as follows:
First chance (January / February)
• Final theoretical-practical exam virtual campus + MS Teams: 38%
• Final exam of computer practices in CoCalc + MS Teams: 22%
• Continuous assessment (virtual course, problems and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 40%
Second chance (July)
• Final theoretical-practical exam: 45%
• Final exam of practices in the computer: 25%
• Continuous evaluation: 30%
Those who take one of the final exams or take part in at least 75% of the activities of the continuous assessment will be considered presented.
Scenario 3: Closure of facilities
The same scheme of scenario 1 is maintained with telematic final tests via virtual course and CoCalc with MS Teams and both in the first opportunity (January / February) and in the second (July) the percentages will be as follows:
• Final theoretical-practical exam virtual campus + MS Teams: 38%
• Final exam of computer practices in CoCalc + MS Teams: 22%
• Continuous assessment (virtual course, problems and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 40%
| 01.19.2023 09:15-14:00 | Grupo de examen | Classroom A3 |
| 06.21.2023 10:00-14:00 | Grupo de examen | Classroom A1 |