Discrete Structures
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2019/2020 - 1S ![Requerida a integração com o Moodle Ícone do Moodle](/fcup/pt/imagens/MoodleIcon)
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
- Set theory: sets and subsets, set operations, Veen diagrams.
- Mathematical induction: mathematical induction, recursive definitions.
- Elementary topics in logic: propositional calculus, logic equivalence, inference rules, brief introduction to predicate calculus.
- Integer numbers: the division algorithm, prime numbers, the greatest comum divisor and Euclid’s algorithm, the fundamental theorem of arithmetic.
- Elementary topics in algebra: rings and modular arithmetic, boolean algebra.
- Relations: cartesian products and relations, properties, functions, computational representations of relations, partial orders, equivalence relations and partitions.
- Counting: sums and products, permutations and combinations, binomial coefficients.
- Graphs: definitons and examples, sub-graphs, complement and isomorphic graphs, degree of a vertex, planar graphs, Eulerian paths and Hamiltonian cicles in graphs.
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 (%) |
Participação presencial |
0,00 |
Teste |
100,00 |
Total: |
100,00 |
Amount of time allocated to each course unit
designation |
Time (hours) |
Estudo autónomo |
106,00 |
Frequência das aulas |
56,00 |
Total: |
162,00 |
Eligibility for exams
Students are required a minumum of 6 (out of 20) in each test. All the studens can take the resit exam.
Calculation formula of final grade
The final grade (FT - firts test, ST - second test)
F = FT*(0.5) + ST*(0.5)
FT,ST >= 6 e F >= 9.5