MC358: Mathematical Foundations of Computer Science

Since 2016.

Prerequisite:  None.

Description:

Basic concepts on discrete mathematics and logic for computing. Proof techniques, mathematical induction. Relations and graph theory concepts. Modeling problems using graphs.

Programme:

1. Sets

2. Mathematical speech: mathematical reading and writing

3. Elements of logic:

        - proposition, logical connectives and quantifiers.

4. Proof strategy

5. Mathematical induction

6. Relations

        - restriction, composition and inverse

        - order relation and extreme elements

        - relations and equivalence classes

7. Functions

- injective, surjetcive an bijective functions

- inverse functions

- sequences

- floor and ceil functions

8. Summation and productory   

- index manipulation and order change

- upper and lower bounding summations

9. Recurrences

- simple additive and multiplicative recurrences

- linear recurrences and characteristic polynomial

- upper and lower bounding recurrences

10. Counting
- basic principles of counting (additive and multiplicative)

- permutations, arrangements and combinations

- binomial identities

Recommended Literature:

I.        A. Gomide e J. Stolfi, Elementos de Matemática Discreta para a Computação http://www.ic.unicamp.br/~anamaria/

II.        D. J. Velleman, How to prove it - A structured approach (2nd edition), Cambridge (2006)

III.        K. H. Rosen, Discrete Mathematics and its applications (7th edition), McGraw-Hill (2011)

IV.        J. L. Gersting, Fundamentos Matemáticos para a Ciência da Computação (5th edition in portuguese), LTC Editora (2004)

V.        M. Ben-Ari, Mathematical Logic for Computer Science (3rd edition), Springer (2012)