| Code |
16669
|
| Year |
1
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
TP(60H)
|
| Scientific area |
Mathematics
|
|
Entry requirements |
This curricular unit don´t have entry requirements. Mathematical maturity at the level of Calculus I is recommended, but not mandatory.
|
|
Mode of delivery |
Face-to-face.
|
|
Work placements |
Non applicable.
|
|
Learning outcomes |
This Curricular Unit aims to give an introduction to several themes of Discrete Mathematics: set theory, relations, equivalence relations, functions, order relations, Boole algebras, mathematical induction, counting principles and graph theory.
In the end of this Curricular Unit the student should be able to:
- discern the different types of proofs
- compute small theoretical proofs within the scope of the subjects covered in the discipline
- compute the partition induced by an equivalence relation and vice versa
- compute the transitive closure of a relation
- represent graphically order relations
- compute proofs using mathematical induction
- resolve counting problems
- manipulate binomial coefficients
- compute an Euler circuit using the Fleury algorithm
- compute a minimal generator tree using Kruskal's algorithm
- estimate the chromatic number of a graph
|
|
Syllabus |
1. Elementary Set Theory
1.1 Intuitive Set Theory
1.2 Universal Set and Empty Set
1.3 Equality of Sets and Power Set
1.4 Operations with Sets
2. Relations Defined on a Set
2.1 Cartesian Product of Sets
2.2 Operations with Relations
2.3 Partitions and Equivalence Relations
2.4 Closure of a Relation
2.5 Functions
2.6 Partial Order Relations, Lattices, and Boolean Algebras
3. Mathematical Induction
3.1 Principles of Mathematical Induction
3.2 Recursive Definitions and Structured Induction
4. Combinatorics
4.1 Elementary Counting Principles
4.2 Arrangements, circular permutations, and combinations
4.3 Pigeonhole Principle
4.4 Multinomial Theorem and Inclusion-Exclusion Principle
5. Introduction to Graph Theory
5.1 Definitions
5.2 Incidence matrix and adjacency matrix
5.3 Eulerian and Hamiltonian graphs
5.4 Trees
5.5 Some applications
5.6 Graph colourings. Chromatic number
|
|
Main Bibliography |
- Discrete Mathematics and Its Applications 7th edition. Rosen, Kenneth.
- Apontamentos de Matemática Discreta. Cruz, Henrique & Rosa, Silvério.
- Notes on Combinatorics. Cameroon, Peter.
- Ten Chapters of the Algebraical Art. Cameron, Peter.
|
|
Teaching Methodologies and Assessment Criteria |
Teaching/Learning Assessment
- M1 - Mini-test 1: 20% (4 points) to be held on March 25th.
- M2 - Mini-test 2: 20% (4 points) to be held on May 6th.
- F - Final exam: 60% (12 points) to be held on June 3rd.
The final grade for the course unit is determined by the sum of the grades obtained in the defined assessment components. The student obtains approval in the course unit, being exempt from the exam, if they obtain a grade equal to or higher than 9.5.
Assessment by Exam
- Exam: 100%.
Admission requirements for attendance and exam:
- Minimum of 75% attendance in classes during the teaching-learning period;
- Minimum grade of 6 in the sum of the grades obtained in the defined assessment components.
Failure to meet any of the requirements implies failure in the course unit and renders the student ineligible for the exam.
Student workers (nominated by Academic Services) and final-year students are excluded from the need for these criteria.
|
|
Language |
Portuguese. Tutorial support is available in English.
|