Segundas (sala IC-85 do IC2) e quartas (sala 301 do IC3) das 19h às 21h.
Dia, Horário e Local de Atendimento
Quartas-feiras, das 18:00h às 19:00h, na sala 23 (IC-1).
Importante: não haverá atendimento em semana de prova. O horário de atendimento será cancelado caso não haja procura até às 11:30h.
Ementa:
A ementa cobrirá tópicos selecionados em Teoria da Computação. Tópicos previstos:
Estruturas de Dados Avançados
Hash
Árvores Binárias Balanceadas (Rubro-Negras)
Estruturas de Dados Aumentantes
Árvores B
Heaps Binários
Heaps de Fibonacci
Conjuntos Disjuntos
Operações sobre Matrizes
Polinômios e Transformada Rápida de Fourier
Casamento de Caracteres
Geomeria Computacional
Tratamento de Problemas NP-Completos
Referências Bibliográficas
T. H. Cormen, C. E. Leiserson e R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
C. C. de Souza. Teoria da Complexidade: Notas de Aula. 2005.
C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc.,1982.
E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978.
M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, 1979.
P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. Universidade Federal de Pernambuco, Departamento de Informatica, 1994. IX Escola de Computação, Recife, 24 a 31 de julho de 1994.
M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
H. R. Lewis e C. H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição, 2000.
M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação Linear: modelos e algoritmos. Editora Campus, 2000.
N. Ziviani. Projeto de Algoritmos com implementações em Pascal e C. 2a edição. Thomson, 2003.
A. Aho, J. Hopcroft e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
D. E. Knuth, The Art of Computer Programming, vol. I: Fundamental Algorithms Addison-Wesley, 1997.
A avaliação será baseada nas notas de duas provas, uma aula e de listas de exercícios denotadas respectivamente por P1, P2, A e L.
Haverá, no mínimo, um intervalo de 5 dias entre a divulgação da lista e a data de entrega (que será sempre num dia de aula). As listas deverão ser entregues no começo da aula. Não serão aceitas listas entregues fora do prazo (tolerância máxima de 30 minutos). Apesar de discussões em grupo serem incentivadas nesta disciplina, a redação das respostas das listas deverá ser feita individualmente. Só serão aceitas listas escritas a mão, com letra legível. As listas poderão ser entregues incompletas, mas cada exercício entregue deve estar completamente resolvido. O número de listas de exercícios durante o curso, assim como o número de exercícios por lista, deverá variar entre 5 e 15. Serão atribuidas notas as listas de exercícios. Idealmente todos os exercícios serão corrigidos. Na praticamente, a critério exclusivo do docente, poderão ser utilizados outras formas para atribuir notas as listas, por exemplo:
Atribuição de nota máxima para quem entregou e zero para quem não entregou.
Atribuição de uma nota proporcional ao numero de exercícios entregues.
Correção de um (ou mais) exercícios escolhido(s) aleatoriamente. Neste caso o mesmo sub-conjunto de exercícios será considerado para todos os alunos. Caso o exercício escolhido não tiver sido entregue será atribuida nota zero.
Uma combinação destes ou de outros métodos.
A nota L será calculada como a média aritmética simples entre todas as listas de exercícios do semestre.
Cada aluno regularmente matriculado na disciplina ministrará uma aula sobre um dos tópicos relacionados a Estruturas de Dados Avançadas (ver Ementa). Os tópicos serão sorteados. Cada aula terá 1:40h de duração. O responnsável pela aula deverá preparar um material didático (slides) usando Beamer/Latex (veja o modelo). O material didático deverá ser entregue para o professor uma semana antes data prevista para a aula para correção e sugestões de melhorias. A avaliação da aula será baseada na aula em si (50%) e no material didático preparado (30% para a versão inicial e 20% para a versão final).
A média do semestre M será calculada pela fórmula:
M = (L + 3*P1 + 4*P2 + 2*A)/10
O exame final E será aberto para todos alunos. Caso o aluno entregue o exame, sua nota final será: MF = (M + E)/2
Caso o aluno não faça o exame ou não entregue-o, sua nota final será: MF = M
O conceito final será atribuído da seguinte forma:
A: se MF ≥ 8.5
B: se 7.0 ≤ MF < 8.5
C: se 5.0 ≤ MF < 7.0
D: se MF < 5.0
Observações:
Não haverá provas substitutivas.
As provas serão realizados sem consulta.
Qualquer tentativa de fraude nas provas, na aula ou nas listas de exercícios implicará em média final (MF) do semestre ZERO para todos os envolvidos, sem prejuízo de outras sansões.
Não será cobrada presença em sala de aula. Todos os alunos receberão 100% de presença, independente do conceito final obtido (não será atribuido o conceito “Reprovado por Falta” em nenhum caso).
01/08/2007: Prova 0 (sobre os pré-requisitos da disciplina)
29/08/2007: Não haverá aula
26/09/2007: Prova 1
19/11/2007: Não haverá aula
28/11/2007: Prova 2
10/12/2007: Exame
Observações:
Visite a página do Calendário oficial da DAC para saber quais as datas de alteração de matrícula, de trancamento de disciplinas e dos períodos sem atividade.
Todas as notas serão divulgadas em até uma semana após as datas das provas e da entrega das listas de exercícios.