1747 Teoria dos Grafos e Análise de Algoritmos

Na primeira parte desta disciplina vamos estudar e aplicar técnicas de projeto e análise de algoritmos. Na segunda parte vamos estudar os conceitos, representações e problemas clássicos relacionados com grafos.

Veja o programa e o critério de avaliação da disciplina.

Os alunos desta disciplina devem inscrever-se no grupo uem-tgaa para receberem informações e discutirem o conteúdo da disciplina. Por favor, use o seu nome verdadeiro na lista para o professor poder identificá-lo.

Avisos

• 16/02 - Se você é aluno em regime de dependência, e existe conflito de horário entre as aulas desta disciplina e a aulas de alguma disciplina da sua série regular, por favor, procure o professor.

Material

O livro base para esta disciplina é Algoritmo: Teoria e Prática, 2ª edição.

Os materiais utilizados em sala de aula estão disponíveis para download logo abaixo. O estudo utilizando apenas este material não é suficiente para o acompanhamento da disciplina. Recomendamos a leitura das referências no final de cada apresentação e a resolução (por parte do aluno) de todos os exercícios listados no material.

• Capítulo 1: Introdução. Exercícios: 1.2-2, 1.2-3 e 1-1.
• Capítulo 2: Conceitos básicos. Exercícios: 2.1-1 a 2.1-4, 2.2-1 a 2.2-4, 2.3-1 a 2.3-7.
• Capítulo 3: Crescimento de funções. Exercícios: 3.1-1 a 3.1-4, 3-2 a 3-4.
• Material extra: Indução. Exercícios: veja o arquivo.
• Capítulo 4: Recorrências. Exercícios: 4.1-1 a 4.1-6, 4.2-1 a 4.2-5, 4.3-1 a 4.3-4, 4-1 e 4-4.
• Capítulo 6: Heapsort. Exercícios: 6.1-1 a 6.1-7, 6.2-1 a 6.2-6, 6.3-1 a 6.3-3, 6.4-1 a 6.4-3.
• Capítulo 7: Quicksort. Exercícios: 7.1-1 a 7.1-4, 7.2-1 a 7.2-3, 7.3-1 a 7.3-2.
• Capítulo 8: Ordenação em tempo linear. Exercícios: 8.1-1, 8.2-1, 8.2-4.
• Capítulo B.4: Grafos - Introdução.
• Capítulo 22: Algoritmos elementares de grafos. Exercícios 22.1-1 a 22.1-8, 22.2-1, 22.2-2, 22.2-3, 22.2-5, 22.2-6, 22.2-8, 22.3-1 a 22.3-3, 22.3-6 a 22.3-11, 22.4-1 a 22.4-5, 22.5-1 a 22.5-3, 22.5-5 a 22.5-7.
• Capítulo 23: Árvores espalhadas mínimas. Exercícios 23.1-1 a 23.1-4, 23.2-2 a 23.2-5.
• Capítulo 24: Caminhos mais curtos de única origem. Exercícios 24.1-1, 24.1-3, 24.1-4, 24.2-1 a 24.2-4, 24.3-1 a 24.3-4, 24.3-6, 24.3-7.
• Capítulo 25: Caminhos mais curtos de todos os pares. Exercícios 24.2-1, 25.2-3, 25.2-6.
• Implementação do algoritmo de Dijkstra em Python
• Implementação de lista de adjacências em Java
• Texto sobre o Problema do Carteiro Chinês e Problema do Caixeiro Viajante
• Apresentação do Problema do Caixeiro Viajante
• Apresentação do Problema do Carteiro Chinês

Trabalhos

• 3 - Implementação de heurísticas para o PCV: Data de entrega: 12/06.
• 2 - Simulado 1b: Data de entrega: 27/04.
• 1 - Simulado 1a: Data de entrega: 30/03.

Os trabalhos devem ser entregues de acordo com as seguintes normas:

• Papel A4 branco, com margens de 2cm.
• Usar frente e verso do papel.
• Escrever na primeira linha com caneta vermelha: nome do acadêmico, RA, código da disciplina e turma, número da atividade. Faça o download do modelo.
• Manuscrito.
• A troca de informações é permitida (e aconselhada), mas a cópia de solução / código não é permitida. Veja o regime disciplinar.
• As atividades fora das normas não serão aceitas.

Cronograma das Aulas