Combinatória e Grafos (2º período 2024-2025)
Licenciatura em Matemática Aplicada e Computação
Docente: Pedro Martins Rodrigues - pedro.martins.rodrigues@tecnico.ulisboa.pt
Informações
Anúncios publicados no Fenix
Avaliação
Programa
Bibliografia
Notas
de apoio e Fichas de Problemas
Horário de dúvidas
Pautas
Informações
13/02 - Os meus desejos a todas e a todos de um excelente segundo semestre! E contem comigo no que puder ajudar.
13/02 - Com a realização da Revisão de Provas e das provas orais ficou completada a avaliação desta Unidade Curricular. As notas finais constantes da Pauta serão comunicadas à Secretaria de graduação. Esta página não terá portanto mais actualizações.
09/02 - Foram publicados os resultados do Exame. A Revisão de provas fica marcada para a próxima quarta-feira, 12/02, às 09:30.
05/02 - Exame: o exame realiza-se na próxima sexta-feira, 07/02, às 10:30, na sala P12. É necessária folha de Teste.
02/02 - Atenção: o horário de dúvidas foi alterado.
02/02 - Horário de dúvidas: terão lugar horários de atendimento para esclarecimento de dúvidas no próximo dia 06/02, entre as 10:00 e as 12:00 e entre as 15:30 e as 17:30.
28/01 - A Pauta Final foi actualizada após realização de provas orais.
28/01 - Exame de Recurso: O Exame de recurso realiza-se no próximo dia 07/02. Recorda-se que o exame tem a duração de duas horas e vale a totalidade da nota da disciplina. Se uma aluna ou aluno já tiver aprovação e realizar este exame, vale a melhor das duas classificações.
Estão abertas, a partir das 10:30 de hoje e até às 12:00 de dia 04/02, as inscrições para o exame, na plataforma Fenix. A inscrição é obrigatória.
27/01 - Revisão de prova: a data da revisão de prova teve que ser alterada e, por erro meu, essa informação não foi publicada, pelo que peço as minhas desculpas.
Devido à realização amanhã das provas orais, a REvisão de prova fica marcada para quarta-feira, dia 29/01, às 10:00. As alunas e alunos que não possam comparecer neste horário devem enviar-me uma mensagem, a fim de ser encontrada uma alternativa.
13/01 - Revisão de prova: devido a uma deslocação em trabalho, a revisão de provas dos MAPs fica marcada para dia 27/01, às 9:30, na sala de dúvidas do Departamento de Matemática.
10/01 - Ficam aqui disponíveis os resultados do Teste de recuperação . As duas primeiras colunas correspondem aos resultados parciais dos Testes passíveis de melhoria; a última coluna indica a melhoria obtida. A Pauta Final foi actualizada em função destes resultados. Recorda-se que as classificações finais superiores a 17 valores estão dependentes da realização de uma prova oral. Os alunos nessa situação receberão uma mensagem para combinar a marcação da prova oral.
10/01 - as pautas dos Trabalhos de Grupo e dos Testes foram actualizadas com as classificações, respectivamente, do último trabalho de grupo e do segundo MAP15. Foi também publicada uma Pauta Final provisória. Serão publicados logo que possível os resultados do Teste de recuperação. Podem ser consultados nesta tabela os resultados parciais obtidos nos testes; a negrito estão destacados os dois piores parciais, que poderão ser substituídos pelos resultados do Teste de recuperação.
06/01 - Teste de recuperação: devido a um erro na criação do agrupamento na plataforma Fenix, não é possível confirmar a inscrição para o Teste. Todas as alunas e alunos interessados podem considerar-se automaticamente inscritos. Agradeço, em alternativa, que quem não pretenda realizar esse Teste de recuperação me envie uma mensagem com essa indicação até amanhã.
Corrige-se e completa-se aqui a informação sobre o Teste: O Teste terá quatro perguntas, cada uma com uma ou duas alíneas, sobre os tópicos seguintes:
1- Problemas básicos de Enumeração e o Princípio de Inclusão-Exclusão;
2- Permutações e o Lema de Burnside;
3- Conceitos básicos sobre Grafos e Árvores;
4 -Colorações de grafos e outros problemas de Grafos.
Cada pergunta terá a cotação de 2 valores e cada teste entregue serão seleccionadas as duas melhores respostas que substituirão, em caso de melhoria, os piores resultados correspondentes a 2 ou 4 valores obtidos no MAP30, primeiro MAP15 e MAP45.
Pelo menos uma das perguntas respondidas deverá ser uma das assinaladas neste quadro .
02/01 - Teste de recuperação: Conforme foi anunciado, na aula de dia 08/01, a seguir ao MAP15, terá lugar um Teste de recuperação. Foi criado na plataforma Fenix um Grupo no qual as alunas e alunos que queiram realizar este teste se devem inscrever, até ao próximo dia 06/01.
O Teste terá três perguntas, cada uma com uma ou duas alíneas, sobre os tópicos seguintes:
1- Problemas básicos de Enumeração e o Princípio de Inclusão-Exclusão;
2- Permutações e o Lema de Burnside;
3- Árvores, Colorações de grafos e outros problemas de Grafos.
Cada pergunta terá a cotação de 2 valores; em cada teste entregue, serão seleccionadas as duas melhores respostas que substituirão, em caso de melhoria, os piores resultados correspondentes a 2 ou 4 valores obtidos no MAP30, primeiro MAP15 e MAP45.
30/12 - Os meus desejos de um muito Feliz Ano Novo!
30/12 - Na aula de dia 8/01, realizar-se-á, às 9.40, o segundo MAP15, que vai consistir numa pergunta sobre emparelhamentos em grafos. Uma vez que não houve aula de problemas sobre este tópico, fica disponível nesta página uma Ficha de problemas 7 de preparação. A pergunta do MAP será uma variante de uma das perguntas desta lista.
A seguir ao MAP15, as alunas e alunos poderão, se quiserem, realizar um Teste de recuperação. Esse teste terá a duração de 30 minutos, consistirá em duas ou três perguntas sobre qualquer parte da matéria e terá a cotação de 4 valores. A classificação obtida substituirá, em caso de melhoria, os piores resultados obtidos de igual cotação.
30/12 - A pauta dos trabalhos de grupo foi actualizada com os resultados do terceiro trabalho (cotação de 0,0 a 5,0). O quarto e último trabalho de grupo consiste em (pelo menos) um dos exercícios desta lista . Os grupos deverão comunicar entre si por forma a não repetirem perguntas. Cada grupo fará na última aula de problemas uma breve apresentação da solução do respectivo exercício.
24/12 - Foram publicados os resultados do segundo Trabalho de Grupo (cotação de 0,0 a 6,0), e do MAP45. Fica aqui disponível uma Resolução do Teste.
Serão publicadas brevemente informações sobre o último Trabalho de grupo e sobre o segundo MAP15 e Teste de recuperação.
Os meus desejos a todas e a todos de um Feliz Natal!
18/12 - MAP45 - O Teste terá lugar na sala P13. É necessário ter folha de prova (ou folhas brancas agrafadas).
17/12 - Foi publicada uma lista de problemas para as aulas de amanhã.
16/12 - foram publicados os resultados do primeiro MAP15.
16/12 - Devido a uma gralha, a alínea a) do problema 4 do Trabalho de Grupo é anulada.
12/12 - As resoluções deste trabalho de grupo devem ser entregues até à aula de problemas da próxima quarta-feira, 18/12.
11/12 - Foi publicada uma Pauta com os resultados do MAP30.
10/12 - Foi publicado um complemento da Ficha de preparação 5, para esclarecer o problema da decomposição cíclica de permutações.
09/12 - Foi publicada uma lista de problemas para as aulas de quarta-feira.
09/12 - Esclarecimento: a alínea c) do problema 3 do trabalho de grupo, bem como a pergunta a seguir às três alíneas, não serão consideradas para a avaliação do trabalho.
O primeiro trabalho de grupo foi avaliado com uma cotação de 0 a 5. Cada trabalho de grupo ou problema de aula terá uma cotação adequada à avaliação do mesmo, sendo a classificação final dos grupos de trabalho obtida por uma média ponderada dos diferentes trabalhos e de uma avaliação qualitativa do trabalho realizado nas aulas de problemas
09/12 - Foi publicada uma pauta com os primeiros resultados dos trabalhos de grupo. A pauta com os resultados do MAP30 será publicada brevemente.
06/12 - As resoluções deste trabalho de grupo devem ser entregues até à aula de problemas da próxima quarta-feira, 11/12.
02/12 - Foi publicada uma segunda Ficha de preparação e também uma lista de problemas para as aulas de amanhã.
29/11 - Aula suplementar: a aula suplementar combinada após comunicação com a delegada terá lugar no próximo dia 12/12, quinta-feira, às 16:10, na sala PA1.
29/11 - Trabalho de Grupo e Aulas de problemas: o próximo trabalho "de casa" para os grupos será publicado no início da próxima semana, para ser entregue até ao início da aula de dia 9/12. A partir da próxima quarta-feira, será pedido aos grupos a resolução na última parte da aula de um ou dois problemas, que podem ou não estar directamente relacionados com o tópico principal dessa aula.
29/11 - MAP 30: o primeiro teste tem a duração de 30 minutos e terá lugar às 9:10, na aula de segunda-feira, dia 2/12. Agradeço que não se atrasem eaguardem fora da sala.
29/11 - Foi publicada uma Ficha de preparação (sobre permutações) para a próxima aula.
26/11 - Horário de dúvidas: tendo em conta a realização do teste de Álgebra Linear, o horário de atendimento para esclarecimento de dúvidas marcado para hoje é cancelado e substituído por dois horários, dias 28/11 e 29/11, às 14:30.
25/11 - Foi publicada uma lista de problemas para as aulas da próxima quarta-feira.
22/11 - Foi publicada uma Ficha 3 que deve ser estudada como preparação para as próximas aulas.
21/11 - Esta é a lista de Grupos de trabalho de acordo com a informação que tenho. Alunas e alunos sem grupo de trabalho, e que ainda não tenham falado comigo sobre essa situação, devem fazê-lo o mais rapidamente possível, sob pena de isso poder influenciar negativamente a sua avaliação contínua.
18/11 - Horário de dúvidas: devido a uma consulta médica, o horário de dúvidas de amanhã, 19/11, terá lugar previsivelmente às 15:15.
18/11 - Foi publicada uma lista de problemas para as aulas da próxima quarta-feira.
15/11 - Trabalho de Grupo: Os grupos devem entregar, até à aula de problemas de 20/11, resoluções dos problemas 9, 10, 11, 12, 13 da lista Problemas 1, publicada no dia 12/11.
Foi publicada uma Ficha 2 que deve ser estudada como preparação para as próximas aulas.
13/11 - A Ficha de preparação foi actualizada para permitir a compreensão do enunciado dos últimos problemas da lista. Foram corrigidas as datas dos Mini-Testes.
12/11 - A Ficha de preparação foi actualizada. Foi publicada uma lista de problemas para a primeira semana: estas listas contêm problemas para resolver pelos grupos de trabalho nas aulas de problemas e durante a semana entre duas aulas de problemas e podem incluir referência a tópicos que ainda não foram abordados na aula teórico-prática. Em cada semana serão dadas indicações sobre problemas para serem entregues para avaliação.
11/11 - Já está disponível a primeira Ficha de preparação para a aula de dia 13/11.
10/11 - Os grupos de trabalho, mesmo que mantenham a constituição de Introdução à Teoria dos Números, devem enviar mensagem a confirmar essa constituição, com nomes e número de aluno, durante esta semana.
09/11 - Chama-se a atenção para o facto de os tópicos do programa não serem tratados nas aulas pela ordem em que são referidos na descrição abaixo.
09/11 - As aulas, quer as teórico-práticas, quer os turnos de problemas, têm início no próximo dia 13/11. Em cada semana será publicada uma Ficha de preparação que deve ser estudada antes das aulas, e uma lista de problemas. Além disso, fica desde já disponível ma versão de Notas de apoio. Estas Notas poderão ser actualizadas.
Dadas as características desta unidade curricular e o peso do trabalho de grupo na avaliação, é muito importante garantir, desde o início das aulas, o bom funcionamento dos grupos: os problemas sugeridos podem conter pormenores da matéria que não são contemplados nas aulas teórico-práticas; haverá, além de pequenas listas de problemas para "trabalho de casa", problemas para serem resolvidos e entregues pelos grupos nas aulas.
Exemplos e modelos básicos de enumeração. Princípios elementares de análise combinatória e aplicações. Enumeração de partições de conjuntos e de números. O princípio de inclusão-exclusão. Permutações. O teorema de Cauchy-Frobenius-Burnside e aplicações. Conceitos básicos sobre grafos. Conectividade e árvores. Grafos planares. Número de coloração e polinómio de coloração. Emparelhamentos em grafos. Problemas extremais da teoria de grafos. Funções geradoras.
Ao
longo do período, 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.
Durante as aulas serão
dadas, à medida que elas se revelem úteis, informações
e explicações sobre algumas referências bibliográficas, que permitam aos
interessados uma pesquisa mais variada sobre os temas do curso. A lista seguinte é apenas informativa e não se
pretende ou sugere uma consulta generalizada.
Cameron, P. J., Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
Graham, R., Knuth, D., Patashnik, O., Concrete Mathematics, Addison-Wesley, 1994.
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.
A avaliação de conhecimentos nesta cadeira será por avaliação contínua, constituída por dois mini-testes de 15 minutos (11/12 e 08/01, às 10:15) valendo 2 valores cada, um mini-teste de 30 minutos (02/12, às 09:10) valendo 4 valores, um teste de 45 minutos (18/12, às 18:00) valendo 6 valores e trabalhos de grupo que valem 6 valores no total.
No dia 07/02 realiza-se o exame de recurso.
As alunas e alunos devem organizar-se em grupos de trabalho de 4 elementos, para a realização de trabalhos de grupo, projectos e preparação das aulas de problemas. Sugere-se que se mantenham os grupos formados para Introdução à Teoria dos Números ou para outras Unidades Curriculares a decorrer em simultâneo. Agradeço que me comuniquem até ao fim da próxima semana a constituição dos grupos.
À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. Complemento da Ficha de preparação 5. Combinatória Enumerativa - I: Números binomiais e escolhas. Teoria dos Grafos - I: Introdução. Conectividade. Combinatória Enumerativa - II: Números multinomiais. Princípio do pombal. Distribuições. Teoria dos Grafos - II: Árvores Combinatória Enumerativa - III: Princípio de Inclusão-Exclusão Ficha Complementar: Finito e Infinito. Ficha Complementar: Partições de um número. Teoria dos Grafos - III: Grafos Planares. Combinatória Enumerativa - IV: Permutaccedil;ões e simetrias. Combinatória Enumerativa - V: Contagem com simetria. Teoria dos Grafos - IV: Coloração de Grafos.
Notas
de apoio, Fichas de preparação e de Problemas
Segunda-feira, 14:30-16:00, sala de dúvidas do DM.
Terça-feira, 14:30-16:00, sala de dúvidas do DM.