Discrete Mathematics

Code:

M3011

Acronym:

M3011

Level:

300

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2020/2021 - 2S

Active?	Yes
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Biology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	0	Official Study Plan	3	-	6	56	162
L:CC	2	Plano de estudos a partir de 2014	2	-	6	56	162
			3
L:F	2	Official Study Plan	2	-	6	56	162
			3
L:G	0	study plan from 2017/18	2	-	6	56	162
			3
L:M	24	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

With this course, it is intended that students will know and understand some of the main results of Discrete Mathematics that, for its present relevance within Mathematics, and by its special applicability, inside and outside Mathematics, should be of general knowledge for mathematicians. In this course the students should also develop their ability to solve combinatorial problems and the ability do solve problemas looking for the more suitable structure.

Learning outcomes and competences

Upon completing this course, the student should know and be able to apply the concepts and results covered in the course. It is intended that this unit contribute to the furthering of skills in the field of discrete mathematics. In summary, it is intended that upon completion of this class the student can:

-Understand and apply fundamental combinatorial techniques as well as understand when these can or cannot be applied.
-Use appropriate techniques and problem solving skills on new problems.
-Recognize mathematical structures (e.g. algebraic ones) in combinatorial problems, can formulate them and solve them using the corresponding techniques.
-Be mathematically creative and inquisitive, being capable of formulating interesting new questions in combinatorics.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Basic notions from linear algebra, combinatorics and elementary group theory.

Program

DYNAMICAL SYSTEMS MODULE

1. SHIFT SPACES
- Full Shifts
- Shift Spaces
- Languages
- Higher Block Shifts and Higher Power Shifts
- Sliding Block Codes
- Convolutional Encoders

2. SHIFTS OF FINITE TYPE
- Finite Type Constraints
- Graphs and Their Shifts
- Graph Representations of Shifts of Finite Type
- State Splitting
- Data Storage and Shifts of Finite Type

3. ENTROPY
- Definition and Basic Properties
- Perron-Frobenius Theory
- Computing Entropy
- Irreducible Components
- Cyclic Structure

1. ENUMERATIVE COMBINATORICS
- The Knaster–Tarski fixed point theorem, Banach Theorem and Schroder–Bernstein Theorem
- Inclusion-exclusion principle and applications to number theory
- Integer partitions and generating functions
- The 12-fold way
- Euler's pentagonal Theorem

2. GROUPS AND PERMUTATIONS
- Permutation statistics
- Counting under a group action and Polya theory
- Walks in graphs

3. RECURRENCE RELATIONS AND GENERATING FUNCTIONS
- Finite differences and discrete analysis
- Recurrence relations: formalization and classification
- Generating functions and solutions of recurrence relations 

[Tentative, time allowing] 
4. ALGEBRAIC COMBINATORICS
- Random walks
- Radon transform on hypercubes
- The Sperner property

Mandatory literature

Douglas Lind; An introduction to symbolic dynamics and coding. ISBN: 0-521-55124-2
Ronald L. Graham; Concrete mathematics. ISBN: 0-201-55802-5
J. H. Van Lint; A course in combinatorics. ISBN: 0-521-42260-4

Complementary Bibliography

Bai-Lin Hao; Elementary symbolic dynamics and chaos in dissipative systems. ISBN: 9971-50-698-X
F., ed. lit. Blanchard; Topics in symbolic dynamics and applications. ISBN: 0-521-79660-1
Devaney Robert L.; A first course in chaotic dynamical systems. ISBN: 0-201-55406-2
Richard P. Stanley; Algebraic combinatorics. ISBN: 978-1-4614-6997-1
Richard P. Stanley; Enumerative combinatorics. ISBN: 0-534-06546-5
José Félix Costa; Matemática discreta. ISBN: 978-989-8481-69-6
Domingos Moreira Cardoso; Matemática discreta. ISBN: 978-972-592-237-8

Teaching methods and learning activities

Expositional classes with discussion of examples and resolution of exercises.

Software

Sagemath

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	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

No requisites.

Calculation formula of final grade

For the normal exam period (época normal) the exam will consist of two tests, each for 10 ponts out of 20. If the conditions allow it, one of the tests will be administered during the semester.

For the second exam period (época de recurso) the exam will consist of two parts, each corresponding to one of the tests from the normal exam period. Students can opt to taking just one of these parts or both.

Throughout the first part of the course (and corresponding assessment by the first test), the students may be given the oportunity to work on small, optional assignments to potentially suplement their grade on the first test of the normal exam period. This includes an assessment for a potential active participation on the class forum in Piazza, with good quality materials and helpful comments. The total amount of points which can be used to suplement this test cannot exceed 2 points.

Special assessment (TE, DA, ...)

Any type of special student evaluation may take one of the following forms: exclusively an oral examination; an oral examination plus a written examination, the student being required to pass both of them; only a written examination. The option for one of them is the sole responsibility of the professors in charge of the course unit.

Observations

Artigo 13º do Regulamento Geral para Avaliação dos Discentes de Primeiros Ciclos, de Ciclos de Estudos Integrados de Mestrado e de Segundos Ciclos da U.Porto, aprovado em 19 de Maio de 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "A fraude cometida na realização de uma prova, em qualquer das suas modalidades, implica a anulação da mesma e a comunicação ao órgão estatutariamente competente para eventual processo disciplinar."

Any student may be required to take an oral examination should there be any doubts concerning his/her performance on certain assessment pieces.

Course jury:

José Ferreira Alves
Samuel António Lopes