Elementos de Matemática Finita (1º semestre 2019-2020)

 Licenciatura em Matemática Aplicada e Computação


Docente: Pedro Martins Rodrigues - pmartins@math.tecnico.ulisboa.pt



Informações        Avaliação       Programa          Bibliografia

Notas de apoio e Fichas de Problemas       Horário de dúvidas        Pautas  


Informações

11/02 - A Pauta publicada contém as Notas finais submetidas à Secretaria. Esta página não terá mais actualizações. Os meus desejos a todas as alunas e alunos de felicidades e excelente continuação de estudos.

07/02 - A Pauta foi actualizada com os resultados do segundo exame, bem como das orais realizadas hoje e da avaliação contínua. A revisão de provas terá lugar na segunda-feira, 10/02, às 10.00 horas, na sala de dúvidas do Departamento de Matemática. Pede-se antecipadamente às alunas e alunos cuja nota final esteja dependente da realização de prova oral para comparecerem ou, em caso de impossibilidade, comunicarem por mensagem.

03/02 - O exame de amanhã realiza-se às 15.00 horas, na sala P12.

01/02 - Por lapso, foi indicada a data de 02/02, domingo, para horário de dúvidas. A data correcta, já emendada, é 03/02.

17/01 - As provas orais deverão ter lugar, em princípio, nos dias 07/02 ou 10/02, em horário a combinar.

25/01 - Horário de dúvidas: os horários de dúvidas até ao exame terão lugar nos dias 30/01, 31/01 e 03/02, entre as 14.00 e as 15.30.

17/01 - A Pauta foi actualizada com o resultado da revisão de provas. O exame da segunda fase terá lugar no dia 04/02. A inscrição, através da plataforma Fénix, é obrigatória; o período de inscrição decorre das 09.00 horas do dia 20/01 até às 12.00 horas de dia 31/01.

16/01 - Resultados do Exame Os resultados do exame foram publicados. Fica disponível uma resolução do exame .

15/01 - Resultados do Exame e Revisão de provas Os resultados do exame serão publicados até amanhã. A revisão de provas fica marcada para dia 17/01, sexta-feira, às 15.00 horas, na sala de dúvidas do Departamento de Matemática. Pede-se antecipadamente às alunas e alunos cuja nota final esteja dependente da realização de prova oral para comparecerem ou, em caso de impossibilidade, comunicarem por mensagem.

03/01 - O Exame terá lugar no próximo dia 10/01, sexta-feira, às 08.00 horas, na sala PA1. Não é necessário fazer inscrição para o Exame.

31/12 - Os meus desejos para todos de um excelente 2020! Até breve.

31/12 - Horário de Dúvidas: Até ao exame de 10/01, o horário de dúvidas será o seguinte:

03/01 - 11.00-12.00,    07/01 - 10.00-11.30,    08/01 - 10.00-11.30,     09/01 - 14.00-15.30.

31/12 - Um dos MiniTestes 6 não está identificado. Agradeço à aluna ou aluno que verifique que a sua nota não está lançada que me avise.

31/12 - Foi publicado o ficheiro Notas XIII sobre Funções Geradoras (em actualização).

30/12- Um ficheiro de Notas Complementares sobre Funções Geradoras será publicado hoje ou amanhã.

30/12 - Foram publicadas na pauta dos Mini-Testes os resultados do último Mini-Teste, bem como a nota resultante dos seis Mini-Testes. Foi também publicada uma Pauta com a nota de Avaliação Contínua.

27/12 - Aactualização da página anunciada ficou adiada para segunda-feira. As minas desculpas.

23/12 - Está disponível o ficheiro Notas e Problemas XII.

21/12 - Esta página será actualizada com informações sobre avaliação contínua, problemas complementares e horário de dúvidas no próximo dia 27/12. Entretanto, os meus desejos de Boas Festas a todos.

18/12 - Foram publicados os resultados do quinto Mini-Teste.

11/12 - A aula de amanhã será dedicada, principalmente, a problemas sobre coloração de grafos e outros relacionados; os grupos deverão resolver, pelo menos, cinco dos seguintes problemas: XI.1 2., 3., 4., 6. e 8., XI.2 2., 3., 4. e 5. .

09/12 - Não poderei estar presente no horário de dúvidas marcado para hoje. Será marcado um horário de substituição brevemente.

05/12 - Está disponível uma primeira versão do ficheiro Notas e Problemas XI.

02/12 - Está disponível o ficheiro Notas e Problemas X.

28/11 - Foram publicados os resultados do quarto Mini-Teste.

27/11 - Trabalho de casa Cada grupo deve estudar e e entregar a resolução na aula de quinta-feira, 05/12, dos seguintes problemas.

20/11 - Está disponível o ficheiro Notas e Problemas IX.

