Discrete Structures
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2015/2016 - 1S 
Cycles of Study/Courses
Teaching language
Portuguese
Objectives
Study of the fundamental discrete structures that serve as a theoretical basis for the area of Computer Science/Informatics.
Learning outcomes and competences
After taking the course the students should be capable of:
- Work with mathematical notation and common concepts in discrete mathematics;
- Construct and understand mathematical proofs;
- Use mathematical concepts to formalise and solve problems in Computer Science/Informatics.
Working method
Presencial
Program
- Elementary topics in logic: propositional calculus, logic equivalence, inference rules, breve introduction to predicate calculus.
- Set theory: sets and subsets, set operations, Veen diagrams.
- Mathematical induction: mathematical induction, recursive definitions.
- Relations: cartesian products and relations, properties, functions, computational representations of relations, partial orders, equivalence relations and partitions.
- Graphs: definitons and examples, sub-graphs, complement and isomorphic graphs, degree of a vertex, planar graphs, Eulerian paths and Hamiltonian cicles in graphs.
- Elementary topics in algebra: rings and modular arithmetic, boolean algebra.
- Integer numbers: the division algorithm, prime numbers, the greatest comum divisor and Euclid’s algorithm, the fundamental theorem of arithmetic.
- Counting: sums and products, permutations and combinations, binomial coefficients.
Mandatory literature
Makinson David 1941-;
Sets, logic and maths for computing. ISBN: 978-1-84628-844-9
Grimaldi Ralph P.;
Discrete and combinatorial mathematics. ISBN: 978-0-201-54983-6 hbk
Kenneth H. Rosen; Discrete Mathematics and its Applications, McGraw-Hill, Inc.
Teaching methods and learning activities
Lectures: exposition of the elements in the syllabus as well as of examples and case studies.
Tutorial classes: resolution of exercises proposed each week.
keywords
Technological sciences
Evaluation Type
Distributed evaluation without final exam
Assessment Components
designation |
Weight (%) |
Exame |
50,00 |
Participação presencial |
0,00 |
Teste |
50,00 |
Total: |
100,00 |
Calculation formula of final grade
Mid semester test (50% of the final mark).
Final exam (50% of the final mark).
If MT is the mark obtained in the mid semester test and FE the mark
obtained in the final exam, then the final mark is given by:
F = MT*(0.5) + FE*(0.5)
MT,FE >= 6 and F >= 9.5
To get approval in the distributed evaluation, students must obtain a minimum of 6 points (in a total of 20) in each test and a minimum of 9.5 as final mark.
The students not obtaining approval, can take a resit exam. The resit exam will have two different components (clearly indicated) corresponding to the topics evaluated in the mid term test and the final exam, allowing for two different scenarios to determine the final mark:
- the students can answer the two components of the resit exam, in which case the final mark is determined exclusively by the mark obtained in the exam (this option is mandatory for students taking an improving exam, and for students that have not obtained a minimum of 3 points in the first test);
- the students can only answer the component of the test corresponding to the topics evaluated in the second test, in which case the final mark is determined using the formula indicated for the distributed evaluation.