| 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 |
The teaching-learning assessment consists of three evaluation periods: two mini-tests and a final exam.
The grade in Teaching-Learning (EA) is given by the sum of the results obtained in the three evaluation periods.
The student must demonstrate, at the end of the semester, that they have acquired a minimum of competencies to be admitted to the exam. Students who do not obtain a minimum grade of 5.5 in Teaching-Learning will not be admitted. Attendance is also monitored to promote continuous study throughout the semester. A minimum attendance rate of 75% is required; otherwise, the student will not be admitted.
|
|
Language |
Portuguese. Tutorial support is available in English.
|