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.
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.
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.
Niven, I., Zuckerman, H.S., Montgomery, H.L., An Introduction to the Theory of Numbers, John Wiley & Sons, Inc., 1991.
Hardy, G.H., Wright, E.M., (Heath-Brown, D.R., Silverman, J.H., rev.), An Introduction to the Theory of Numbers, (6th ed.) Oxford University Press, 2008.
Silverman, J.H., A Friendly Introduction to Number Theory, Pearson International Edition, 2005.
Bressoud, D., Wagon, S., A Course in Computational Number Theory, Key College Publishing, 2000.
Cameron, P. J., Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
Graham, R., Knuth, D., Patashnik, O., Concrete Mathematics, Addison-Wesley, 1994.
Lovasz, L., Vesztergombi, K. L., Pelikan, J., Discrete Mathematics: Elementary and Beyond, Undergraduate Texts in Mathematics, Springer-Verlag, 2003.
Martin, George E., Counting: The Art of Enumerative Combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, 2001.
Harris, J.M., Hirst, J.L., Mossinghoff, M.J., Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag, 2008.
Andreescu, T., Feng, Z., A Path to combinatorics for Undergraduates, Birkhauser, 2004.
Bóna, M., A Walk Through Combinatorics (An Introduction to Enumeration and Graph Theory), World Scientific, 2006.
Bollobas, B., Modern Graph Theory, Springer-Verlag, 2002.
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.
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.