Seminar in Discrete Mathematics
Code: 100098 ECTS Credits: 6| Degree | Type | Year |
|---|---|---|
| Mathematics | OB | 2 |
Contact
- Name:
- Francesc Bars Cortina
- Email:
- francesc.bars@uab.cat
Teachers
- Laura Brustenga Moncusi
- Guillem Quingles Daví
Teaching groups languages
You can view this information at the end of this document.
Prerequisites
BMath first year courses Linear Algebra-100088 and Fundamental Mathematics-100089.
Objectives and Contextualisation
Discrete Mathematics is a field of mathematics that studies finite mathematical objects or more general discrete mathematics objects. It covers topics such as combinatorics, graph theory, cryptography, error-correcting codes, combinatorial design theory, game theory, logic, optimization, or algorithm design and analysis that can be applied to solve problems in any of the above-mentioned branches. Most of discrete mathematics has evolved relatively recently, motivated by the challenges mainly in computer science and operations research. The chapters of this introductory course are quite independent from one another. A prior knowledge of linear algebra, modular arithmetic, basic combinatorics, and -fundamentally- mathematical language and reasoning should be adequate to understand the subject matter of each chapter.
The course begins with a review of linear algebra but with the notion of networks and finitely generated abelian groups and also a review of combinatorics observed in the 1st year, then generating functions and recurrent sequences will be discussed as a natural continuation of the combinatorics that has been done in the first year Foundations of Mathematics subject. In the problems of this topic, the ability to translate statement problems into mathematical language is continued to be put into practice.
Graphs are a basic tool for solving problems in very diverse areas, from the most abstract mathematics to operational research. In some cases, almost only the translation into the language of graphs is already clarifying and very effective. This topic will be the central topic of the entire course and to which we will dedicate the most time.
The third topic of the course, if time permits, will be combinatorial optimization or initial notions in cryptography.
Throughout the course, therefore, different examples of applications of mathematics will be presented, in which, with relatively simple tools and a lot of ingenuity, interesting and difficult problems are solved.
Competences
- Actively demonstrate high concern for quality when defending or presenting the conclusions of one's work.
- Apply critical spirit and thoroughness to validate or reject both one's own arguments and those of others.
- Effectively use bibliographies and electronic resources to obtain information.
- Students must be capable of applying their knowledge to their work or vocation in a professional way and they should have building arguments and problem resolution skills within their area of study.
- Students must be capable of communicating information, ideas, problems and solutions to both specialised and non-specialised audiences.
- Students must develop the necessary learning skills to undertake further training with a high degree of autonomy.
- Students must have and understand knowledge of an area of study built on the basis of general secondary education, and while it relies on some advanced textbooks it also includes some aspects coming from the forefront of its field of study.
- Use computer applications for statistical analysis, numeric and symbolic calculus, graphic display, optimisation or other purposes to experiment with Mathematics and solve problems.
- When faced with real situations of a medium level of complexity, request and analyse relevant data and information, propose and validate models using the adequate mathematical tools in order to draw final conclusions
Learning Outcomes
- Actively demonstrate high concern for quality when defending or presenting the conclusions of one's work.
- Apply critical spirit and thoroughness to validate or reject both one's own arguments and those of others.
- Consider and resolve linear programming problems.
- Consider ordering and enumeration problems and use efficient techniques to resolve them.
- Consider real problems as Mathematical Programming problems.
- Effectively use bibliographies and electronic resources to obtain information.
- Students must be capable of applying their knowledge to their work or vocation in a professional way and they should have building arguments and problem resolution skills within their area of study.
- Students must be capable of communicating information, ideas, problems and solutions to both specialised and non-specialised audiences.
- Students must develop the necessary learning skills to undertake further training with a high degree of autonomy.
- Students must have and understand knowledge of an area of study built on the basis of general secondary education, and while it relies on some advanced textbooks it also includes some aspects coming from the forefront of its field of study.
- Understand the language and most elementary applications of graph theory, as well as algorithms for problem-solving with graphs.
- Use computational techniques to solve optimisation problems.
Content
1. Lattices, combinatoris and generating functions.
-Definition of discrete set and lattice. Overview on classification of finitely generated abelian groups.
-Initial concepts on combinatorics.
- Generating function definition. Computation techniques. Solving combinatorial problems using generating functions.
- Recurrent sequences. First and second order linear recurrence relations.
- Solving recurrence relations with generating functions.
2. Graph Theory.
- Definition and examples of mathematical modeling using graph theory.
- Basic concepts. Some graph families.
- Graph representation, graph isomorphism.
- Paths and cycles.
- Trees.
3. Criptography. Combinatorial optimization.
- Coding theory, an introduction.
-Criptography, an introduction.
- Linear Programming. The simplex method.
Activities and Methodology
| Title | Hours | ECTS | Learning Outcomes |
|---|---|---|---|
| Type: Directed | |||
| Computer Lab | 8 | 0.32 | |
| Lectures | 28 | 1.12 | |
| Problem Set meetings | 16 | 0.64 | 7 |
| Type: Supervised | |||
| Meeting with instructor for feedback on the seminar project | 0 | 0 | 10, 9, 8 |
| Type: Autonomous | |||
| Group meetings for study/preparation for the Student-registered Seminar | 15 | 0.6 | 10, 9, 8 |
| Individual practice on computer solving of exercises | 8 | 0.32 | 7 |
| Self-study of lecture material | 26 | 1.04 | 10, 9, 7 |
| Working on problem sets | 36 | 1.44 | 7 |
Classroom activities will consist of:
- Lectures. The professor will lecture on the basic theory of the course.
- In turn, students will explain projects elaborated in groups of five about specialized aspects or applications, in the format of a short talk and a writting document:
- In a file will presented different projects. Each team will chose a subject and work on it autonomously.
- The result of their work will be handed in and a public recorderer talk of about 12 minutes and the writting document of the work did.
- Problems (seminars). In order to benefit from the class discussion, students should come to Problem-Set class meetings after having prepared the corresponding assignments.
- Computer Labs. Using the SageMath software. The first three sessions will match the three chapters of the course. The fourth session will include exercises on all the topics of the course and will be graded.
Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.
Assessment
Continous Assessment Activities
| Title | Weighting | Hours | ECTS | Learning Outcomes |
|---|---|---|---|---|
| Computer Lab test | 0.15 | 2 | 0.08 | 3, 4, 12 |
| Final exam | 0.45 | 4 | 0.16 | 11, 3, 4, 5 |
| Grading of the student-recordered seminar | 0.1 | 1 | 0.04 | 2, 1, 10, 9, 8, 7, 6 |
| Midterm exam | 0.3 | 2 | 0.08 | 11, 3, 4, 5, 7 |
| Retake exam | 0.75 | 4 | 0.16 | 11, 3, 4, 5 |
There are four graded tasks: a midterm exam, a computer lab test, a seminar project, and a final exam.
Course grade is calculated according to the following formula:
0.3 midterm exam score + 0.15 computer lab test score + 0.1 seminar project score+ 0.45 final exam score
Exam Retake Option: There is only one possible retake for the written exams (75%). To be eligible to retake the final exam you should have participated, at least, in three graded tasks.
Participating in less than three graded tasks and not taking the final exam will result in a "Non-assessable" course grade.
The course ``Seminari de Matemàtica Discreta" may only be avaluated by the previous description.
Bibliography
Recommended textbooks:
Aigner, M. "Discrete Mathematics", AMS 2007.
Basart, J.M. , Rifà, J, and Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
Basart, J.M. "Grafs: fonaments i algoritmes", Col. Manuals de la UAB, n. 13, 1998.
Comellas, F, Fàbrega,J., Sànchez, A, Serra, O. "Matemática discreta". Edicions UPC, 2001.
Gimbert, J. Moreno, R., Ribó, J.M., Valls, M. "Apropament a la teoria de grafs i als seus algoritmes". UdL, 1998.
Graham, R.L. , Knuth, D. E. , and Patashnik, O. "Concrete mathematics: a foundation for computer science". Addison-Wesley. 1990.
Grimaldi, Ralph P. "Discrete and combinatorial mathematics: an applied introduction". 5th ed. Pearson.Addison-Wesley. 2004.
Rosen, Kenneth H. "Discrete mathematics and its applications". 6th ed. McGraw-Hill. 2007.
Lawler, Eugene. Combinatorial Optimization: Networks and Matroids. Dover. ISBN 0-486-41453-1. (2001)
Suggested Readings on Graph Theory:
Wilson, R.J. , and Watkins, J. "Graphs: an introductory approach: a first course in discretemathematics". Wiley, cop. New York. 1990.
Suggested Readings on Linear Programming:
Alabert, A. , and Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
Basart, J.M. "Programació lineal". Col. Materials de la UAB, n. 58.. 1998.
Luenberger, D. , and Ye, Y. "Linear and Nonlinear Programming". 3rd ed. Springer. 2008.
Software
Python, SageMath, Magma
Groups and Languages
Please note that this information is provisional until 30 November 2025. You can check it through this link. To consult the language you will need to enter the CODE of the subject.
| Name | Group | Language | Semester | Turn |
|---|---|---|---|---|
| (PLAB) Practical laboratories | 1 | Catalan | first semester | morning-mixed |
| (PLAB) Practical laboratories | 2 | Catalan | first semester | morning-mixed |
| (PLAB) Practical laboratories | 3 | Catalan | first semester | morning-mixed |
| (SEM) Seminars | 1 | Catalan | first semester | morning-mixed |
| (SEM) Seminars | 2 | Catalan | first semester | morning-mixed |
| (TE) Theory | 1 | Catalan | first semester | morning-mixed |