Matemática Combinatória
Primeiro
Semestre de 2007
Prof. Fábio Protti
Onde me achar: sala E-2009 do DCC (ramal 9520)
Horário da disciplina: 3as e 5as, 13:00 - 15:00
Local das aulas: sala F2-006
PARTICIPE DA SELETIVA INTERNA DA
MARATONA DE PROGRAMAÇÃO!
A Maratona de Programação (http://maratona.ime.usp.br/) é uma competição que acontece anualmente, reunindo times de estudantes de cursos de computação de todo o Brasil.
Como muitos de vocês sabem, de uns anos para cá temos nos organizado na UFRJ de maneira a mandar times competitivos, e estamos, a cada ano, melhorando nosso desempenho e ganhando projeção nacional e internacional, bem como respeito para a nossa universidade. Nos últimos 4 anos, os times da UFRJ ganharam 1 medalha de bronze, 3 medalhas de prata e 1 medalha de ouro, além de terem sido classificados para a final mundial do evento por duas vezes (uma em Xangai, outra em Tóquio).
A partir do dia 18/07, quarta-feira, iniciaremos, então, a Seletiva Interna para escolher os times que irão representar a UFRJ na Maratona de Programação 2007.
É interessante ressaltar que para participar da Seletiva Interna não é necessário ter um time previamente formado, pois os times serão montados pela organização ao final da Primeira Fase, a qual é individual. Além disso, haverá treinamento para a Maratona, com aulas sobre os tópicos que aparecem com mais freqüência.
Neste ano de 2007, a Final Brasileira da Maratona será em Belo Horizonte, sendo organizada pela UFMG, enquanto as Finais Mundiais serão em Banff, no Canadá, sendo sediadas pela Universidade de Alberta.
Mais informações sobre a Maratona de Programação, a Seletiva Interna e o treinamento podem ser vistas no endereço http://www.dcc.ufrj.br/~maratona/.
Calendário de Provas
Prova 1: dia 26 de abril de 2007 -- PEGUE O GABARITO
Prova
2: dia 26 de
junho de 2007 -- PEGUE
O GABARITO
Segunda Chamada: dia 3 de julho de 2007
QUEM QUISER PEGAR PROVAS E LISTAS CORRIGIDAS,
ESTOU
À DISPOSIÇÃO -- ENVIE E-MAIL ANTES
Critério de Avaliação
Seja Trab a média entre Lista 1, Lista 2, Programa.
A nota final é a média das duas melhores notas entre Prova 1, Prova 2, Trab.
A Segunda Chamada é apenas para quem perdeu prova, sem exceções.
Lista 1 - entrega dia 22 de maio
Lista 2 - entrega dia 3 de julho (durante a Segunda Chamada)
Programa 1 - 10198 - Counting - entrega até 6 de julho (por e-mail)
Programa 2 - 10004 - Bicoloring - idem
Programa 3 - 639 - Don't Get Rooked - idem
BASTA ESCOLHER *UM* PROGRAMA. CADA PROGRAMA ADICIONAL *CERTO*
VALE UM BÔNUS DE *MEIO PONTO* ADICIONADA À MEDIA DE TRABALHOS.
ENVIE NO E-MAIL: ARQUIVO ANEXADO COM O CÓDIGO *FONTE*
E NOME COMPLETO DOS INTEGRANTES DA DUPLA.
Monitor
Carlos André
Horário de atendimento: 3as e 5as, 12:00-13:00, sala F2-006
Os
dias de atendimento serão nas duas semanas que antecedem as provas.
Tópicos do Curso
Contagem, Permutações e Combinações
Provas por Indução
Relações de Recorrência
Princípio da Inclusão e Exclusão
Teoria dos Grafos: Conceitos Básicos
Árvores
Circuitos
Grafos Planares
Problemas algorítmicos em grafos
Bibliografia básica
A.C.O.
Morgado, J.B.P. Carvalho, P.C.P. Carvalho e P. Fernandez.
Análise Combinatória e Probabilidade.
SBM, Rio de Janeiro, 1991.
A venda no Instituto de Matemática da UFRJ com a Professora Walcy ou diretamente no IMPA
C.L. Liu.
Introduction to Combinatorial Mathematics.
McGraw-Hill, 1968.
Disponível na biblioteca do Instituto de Matemática da UFRJ.
A.C. Bachx, L.M.B. Poppe e R.N.O. Tavares.
Prelúdio à Análise Combinatória.
Companhia Editora Nacional, 1975.
Edição esgotada. Introdutório às técnicas de contagem.
Judith L. Gersting.
Fundamentos matemáticos para a Ciência da Computação.
LTC, 2001.
Edward R. Scheinerman.
Matemática Discreta: Uma introdução.
Thomson, 2003.
Muito didático e bem abrangente.
Jayme Luiz Szwarcfiter.
Grafos e Algoritmos Computacionais.
Campus, Rio de Janeiro, 1984.
Edição esgotada. Mas pode ser encontrado na biblioteca do NCE.