14/11 - Foram publicados os resultados do terceiro Mini-Teste.

13/11 - Está disponível o ficheiro Notas e Problemas VIII.

06/11 - Está disponível o ficheiro Notas e Problemas VII.

04/11 - Trabalho de casa Cada grupo deve estudar e e entregar a resolução na aula de quinta-feira, 07/11, dos seguintes problemas: VI.1 8 e 13, VI.2 3,7 e 8.

30/10 - Foram publicados os resultados do segundo Mini-Teste.

24/10 - O ficheiro Notas e Problemas V foi actualizado. Está também disponível o ficheiro Notas e Problemas VI.

21/10 - Está disponível o ficheiro Notas e Problemas V e uma Ficha Complementar.

15/10 - Está disponível o ficheiro Notas e Problemas IV.

15/10 - Foram publicados os resultados do primeiro Mini-Teste.

12/10 - Trabalho de casa Cada grupo deve estudar e e entregar a resolução na aula de quinta-feira, 17/10, dos seguintes problemas.

10/10 - O horário de dúvidas da próxima segunda-feira, 14/10, terá lugar às 14.00 horas.

07/10 - Para a próxima aula de problemas os grupos devem preparar os exercícios III.1.(2 e 4), III.2 (1 b),1 d) 1 f), e 3), III.3 (1,2 e 3), III.4.3.

07/10 - Não poderei estar presente no horário de dúvidas de hoje às 13.30. Estarei na sala de dúvidas às 15.00. As minhas desculpas.

07/10 - O ficheiro Notas e Problemas II foi ligeiramente alterado no conjunto de exercícios II.4.

02/10 - Problemas a preparar para a aula de amanhã: II.2 (1 a 6); II.3 (2 a 4); II.4 (1 a 3 e 5).

02/10 - Está disponível o ficheiro Notas e Problemas III.

01/10 - Foram publicadas duas Fichas complementares sobre temas da Aritmética dos inteiros. Estes problemas podem ser estudados e resolvidos pelos grupos de trabalho e entregues como complemento de avaliação contínua.

27/09 - Trabalho de grupo - Cada grupo deve apresentar na aula de problemas de dia 3/10, a resolução dos seguintes exercícios: Notas I - I.5.8 e I.5.12; Notas II - II.2.1 (uma das alíneas) e II.3.2.

25/09 - Está disponível o ficheiro Notas e Problemas II.

24/09 - A próxima aula de problemas, 5ª feira 26/09, será dedicada principalmente aos problemas da secção I.5 das Notas e Problemas I (indução finita). Os grupos de trabalho devem preparar alguns dos problemas antes da aula.

24/09 - Foi publicado um anexo a Notas e Problemas I. Este anexo será eventualmente actualizado mais tarde.

20/09 - Foi feita uma alteração no horário de dúvidas.

13/09 - Está disponível o ficheiro Notas e Problemas I.

10/09 - O início das aulas, teóricas e práticas, tem lugar na terça-feira, 17/09. Durante os próximos dias serão publicados informações sobre o funcionamento das aulas e materiais de apoio.



Programa

O programa da disciplina Elementos de Matemática Finita consiste essencialmente numa introdução à Aritmética Modular, à Combinatória Enumerativa e à Teoria dos Grafos.

Na Aritmética Modular estuda-se a solubilidade e resolução prática de equações em inteiros, a menos de múltiplos de um inteiro fixo (o módulo), bem como as relações deste tema com a aritmética dos inteiros.
A Combinatória Enumerativa é a teoria que procura sistematizar os princípios e técnicas de contagem. Partindo de exemplos concretos elementares, procura-se chegar a resultados mais gerais sobre a combinatória de conjuntos finitos e suas aplicações.

Finalmente, a Teoria dos Grafos aborda as propriedades combinatórias de diagramas (finitos) constituídos por vértices e arestas.

O planeamento seguinte serve apenas de orientação geral.

I -

Noções gerais sobre Conjuntos e Funções. Relações de equivalência e de ordem.
Os números naturais e suas propriedades básicas.
Princípio da Boa Ordenação. Princípio de Indução Finita.
Recorrências.
Números Inteiros. Lema da divisão.
Representação em bases inteiras.
Máximo Divisor Comum e Algoritmo de Euclides.
Teorema Fundamental da Aritmética.

II -

Congruências e equações modulares.
A equação linear.
Teorema Chinês dos Restos.
Teoremas de Fermat e Euler.
Função de Euler. Funções Aritméticas.
Factorização, testes de primalidade e aplicações.
Equações modulares de grau superior.
Raízes Primitivas e critério de Euler.
Lema de Hensel.

III -

