Combinatória e Grafos (2º período 2021-2022)

 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

01/03 - A Pauta foi actualizada com as classificações das Fichas Complementares e a Nota Final. Recorda-se que as Notas finais superiores a 17 valores estão dependentes de prova oral, sem a qual a nota é fixada em 17 valores.

01/03 - Está publicada junto das pautas uma tabela com os horários das provas orais. Como não consegui criar uma tabela que pudesse sr preenchida pelos próprios, agradeço que cada um me indique o horário pretendido e eu actualizarei permanentemente a tabela. Evidentemente, se puderem falar previamente uns com os outros, será muito mais fácil. O acesso à oral de algumas alunos e alunos só ficará definido com as classificações das Fichas Complementares que serão publicadas nas próximas horas; sugiro que essas alunas e alunos se preparem para essa eventualidade.

28/02 Foi publicada uma Pauta que já inclui as classificações dos TPC. Brevemente serão aí publicadas as classificações das Fichas Complementares e Notas finais.

26/02 - Orais: Embora a classificação dos trabalhos ainda não esteja concluída, existe um número elevado de alunos que irão (com certeza ou com elevada probabilidade) à oral. Tendo em conta as restrições de tempo essas provas serão curtas. Duas ou três delas podem ter lugar na quarta, 02/03, entre as 09:00 e as 11:30, devendo as restantes ter lugar na quinta, 03/03, a partir das 10:30 e na sexta, 04/03, a partir das 09:00. Vou tentar criar uma tabela que possa ser preenchida pelos próprios para organizar essas orais. Entretanto, apelo às alunas e alunos envolvidos para que procurem organizar-se nesse sentido. Muito obrigado.

24/02 - Dado o atraso na publicação dos resultados, e feito um balanço provisório, resolvi anunciar já que os TPC de todos os grupos terão uma classificação total entre 4 e 6 valores. A classificação definitiva dos TPC dos elementos de cada grupo será publicada em breve. Esta não inclui as Fichas Complementares, cuja classificação também será anunciada brevemente.

24/02 - A pauta já publicada inclui agora as classificações do Teste Final (cotação de 10 valores). Os resultados dos trabalhos de grupo serão publicados o mais brevemente possível.

22/02 - Horário de dúvidas: devido à realização de uma reunião à mesma hora, o horário de atendimento por Zoom marcado para amanhã, 23/02, fica adiado para quinta-feira, 24/02, à mesma hora.

22/02 - A Pauta dos Mini-Testes foi actualizada com os resultados do Mini-Teste de recuperação e com a classificação final dos quatro Mini-Testes. As classificações do Mini-Teste final bem como dos TPC e das Fichas complementares só poderão ser publicadas nos próximos dias.

21/02 - Esta ficha contém uma selecção de exercícios para revisão.

21/02 - Horários de atendimento:

23/02, 11:00, sala de dúvidas do DM

24/02, 17:00, https://videoconf-colibri.zoom.us/j/83944827116

24/02, 10:00, sala de dúvidas do DM

25/02, 16:00, https://videoconf-colibri.zoom.us/j/87223895513.

18/02 - Ao contrário do que tinha planeado, decidi que, devido a várias dificuldades de concretização, as reuniões com os grupos não serão obrigatórias. Desse modo, os trabalhos de casa serão avaliados, podendo depois da publicação dos resultados ser feitas reuniões se os grupos manifestarem esse desejo.

18/02 - Exame: As notas de avaliação contínua deverão ser conhecidas até dia 22/02. Chama-se a atenção para o facto de a inscrição para o exame de recurso, através da plataforma Fenix, ser obrigatória e ter que ser feita até às 15:00 de dia 14/02.

16/02 - Foram corrigidos alguns enganos na lista.

16/02 - Mini-Teste Recuperação: Nesta lista pode ser confirmado qual o moni-teste a recuperar.

16/02 - Aproveito para pedir aos grupos que entregaram trabalhos por mensagem que mos entreguem em papel.

16/02 - O horário de atendimento de amanhã passa a ser presencial. O horário por Zoom decorrerá entre as 17:00 e as 18:00.

