| Code |
14764
|
| Year |
1
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
TP(60H)
|
| Scientific area |
Mathematics
|
|
Entry requirements |
N.A.
|
|
Learning outcomes |
- Apprehend some concepts and fundamental results of the partially ordered sets, enumeration theory and graph theory
- Analyse and understand proofs;
- Communicate, written and orally, using mathematical language;
- To recognize some examples of the application of the contents presented in the context of the exact and social sciences.
|
|
Syllabus |
1- Partially ordered sets and lattices.
Hasse diagram, Tarski's fixed point, distributive lattice, Boolean algebra.
2- Fundamental principles.
Fundamental counting principle, pigeonhole and double counting. Permutations and combinations.
3- Subsets and binomial coefficients.
Properties of binomial coefficients, binomial theorem.
4- Generating functions and recurrence relations.
Generating functions, operations on generating functions, binomial theorem. Fibonacci numbers, linear and non-linear recurrences.
5- Partitions and permutations.
Partitions: Bell and Stirling numbers. Permutations: cycle decomposition and Stirling numbers.
6- The Principle of inclusion-exclusion.
Surjections and Stirling numbers, derangements.
7- Graph theory.
Graph isomorphism, incidence and adjacency matrices, paths and circuits, Eulerian graphs, Fleury algorithm, Hamiltonian graphs, graphs coloring, trees, minimal tree problem, shorter path problem, oriented graphs, maximum flow problem.
|
|
Main Bibliography |
1- Peter J. Cameron, Notes on Combinatorics, 2013.
2- Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms (2nd edition), Cambridge University Press, 1996.
3- Brian A. Davey, Hilary A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.
4- Norman Biggs, Discrete Mathematics (2nd edition), Oxford University Press, 2002.
5- Bela Bollobas, Modern Graph Theory, Springer-Verlag, 2002.
6- Domingos M. Cardoso, J. Szymanski, Mohammad Rostami, Matemática Discreta Combinatória, Teoria dos Grafos e Algoritmos, Escolar Editora, 2008
|
|
Teaching Methodologies and Assessment Criteria |
The assessment throughout the teaching-learning period will consist of the following items:
Two in-person assessments (F1, F2). Each assessment will be worth 8.0 points;
Completion and presentation of a paper (T) on a topic agreed upon with the teacher. The grade for this item will total 4 points.
The cumulative grade for the assessments (N1) is the sum of the two assessments and the paper. N1 = F1 + F2 + T
If N1 >= 9.5 the student will have to take an oral exam (PO).
The final grade for the teaching-learning period (N) will be the arithmetic mean of the cumulative grade of the assessments and the oral exam: N = (N1 + PO) / 2
The minimum for admission to the exam is 4 points.
In the written exam, all students with a grade of 9.5 or higher will be called for an oral exam graded out of 20. The final grade will be the arithmetic mean of the written exam and oral exam..
Students with special status have their own rules defined by the academic regulations.
|
|
Language |
Portuguese. Tutorial support is available in English.
|