Conceitos básicos de contagem; princíos da dupla contagem e do pombal.
Números binomiais e multinomiais.
Contagem com e sem reposição, com e sem ordem.
Princípio de Inclusão-Exclusão. Função de Möbius.
Números de Stirling de 2ª espécie.
Permutações. Números de Stirling de 1ª espécie.
Contagem com simetria. Teorema de Cauchy-Frobenius-Burnside.

IV -

Definições e exemplos de grafos.
Caminhos e conectividade. Grafos Eulerianos e Hamiltonianos.
Matrizes de adjacência e de incidência de um grafo.
Árvores. Árvores geradoras e Algoritmo de Kruskal.
Grafos com pesos e árvores geradoras minimais.
Buscas em grafos e algoritmos.
Colorações de grafos, número de coloração e polinómio de coloração.
Grafos bipartidos. Emparelhamentos e o Teorema de Hall.
Grafos dirigidos.
Redes de comunicação e fluxos. O Teorema do fluxo máximo-corte mínimo.

 

Bibliografia

Ao longo do semestre, serão disponibilizadas nesta página fichas de apontamentos como material de apoio ao estudo. Estas fichas não substituem a consulta das referências bibliográficas indicadas.

Dos muitos livros disponíveis, o seguinte pode ser recomendado como o que mais facilmente pode ser usado como referência:


Serão utilizados e referidos outros livros; durante as aulas serão dadas, à medida que elas se revelem úteis, informações e explicações sobre alguns deles, que permitam aos interessados uma pesquisa mais variada sobre os temas do curso. A extensa lista seguinte é apenas informativa e não se pretende ou sugere uma consulta generalizada. 




Notas de apoio e Fichas de Problemas .

Notas e Problemas I - Conjuntos, Funções e Relações. Princípio de Indução Finita.        Sugestões e Esboços de solução de alguns problemas

Notas e Problemas II - Aritmética dos Inteiros

Ficha Complementar: Números Perfeitos        Ficha Complementar: O problema de Frobenius

Notas e problemas III - Aritmética Modular: Introdução; Equação Linear; Teorema Chinês dos Restos

Notas e problemas IV - Aritmética Modular: Potências; Teorema de Fermat-Euler.

Notas e problemas V - Aritmética Modular: Equações polinomiais; Raizes Primitivas.

Ficha Complementar: Equações polinomiais e o Lema de Hensel

Notas e Problemas VI: Combinatória Enumerativa: Introdução.

Notas e Problemas VII: O Princípio de Inclusão-Exclusão.

Notas e Problemas VIII: Permutações e Simetrias. Contagem com Simetria.

Notas e Problemas IX: Introdução à Teoria dos Grafos.

Notas e Problemas X: Árvores. Grafos planares.

Notas e Problemas XI: Colorações de Grafos.

Notas e Problemas XII: Emparelhamentos em Grafos.

Notas e Ficha Complementar XIII: Funções Geradoras.

Avaliação

A avaliação de conhecimentos nesta cadeira será por avaliação contínua nas aulas práticas, complementada com Exame Final.

O resultado da avaliação contínua (AC) consiste na soma das classificações de cinco mini-testes, com a cotação de 3 valores cada, com uma nota entre 0 e 5 valores que corresponde à avaliação global da participação na cadeira (participação na resolução de problemas nas aulas, trabalhos de casa, pequenos projectos).
As alunas e alunos devem organizar-se em
grupos de trabalho de 4 ou, no máximo, 5 elementos, para a realização de trabalhos de casa, projectos e preparação das aulas de problemas. Aconselha-se que estes grupos de trabalho coincidam com os formados para outras Unidades Curriculares, como Matemática Experimental e Elementos de Programação.

As duas datas de exame final (3 horas cada)são:  10
de Janeiro (08.00 horas)  e 4 de Fevereiro (15.00 horas); cada aluna/o pode realizar um ou os dois exames, prevalecendo a melhor classificação (E); cada exame tem a cotação de 20 valores.

A classificação final é dada pela fórmula max(E, 0.3xAC+0.7xE).

Às alunas e alunos com nota final superior a 17 valores será proposta a realização de uma prova oral que determinará uma nota final igual ou superior a 17 valores. Caso não se apresentem a essa prova oral, a nota final ficará fixada em 17 valores.


Horário de dúvidas

2ª feira - 13.30-15.00        3ª feira - 13.00-14.30


As sessões de atendimento para dúvidas têm lugar na sala reservada a esse fim no Pavilhão de Matemática; o docente permanece lá pelo menos durante os primeiros 45 minutos de cada período, podendo retirar-se ao fim desse tempo caso não haja alunos presentes. Caso isso aconteça, o docente pode ser contactado por telefone (extensão 1128)  no resto do período de atendimento, no seu gabinete.




Pautas

Pauta Mini-Testes

Av. Contínua, Exame e Nota Final