Discrete Structures
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2021/2022 - 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
- Set theory: sets and subsets, set operations, Veen diagrams.
- Mathematical induction: mathematical induction, recursive definitions.
- Elementary topics in logic: propositional calculus, boolean algebra, 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.
- Relations: cartesian products and relations, properties, functions, computational representations of relations, partial orders, equivalence relations and partitions, modular arithmetic.
- 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
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.
John O.Donnell;
Discrete mathematics using a computer. ISBN: 1-84628-241-1
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.
Evaluation Type
Distributed evaluation without final exam
Assessment Components
designation |
Weight (%) |
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, TT - third test)
F = FT*(1/3) + ST*(1/3) + TT*(1/3)
FT,ST,TT >= 6 e F >= 9.5
Special assessment (TE, DA, ...)
final exam
Classification improvement
Final exam