Go to:
Logótipo
Esta página em português Ajuda Autenticar-se
FCUP
You are in:: Start > M3011

Discrete Mathematics

Code: M3011     Acronym: M3011     Level: 300

Keywords
Classification Keyword
OFICIAL Mathematics

Instance: 2019/2020 - 2S Ícone do Moodle

Active? Yes
Responsible unit: Department of Mathematics
Course/CS Responsible: First Degree in Mathematics

Cycles of Study/Courses

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

Teaching Staff - Responsibilities

Teacher Responsibility
Jorge Manuel Martins da Rocha
Pedro Ventura Alves da Silva

Teaching - Hours

Theoretical and practical : 4,00
Type Teacher Classes Hour
Theoretical and practical Totals 1 4,00
Pedro Ventura Alves da Silva 2,00
Jorge Manuel Martins da Rocha 2,00

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

Program

Module AUTOMATA:

  1. WORDS AND LANGUAGES: words, free monoids, languages.

  2. RATIONAL AND RECOGNIZABLE LANGUAGES: rational expressions, finite automata, alternative versions, transition monoid, recognizability by a finite monoid.

  3. CLOSURE OPERATORS: closure properties of recognizable languages, Kleene's Theorem.

  4. DECIDIBILITY: minimal automaton of a rational language, syntactic monoid, decidable properties, pumping lemma.

  5. CLASSIFICATION: some instances of Eilenberg’s correspondence.
  6. GENERALIZATIONS: infinite automata, pushdown automata, Turing machines.

Module DISCRETE DYNAMICS:
  1. Sharkovsky's Theorem 

  2. Dynamics of the shift mapping

  3. Dynamics of the quadratic family

  4. Sperner's Lemma and Brower's Fixed Point Thorem



Mandatory literature

Burns Keith and Hasselblatt Boris; The Sharkovsky Theorem: A Natural Direct Proof, The American Mathematical Monthly, Vol. 118, No. 3, pp. 229-244, 2011
Devaney Robert L.; A first course in chaotic dynamical systems. ISBN: 0-201-55406-2
Howie John M.; Automata and languages. ISBN: 0-19-853424-8
Sakarovitch Jacques; Elements of automata theory. ISBN: 978-0-521-84425-3
Shashkin Yu. A.; Fixed points. ISBN: 0-8218-9000-X

Teaching methods and learning activities

Expositional classes with discussion of examples and resolution of exercises.

Evaluation Type

Distributed evaluation with 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 52,00
Total: 158,00

Eligibility for exams

No requisites.

Calculation formula of final grade



  • Evaluation in the first season is performed through two mandatory tests, T1 and T2, one for each module, each one worth 10 points with a duration of 2 hours. The first test is done during the semester and the second during the first season of exams.




  • The final mark will be the sum of the marks obtained in each test. Approval requires a sum not inferior to 9,5 points. Those obtaining a grade higher than 18 in the exam or in the full collection of tests must do an extra short written exam to confirm their mark.




  • The second season exam consists of two independent tests, one for each module, each one worth 10 points with a duration of 2 hours. In any situation (seeking approval or improving their grade), in the second season the student may choose to do both parts or just one of them, R1 and R2, R1 or R2. They must transmit that intention to the professors before doing the exam. The final grade, CF, is the sum of the maximum grades obtained in each part of the evaluation: CF=max{T1, R1}+max{T2,R2}. Approval requires a sum not inferior to 9,5 points. Those obtaining a grade higher than 18 in the exam or in the full collection of tests must do an extra short written exam to confirm their mark.




  • All other evaluation situations unforeseen in the previous points, in particular improving grades from previous seasons and substitution exams previewed in the regulations, will be performed through a unique exam, not exceeding 3 hours of duration, which may be  preceded by a simple oral exam to verify if the student is minimally prepared to realize the exam.



Special assessment (TE, DA, ...)

Special exams will consist of a written test, which might be preceded by an eliminatory oral test to assess whether the student satisfies minimum requirements to tentatively pass the written test.

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.

Jury:

Jorge Manuel Martins da Rocha
Pedro Ventura Alves da Silva
Recommend this page Top
Copyright 1996-2019 © Faculdade de Ciências da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2019-09-19 at 16:32:29