MC448 - Análise de Algoritmos I

Conteúdo desta página

Avaliação Didática

Veja o resultado da avaliação didática realizada no dia 01/07/2004.

Docente

Zanoni Dias
Sala: 23 (IC-1)
Email: zanoni@ic.unicamp.br

Dias, Horários e Local das Aulas

As aulas serão às terças e quintas das 10h00 às 12h00 no PB02.

Dias, Horários e Local de Atendimento

Os atendimentos serão marcados pelo docente e anunciados em classe.
Atendimento para o exame (sala 23 - IC):
- Terça-feira (06/07/2004) - 18:00h às 19:00h
- Quinta-feira (08/06/2004) - 17:30h às 18:30h

Programa

Introdução à Análise de Algoritmos
Indução Matemática
Complexidade de Algoritmos.
Relações de Recorrência
Construção de Algortimos por Indução
Algoritmos de Ordenação
Limite Inferior para Ordenação
Estatísticas de Ordem
Estruturas de Dados para Conjuntos Disjuntos.
Programação Dinâmica
Análise Amortizada
Algoritmos em Grafos

Referências Bibliográficas


[1]		[Livro-texto] Introduction to Algorithms: A Creative Approach U. Manber Addison-Wesley, 1989.
[2]		[Livro-texto] Algoritmos - Teoria e Prática T. Cormen, C. Leiserson, R. Rivest, C. Stein Editora Campus, 2002. Errata
[3]		Introduction to Algorithms T. Cormen, C. Leiserson, R. Rivest, C. Stein McGraw-Hill, 2001. Errata
[4]		Introduction to Algorithms T. Cormen, C. Leiserson, R. Rivest McGraw-Hill, 1990.

Obs: As referências [2], [3] e [4] são equivalentes:

A referência [4] é a primeira edição do livro.
A segunda edição possui versões em inglês [3] e português [2].
Verifique a equivalência de capítulos entre as edições.

Outras referências recomendadas:


[5]		Algorithmics: theory and practice G. Brassard e P. Bratley Prentice-Hall, 1995.
[6]		Projeto de Algoritmos - 2a edição N. Ziviani Thomson, 2004.
[7]		The Design and Analysis of Computer Algorithms A. Aho, J. Hopcroft, J. Ullman Addison-Wesley, 1974.
[8]		The Art of Computer Programming D. E. Knuth Addison-Wesley, 1974.
[9]		Grafos e Algoritmos Computacionais J. L. Szwarcfiter Addison-Wesley, 1974.

Listas de Exercícios

Listas de exercícios serão atribuídas ao longo do semestre.

Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e será assumido como parte da matéria coberta.

Como as listas não farão parte da avaliação, suas soluções não serão coletadas.

Os alunos são encorajados a resolver todos os exercícios individualmente e, só posteriormente, realizar discussão em grupo.

Quaisquer dificuldades devem ser prontamente discutidas com o professor nos horários de atendimentos. Dúvidas não sanadas geram mais dúvidas.

Números entre colchetes indicam os respectivos livros listados nas Referências Bibliográficas.

Introdução à Análise de Algoritmos:
- [4] 1.1-3, 1.2-1, 1.2-2
Indução Matemática:
- [1] 2.1, 2.3, 2.12, 2.18, 2.26
Complexidade de Algoritmos:
- [4] 2.1-1, 2.1-2, 2.1-4
Relações de Recorrência:
- [4] 4.1-1, 4.1-2, 4.1-6, 4.2-1, 4.2-2, 4.2-3, 4.2-4, 4.2-5, 4.3-1, 4.3-2, 4.3-3
Construção de algoritmos por indução:
- [1] 5.5, 5.11, 5.12, 5.14, 5.15, 5.25a
Algoritmos de ordenação:
- [4] 7.1.1, 7.1-4, 7.1-5, 7.2-1, 7.2-3, 7.3-1, 7.4-1, 7.4-2 ([2] 6.4-3)
- [4] 8.1-1, 8.1-2, 8.2-1 ([2] 7.2-2), 8.2-2 ([2] 7.3-2), 8.3-2, 8.4-4 ([2] 7.4-5)
Limite inferior para ordenação e ordenação em tempo linear:
- [4] 9.1-1, 9.2-1, 9.2-2, 9.2-3, 9.2-5 ([2] 8.2-4), 9.3-4, 9.4-1 ([2] 8.4-2), 9.4-2 ([2] 8.4-3)
Estatística de ordem:
- [4] 10.1-1, 10.3-1, 10-3.3, 10.3-5, 10.3-8
Programação Dinâmica:
- [4] 16.1-2 ([2] 15.2-2), 16.3-2 ([2] 15.4-2), 16.3-3 ([2] 15.4-3), 16.3-4 ([2] 15.4-4), 16.3-5 ([2] 15.4-5), 16-3 ([2] 15-3)
Algoritmos Gulosos:
- [4] 17.1-3 ([2] 16.1-4), 17.2-4, 17.2-5, 17.3-2, 17.3-7, 17-1
Algoritmos elementares em grafos:
- [4] 23.1-1, 23.1-5, 23.1-6, 23.2-2, 23.2-3, 23.2-6, 23.3-9 ([2] 22.3-11), 23.4-3, 23.4-5, 23.5-1
Árvore geradora mínima:
- [4] 24.1-1, 24.1-5, 24.2-2, 24.2-3, 24.2-4, 24.2-5, 24.2-8 ([2] 23.2-7)
Estruturas de dados para conjuntos disjuntos:
- [4] 22.1-3, 22.2-2, 22.3-2, 22.3-3
Caminhos Mínimos:
- [4] 25.2-2 ([2] 24.3-2), 25.2-3 ([2] 24.3-3), 25.2-4 ([2] 24.3-4), 25.2-5 ([2] 24.3-6), 25.2-6 ([2] 24.3-7), 25.3-3 ([2] 24.1-3), 25.3-4 ([2] 24.1-4), 25.4-3 ([2] 24.2-3)
Todos Caminhos Mínimos:
- [4] 26.2-5 ([2] 25.2-6), 26-1

Listas Complementares

Avaliação

Haverá três provas (P1, P2, P3) nas datas indicadas ao final deste documento.
Cada prova será em classe e terá duração de 120 minutos.
A média final será a média ponderada de P1, P2 e P3 com pesos iguais a 2, 3 e 4, respectivamente.
Não serão ministradas provas antecipadas nem substitutivas.

Aviso: Qualquer tentativa de cola ou fraude, detetada durante uma prova ou posteriormente, acarretará nota zero naquela prova para todos os implicados, além das sansões regimentais, a critério do docente.

Tópicos Selecionados para o Exame