| 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 |
All classes will be both theoretical and practical.
The evaluation over the teaching-learning period will consist of the following items:
1- Two face-to-face frequencies. Each frequency is quoted to 8 points. They will be held on 17 April and 6 June.
2- Realization and presentation of an assignment previously accorded with the professor. This item sum up to 4 points.
The minimum grade for admission to the exam is 4 points.
Any fraud attempt will automatically exclude the student from the entire assessment process.
|
|
Language |
Portuguese. Tutorial support is available in English.
|