MO412 / MC908 - Algoritmos em Grafos

Visão Geral

Este é um curso sobre Algoritmos em Grafos, com ênfase em Ciência de Redes. Abordaremos alguns algoritmos clássicos em grafos, intercalados com capítulos do livro de Barabási.

Teremos aulas presenciais regulares neste semestre. Em uma aula típica, o instrutor começará fazendo uma breve apresentação sobre o tema do dia, seguida de discussões e, geralmente, de uma revisão de exercícios relacionados ao tema, de diversas fontes. Os alunos são incentivados a compartilhar suas opiniões e impressões. Algumas aulas terão eventos especiais, como apresentações de alunos, aulas práticas, exames, etc.

Temos muito material para cobrir em um semestre. Sabemos que os alunos da Unicamp têm que lidar com uma carga horária pesada. Para poder cumprir seus compromissos, é essencial ter boa organização. Estimamos que os alunos terão que dedicar cerca de 12 horas semanais a este curso, incluindo tempo para leitura, frequência às aulas e realização de tarefas.

Atendimento

Favor marcar um horário por email.

Cronograma

Temos abaixo um calendário semestral, contendo os temas a abordar em cada aula, bem como o correspondente capítulo de livro ou outro recurso de apoio. Poderemos ter que mudar os tópicos das aulas ocasionalmente, devido a circunstâncias imprevistas, mas esperamos que o curso siga de perto este cronograma em grande medida.

Avaliação

A avaliação será baseada em uma série de tarefas, incluindo Exercícios, Contribuições para o Quiz Blog, um Quiz e um Projeto Final. Os Exercícios e as Contribuições para o Quiz Blog e o Quiz são individuais, mas o Projeto Final deverá ser realizado por grupos de 2 alunos, preferencialmente com formações diferentes. Caso o número de alunos da turma seja ímpar, permitiremos um grupo com 3 integrantes. No Projeto Final, cada grupo selecionará uma rede de interesse para mapear e analisar.

O Quiz será um exame com questões de múltipla escolha elaboradas por alunos de MO412, incluindo alunos deste semestre, algumas delas editadas pelo instrutor, coletadas em nosso Blog Oficial do Quiz. Em todas as semanas em que houver matéria nova (ver programação), os alunos têm que enviar questões de múltipla escolha sobre os temas da semana, geralmente às sextas-feiras. Alunos cujas questões forem aceitas para o Blog, com ou sem edição, ganharão pontos extras. Alunos que não enviarem uma questão serão penalizados.

Os Exercícios são problemas de lição de casa atribuídos pelo instrutor. Às vezes, serão exercícios de programação. Eles normalmente são atribuídos em uma quinta-feira após a aula e os alunos terão uma semana para entregar as respostas.

Para o Projeto Final, os grupos deverão apresentar seu trabalho em uma apresentação de 10 minutos, com no máximo 10 slides, descrevendo os dados, como foram coletados, características básicas da rede e insights obtidos com a análise. Haverá Apresentações Preliminares de Projetos no meio do semestre onde os grupos apresentarão sua rede, como irão coletá-la e questões relevantes sobre ela, em apresentações de 5 minutos, baseadas em no máximo 5 slides. Após a apresentação preliminar, até a apresentação final, cada grupo se reunirá semanalmente com o instrutor, por 15 minutos, para orientação na condução do projeto. Maiores orientações sobre os Exercícios e o Projeto Final serão dadas durante o curso.

Cada tipo de tarefa dará origem a uma nota numérica no intervalo de 0 a 10. As participações das notas de cada tipo de trabalho para a nota final são as seguintes:

Para a pós-graduação, as notas numéricas serão convertidas em letras de acordo com o seguinte esquema:

Penalidades por atraso

Para os Exercícios, haverá penalidades por atraso na entrega. Quem não entregar suas soluções no prazo incorrerá em multa de atraso de 20% da nota ao dia, calculada proporcionalmente, com granularidade de 1 minuto. Desta forma, se você está 1 dia atrasado, sua multa é de 20%; 2 dias de atraso, 40%; 1 hora de atraso, 0,833%; e assim por diante.

Fraude

Qualquer tentativa de fraude neste curso implicará nota final igual a zero para todos os envolvidos, com possíveis sanções adicionais se consideradas necessárias pela administração da Universidade.

Referências

Network Science. Albert-László Barabási. Cambridge University Press, 2016.

Introduction to Algorithms, 3rd Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. The MIT Press, 2009.

Algorithms, 4th Edition. Robert Sedgewick, Kevin Wayne. Addison-Wesley Professional, 2011.

Créditos

Network Icon from PNGFLY.