15/02 - Entrega do TPC: A entrega do último TPC deve ser feita até sexta-feira, durante a realização dos testes.

11/02 - Horários de dúvidas: Na próxima semana, farei dois períodos de atendimento por Zoom:

terça-feira, 15/02, 14:00-15:30, https://videoconf-colibri.zoom.us/j/89414024221,

quinta-feira, 17/02, 14:00-15:30, https://videoconf-colibri.zoom.us/j/81209191568.

Serão marcados outros horários na semana seguinte, para as alunas e alunos que se inscrevam para o exame de segunda época. Publicarei, logo que possível, um ficheiro com problemas para revisão para apoiar a preparação para esse exame.

11/02 - Trabalhos de casa: agradeço que os trabalhos de casa entregues por mensagem me sejam também entregues em papel. Essa entrega pode ser feita em qualquer dia, quer deixando-os no meu gabinete, quer no cacifo do piso 3 do DM. Obrigado.

10/02 - COVID 19: Devido a um teste positivo, não poderei comparecer em quaisquer horários de atendimento presenciais até dia 17/02. Vou marcar horários remotos e as sessões Zoom serão anunciadas brevemente.

08/02 - O exercício 1.37 nas Notas sobre Funções Geradoras foi completado com uma sugestão.

08/02 - Escola de Inverno: Esqueci-me, na última aula de publicitar a Escola de Inverno do departamento. Podem encontrar aqui toda a informação.

08/02 - A entrega do TPC 3 pode ser feita até dia 10/02.

06/02 - As definições dos grupos para inscrição nos mini-testes de recuperação e final foram corrigidas. Agradeço os avisos sobre os erros e apelo a que façam a inscrição o mais cedo possível.

05/02 - A Pauta dos Mini-Testes foi actualizada.

04/02 - mini-teste de recuperação e final: As duas datas para a realização do mini-teste de recuperação e final são

terça-feira, 08/02, 14:30, sala P8

sexta-feira, 18/02, 10:00, sala PA2

Cada aluna ou aluno só pode comparecer a uma destas datas. Foram criados na plataforma Fenix dois agrupamentos, um para cada data, e cada aluna ou aluno deve, obrigatoriamente, inscrever-se no agrupamento da data em que pretende comparecer.

As classificações do quarto mini-teste serão publicadas até segunda-feira de manhã.

03/02 - Foram publicadas as Notas sobre Emparelhamentos em Grafos e sobre Funções Geradoras, e foi actualizada a Ficha Complementar sobre Partições. Os exercícios das Notas sobre Emparelhamentos (exceptuando o 7., que foi resolvido na aula) constituem o último trabalho de casa dos Grupos, que pode ser entregue até dia 15/02.

Os exercícios das Notas sobre Funções Geradoras constituem uma Ficha Complementar.

03/02 - Tal como na semana passada, horário de atendimento de hoje será entre as 15:00 e as 16:30.

03/02 - Última aula e Avaliação: na aula de amanhã não será dada matéria sujeita a avaliação obrigatória, sendo a aula dedicada a dois temas complementares ao programa. No final da aula falaremos sobre os pormenores finais da avaliação, pelo que apelo a todas as alunas e alunos para estarem presentes.

02/02 - Horário de dúvidas presencial: Na próxima sexta-feira terá lugar um horário de atendimento presencial (sala de dúvidas do DM), entre as 9:30 e as 11:00, durante o qual poderão ser consultados os mini-testes já corrigidos.

01/02 - A pauta com as notas dos mini-testes foi actualizada.

31/01 - Devido à realização das provas orais de Introdução à Teoria dos Números, não pude estar na sessão de dúvidas marcada. As minhas desculpas. Farei uma sessão, por Zoom e com o link https://videoconf-colibri.zoom.us/j/82404246807, hoje ás 18:00.

29/01 - Trabalho de grupo: o seguinte trabalho de grupo deve ser entregue até dia 08/02.

28/01 - A pauta com as notas dos mini-testes foi actualizada.

27/01 - Não consegui chegar a horas ao horário de dúvidas, apesar da mudança da hora. As minhas desculpas.

27/01 - O horário de dúvidas de hoje será entre as 15:00 e as 16:00. Amanhã haverá um horário de dúvidas suplementar, presencial, entre as 10:00 e as 11:00.

