Segundas e quartas, das 14h às 16h, na sala 322 do IC-3.
Dia, Horário e Local de Atendimento
Segundas-feiras, das 16h às 17h, na sala 23 (IC-1).
Importante: não haverá atendimento em semana de prova. O horário de atendimento será encerrado caso não haja procura até às 16:30h.
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, R.L. Rivest e C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition (2009)
U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley (1989)
C. C. de Souza. Teoria da Complexidade: Notas de Aula (2005)
N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. Thomson, 3a edição (2010)
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. IX Escola de Computação, Universidade Federal de Pernambuco. Departamento de Informatica (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)
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
Transparências utilizadas nas aulas (4 slides por página):
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 de uma lista de exercícios e a data de sua 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 prática, 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 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 + 3*P1 + 3*P2 + 3*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.
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é duas semanas após as datas das provas e das entregas das listas de exercícios.