[28/11/2008] Divulgados os conceitos finais, já considerando as notas da décima lista de exercícios e da terceira prova. Observações:
A coluna “Critério 1” representa a média final ponderada considerando pesos 1, 3, 3 e 3, para, respectivamente, a média das listas de exercícios, a P1, a P2 e a P3 (critério original da disciplina). Neste caso, as notas das provas foram obtidas através da média simples das questões de cada prova.
A coluna “Critério 2” considera médias ponderadas para as questões da P2 e P3, sendo atribuidos pesos 3.0, 2.5, 2.0, 1.5 e 1.0, respectivamente, para a questão de maior nota, a segunda maior e assim por diante. Para o cálculo da média final, neste caso, foi considerado a média simples entre a média das listas de exercícos, a P1, a P2 e a P3.
O conceito final foi atribuído levando em consideração o máximo entre estes dois critérios de nota.
[13/11/2008] Avisos importantes sobre a última prova:
Haverá um atendimento extra na sexta-feira, dia 14/11/2008, das 9h às 10h, para dúvidas sobre a matéria relativa à décima lista de exercícios.
A prova final (P3), será realizada no dia 18/11/2008, terça-feira, das 14h às 17h.
As notas da P3, da décima lista de exercícios, bem como os conceitos finais da disciplina serão divulgados até o final do mês de novembro.
A revisão da prova será realizada somente no dia 01/12/2008, na sala 23 do IC-2, das 10h às 11h.
[11/09/2008] Excepcionalmente, na próxima segunda-feira, dia 15/09/2008, o horário de atendimento será alterado para das 9 às 10h da manhã, em virtude do Forum da Pós-Graduação, que ocorrerá neste mesmo dia, das 10 às 12h, em local a ser confirmado pela CPG.
Segundas-feiras, das 17:30h às 18:30h, na sala 23 (IC-1).
Importante: não haverá atendimento em semana de prova.
Ementa:
Modelos de computação e ferramentas/notação para análise de algoritmos.
Indução matemática e projeto de algoritmos.
Algoritmos gulosos.
Programação dinâmica.
Divisão e conquista.
Algoritmos para ordenação e seleção.
Algoritmos para problemas básicos em grafos.
Reduções e NP-completude.
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.
Material Didático
Trasparências sobre NP-Completude (formato ps e pdf), elaboradas pelo professor Cid Carvalo de Souza [3].
Observação: Até meio ponto extra será computado em cada uma das provas, de acordo com média das listas específicas de cada prova. Para o cálculo desta média serão usadas as seguintes listas:
P1: L1, L2, L3, L4 e L5
P2: L6, L7, L8 e L9
P3: L10, L11, L12 e L13
Avaliação
A avaliação será baseada nas notas de três provas e de listas de exercícios denotadas respectivamente por P1, P2, P3 e E.
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 atribuídas 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.
Atrinuição de uma nota proporcional ao número 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 E será calculada como a média aritmética simples entre todas as listas de exercícios do semestre.
A média do semestre M será calculada da seguinte forma:
M=(1*E+2*P1+3*P2+4*P3)/10
O conceito final será atribuído da seguinte forma:
A: se M ≥ 8.5
B: se 7.0 ≤ M < 8.5
C: se 5.0 ≤ M < 7.0
D: se M < 5.0
Observações:
Não haverá provas substitutivas.
Todas as provas serão realizados sem consulta.
Qualquer tentativa de fraude nas provas ou nas listas de exercícios implicará em média do semestre ZERO para todos os envolvidos, sem prejuízo de outras sançõ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).
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.