26/01 - Foi publicado mais um conjunto de Notas. Será publicado brevemente o Trabalho de casa para os grupos.

22/01 - Foi publicado mais um conjunto de Notas.

18/01 - Foi publicada a pauta com as notas do primeiro Mini-Teste.

16/01 - Foram publicadas as Notas sobre Permutações e Simetrias e sobre Grafos planares.

06/01 - Foi publicada uma Ficha Complementar sobre Partições. Esta Ficha será aumentada depois de uma aula (e uma outra Ficha Complementar) dedicadas a Funções Geradoras.

05/01 - Esta nota é uma introdução/resumo sobre permutações para preparação da próxima aula.

03/01 - Trabalho de grupo: o seguinte trabalho de grupo deve ser entregue até à aula de dia 18/01.

02/01 - Foi publicada uma Ficha Complementar sobre conjuntos finitos e infinitos. Esta Ficha poderá ser aumentada mais tarde.

01/01 - Os meus desejos de Feliz Ano Novo para todos.

27/12 - Foi publicado mais um conjunto de Notas sobre Teoria dos Grafos.

20/12 - Foi publicado mais um conjunto de Notas sobre Combinatória.

17/12 - Grupos de Trabalho: Esta é a lista dos grupos inscritos até agora. Os grupos de trabalho que não se inscreveram ainda no agrupamento no Fenix devem fazê-lo até à próxima terça-feira.

16/12 - Trabalho de casa: O primeiro trabalho de casa pode ser entregue até ter&ccdil;a-feira, 21/12. Cada grupo deve marcar um período (cerca de 20 a 30 minutos) num dos dias 20/12, entre as 09:30 e as 13:30, e 21/12, entre as 10:00 e as 13:00 ou entre as 14:00 e as 17:00, para entregar e discutir brevemente o trabalho feito. Essa entrega/discussão será feita na sala de dúvidas do Departamento de Matemática. Grupos que não tenham de todo possibilidade de o fazer devem agendar comigo a entrega de outra forma. Os grupos podem ainda entregar problemas que não conseguiram completar no prazo até 07/01. Em qualquer caso, os trabalhos de casa devem ser entregues em papel.

16/12 - Avaliação: A infomração sobre Avaliação foi actualizada.

12/12 - O primeiro mini-teste passou para a aula do dia 17/12.

As Notas Grafos I foram re-editadas e foram publicadas as notas Combinatória Enumerativa II. O horário de atendimento de amanhã tem que ser adiado para as 17:00 de quarta-feira, 15/12.

07/12 - O primeiro mini-teste realiza-se na aula de 14/12. Como primeiro trabalho de casa os grupos devem entregar, até à aula de 17/12, a sua resolução dos exercícios das primeiras Notas de Combinatória e de Teoria dos Grafos .

07/12 - O horário de dúvidas foi alterado, passando a ser totalmente remoto. Poderão ser combinados horários presenciais, nomeadamente para grupos de trabalho.

05/12 - Foi publicada uma versão desenvolvida das primeiras Notas sobre Combinatória, incluindo os resultados e exemplos dados na aula. A lista de exercícios foi aumentada e os grupos de trabalho são aconselhads a tentar resolvê-los. Esta ficha contém quatro perguntas de preparação para a próxima aula.

01/12 - Estas Notas são uma introdução à Teoria dos Grafos e serão o tema principal da aula de sexta-feira.

30/11 - Foi criado na plataforma Fenix o agrupamento Grupos de Trabalho. Os grupos devem inscrever-se neste agrupamento até dia 05/12.

29/11 - Chama-se a atenção para este Anúncio (não relacionado com Combinatória e Grafos).

25/11 - Esta Ficha é para preparar a primeira aula sobre Combinatória. Sugere-se que os grupos de trabalho discutam e tentem resolver alguns dos problemas apresentados.

24/11 - A primeira aula terá lugar no próximo dia 30/11. Será publicado brevemente um primeiro conjunto de Notas de apoio e problemas.



Programa

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. Problemas extremais da teoria de grafos. Funções geradoras.

Bibliografia

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.