Matemática Discreta

Unidade Curricular / Curricular Unit
Matemática Discreta

Ciclo de Estudos / Study Cycle
1º Ciclo Engenharia Informática

Nome do Docente Responsável
Teresa Maria Catanho da Silva Almada

Nome do Docente Adicional
Objectivos de aprendizagem (conhecimentos, aptidões e competências a desenvolver pelos estudantes)
Fornecer elementos básicos de lógica com vista à eliminação de erros raciocínio. Familiarizar o aluno com a a linguagem da teoria intuitiva dos conjuntos. Identificar conjuntos finitos e conjuntos infinitos. Saber calcular o cardinal de alguns conjuntos finitos. Aplicação a problemas de contagem e combinatória. Dar formação que permita  operar com linguagens formais e identificar linguagens regulares. Adquirir competências que permitam utilizar  gramáticas formais e autómatos como mecanisnos geradores de  linguagens.

Learning outcomes of the curricular unit
To supply elementary concepts of logics aiming at the elimination of poor reasoning. To familiarize the student with intuitive set theory. To identify finite and infinite sets. To determine the cardinality of some finite sets. Applications to counting problems and combinatorics. To supply training that allows operating with formal languages and identifying regular languages. To acquire competences that allows using formal grammars and automata as language generator mechanisms.

Conteúdos programáticos
 Preliminares.
Elementos de Lógica Matemática.
Elementos da Teoria de conjuntos.
Generalidades. Operações com conjuntos. Conjunto potência. Generalidades sobre funções. Conjuntos finitos. Cardinal de um conjunto finito. Elementos de combinatória.
Relações Binárias.
Generalidade sobre relações binárias. Operações com relações binárias. Relações de Equivalência. Partição de um conjunto. Digrafos. Morfismos de digrafos.
Linguagens Formais
Generalidades. Operações com linguagens. Fecho e fecho positivo de uma linguagem. Linguagens regulares. Gramáticas Formais. Generalidades. Derivação. Linguagem gerada por uma gramática. Gramáticas regulares.
Autómatos Finitos
Generalidades. Autómato Determinístico e não determinístico. Linguagem          reconhecida por um autómato. Linguagem reconhecível. Lema de Pumping.

Syllabus
Preliminar
Elements of Mathematical Logic
Elements of Set Theory
Generalities. Operations with sets. Power set. Generalities about functions. Finite sets. Cardinal of a finite set. Elements of combinatorics.
Binary relations.
Generalities about binary relations. Operations with binary relations. Equivalence relations. Set partition. Digraphs. Morphisms of digraphs.
Formal languages.
Generalities. Operations with languages. Closure and positive closure of a language. Formal grammars. Generalities. Derivation. Language generated by a grammar. Regular grammars.
Finite Automata
Generalities. Deterministic and non deterministic automata. Language recognized by an  automata. Recognizable languages. Pumping Lemma.

Demonstração da coerência dos conteúdos programáticos com os objectivos da unidade curricular
É clara a coerência entre os conteúdos programáticos e os objectivos da unidade curricular. Os elementos de Lógica Matemática que são incluídos nos conteúdos programáticos visam não apenas eliminar alguns erros de raciocínio como também desenvolver o raciocínio lógico dedutivo. Para que o aluno se familiarize com a linguagem da teoria de conjuntos, o aluno precisa conhecer os conceitos básicos da teoria dos conjuntos. As relações binárias, de que as funções são um caso particular, integram a linguagem de conjuntos e permitem desenvolver técnicas essenciais para a construção de gramáticas ou de autómatos. A familiarização com linguagens formais e a aquisição de competências para gerar linguagens formais não podem ser adquiridas sem o estudo dos conceitos básicos das linguagens formais, gramática bem como do estudo dos automátos finitos. As relações binárias e as funções são ferramentas essencias para o estudo e construção de gramáticas bem como para o estudo de autómatos finitos.

Demonstration of the syllabus coherence with the Curricular Unit’s objectives
The coherence between syllabus and the unit´s objectives is clear. The elements of mathematical logics included in the syllabus aim at not only to erase poor reasoning skills but also to develop deductive logic reasoning. In order to be familiar with set  theory  language, the student needs to understand its basic concepts. Binary relations, maps being a particular example, are part of the set theory language and allow to develop techniques which are essential towards constructing grammars or automata. The familiarization with formal languages and the acquisition of formal language generating competences cannot be achieved without further study of the basic concepts of formal languages, grammars as well as the study of finite automata. Binary relations and maps are essential tools towards the study and construction of grammars and finite automata as well.

Metodologias de ensino (avaliação incluída)
Alguns tópicos surgem na sequência da análise de problemas cuja resolução torna natural os conceitos a estudar. A matéria é sempre ilustrada com exemplos e contra-exemplos. A exposição da matéria é feita apelando à particiação activa dos estudantes. Os estudantes são estimulados a construir exemplos e contra-exemplos para alguns dos conceitos apresentados.
A avaliação tem uma componente de avaliação contínua que inclui a participação nas aulas e a realização, durante o período lectivo, de quatro testes. Esta avaliação tem o peso de 40% relativamente à classificação final. Há uma prova escrita de 3h a  realizar após o término das aulas com o peso de 60%. Os alunos que obtenham uma classificação superior a 16 valores podem ser sujeitos a uma prova complementar. A não realização desta prova implica que a nota final é de 16 valores.

Planned learning outcomes, teaching methods and assessment methods and criteria
Some topics arise from analyzing problems, the solution of which shows naturally the concepts at stake. Subjects are always illustrated with examples and counter-examples. Exposition is done with constant appeal for the students active participation. Students are encouraged to build examples and counter-examples to illustrate the concepts involved.
Evaluation comprises a continuous component which includes active participation in classes and the performance of our tests weighting 40% of the final classification. A final written test takes place at the end of the semester weighting 60%. Students having more than 16 may have to perform and extra test, the non performance of which yield a final mark of 16.

Demonstração da coerência das metodologias de ensino com os objectivos de aprendizagem da unidade curricular
A eliminação de erros surge na sequência da análise de questões onde esses erros surgem. O uso construtivo do erro é muito eficaz na sua eliminação. A participação do estudante quer durante as aulas quer na construção de exemplos e contra-exemplos facilita a assimilação dos conceitos e a consolidação da matéria.
A realização de 4 mini-testes ao longo do período lectivo permite ao estudante detectar atempadamente as suas dificuldades e promove alguma regularidade no processo de estudo.

Demonstration of the teaching methodologies coherence with the curricular unit’s objectives
Elimination of mistakes takes place following the analysis of questions where those mistakes occurred. The constructive analysis of  errors is very effective towards its elimination.  The class participation of students building examples and counter-example enables the assimilation of concepts and the consolidation of the subjects.
The performance of 4 mini tests during semester allows the student to detect its flaws at an early stage and enables some regularity along the study process.

Bibliografia Principal / Main Bibliography
• Almada, T.; Matemática Discreta; Sebenta Universitária; Edições Universitárias; 2004.
• Howie, J.M.; Automata and Languages; Oxford Science Publications; 1991.
     McEliece, R.J.; Ash, R.B. and Ash, C.; Introduction to Discrete Mathematics;        McGraw- Hill; 1989.