Professor responsável

Paulo Fonseca paulofonseca at cin.ufpe.br

Horário & sala

  • Segunda-feira 13h00 - 15h00 (Sala D003)
  • Sexta-feira 15h00 - 17h00 (Sala D003)

Monitores

  • Caio Lima (ccal)
  • Duhan Caraciolo (dcms2)
  • Gustavo Oliveira (gof)
  • Lucas Maggi (lom)
  • Marvson Allan (mapa)
  • Roberto Fernandes (rcf6)

Ementa

  • Conceitos básicos de algoritmos e estruturas de dados (ED)
  • Revisão de ED básicas:
    • ED estáticas (arrays)
    • ED dinâmicas 1-D (listas encadeadas, filas e pilhas)
  • Introdução à análise de algoritmos e complexidade assintótica
  • Busca e ordenação em ED lineares
    • busca linear vs. busca binária
    • Mergesort (Dividir para conquistar - D&Q)
    • Quicksort
  • Tabelas de dispersão (Hash tables)
  • ED dinâmicas N-D: Árvores binárias
  • Busca/ordenação em ED N-D
    • árvores binárias de busca
    • Heaps e Heapsort
  • ED para relações de equivalência: union-find
  • Grafos
    • Grafos dirigidos vs. não-dirigidos
    • Percursos em grafos e aplicações (ordenação topológica, caminhos mais curtos)
    • Grafos ponderados
    • Algoritmos gulosos para problemas de otimização em grafos:
      • Caminhos mínimos com origem comum: Algoritmo de Bellman-Ford, Algoritmo de Dijkstra
      • Árvores geradoras mínimas: Algoritmo de Prim, Algoritmo de Kruskal
  • NP-completude
    • P vs. NP
    • Redução polinomial e NP-completude
    • Heurísticas para problemas NP-C
      • Backtracking
      • Branch&bound
      • Programação dinâmica

Bibliografia de referência

  1. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algoritmos. McGraw Hill, 2009 link
  2. Clifford Shaffer. Data Structures and Algorithm Analysis . Dover Publications, 2013 link
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. MIT Press, 2009. link (Também disponível em versão traduzida link) - CLRS
Links para material suplementar serão fornecidos ao longo do curso.

Avaliação

A avaliação será feita em duas unidades. A média do curso (MC) será calculada como

MC = (M1+M2) / 2

onde:

  • M1 = Média da 1a. Unidade
  • M2 = Média da 2a. Unidade

Em cada unidade a média será constituída por:

  • Listas de exercícios - 30% da nota da unidade
  • Teste prático - 20% da nota da unidade
  • Prova escrita - 50% da nota da unidade.

Por exemplo, se 2 listas de exercícios na 1a. unidade, então

M1 = ((L1 + L2)/2) * 0.3 + T1 * 0.2 + P1 * 0.5,

onde:

  • L1,2 = Nota da Lista 1, 2
  • T1 = Nota do teste da unidade 1
  • P1 = Nota da prova da unidade 1

Cada teste de unidade versará sobre o assunto da unidade até a aula imediatamente anterior.

Cada prova de unidade versará sobre o assunto de toda a unidade.

Segunda chamada

A prova de segunda chamada só poderá ser realizada mediante solicitação formal junto a secretaria e só será deferida se a falta for devidamente justificada com documentação apropriada, conforme a Resolução n° 04/1994 link to document.

A prova de segunda chamada versará sobre o assunto de todo o curso.

Prova final

Se MC >= 7, o aluno está aprovado por média.

Se MC < 3, o aluno está reprovado por média.

Se 3 <= MC < 7, o aluno deverá fazer uma prova final (PF).

A prova final versará sobre o assunto de todo o curso.

A média final será calculada como

MF = (MC + PF) / 2.

Se MF >= 5, o aluno está aprovado.

Se MF < 5, o aluno está reprovado.

IMPORTANTE: As provas serão discutidas posteriormente (em horário a ser definido) e os alunos poderão solicitar revisão. Entretanto, não há margem "extra" de tolerância quanto às médias.

Ética acadêmica

Os alunos devem fazer seus próprios trabalhos individualmente, compreender o que fizeram e ser capazes de explicar os seus raciocínios sem ajuda externa. é permitido discutir com os colegas sobre os problemas das listas de exercícios mas cada aluno deve escrever seus resultados nas suas próprias palavras indivudualmente.

é também permitido estudar código de terceiros, mas não é permitido copiar partes significativas destes e apresentar como se fosse trabalho pessoal. O plágio e a fraude acadêmica não contribuem para o processo educacional e não serão tolerados.

Frequência obrigatória

A frequência às atividades escolares é obrigatória, respeitados o turno e o horário previstos para a disciplina (conforme a Resolução n° 04/1994 link to document). Considera-se reprovado por falta, independentemente do aproveitamento escolar, o estudante que não tiver comprovado sua participação em pelo menos 75% (setenta e cinco por cento) das aulas, ou ao mesmo percentual de avaliações parciais de aproveitamento escolar.

Monitoria

Serão oferecidas, no contexto da discplina, aulas práticas e atividades de monitoria fora do horário de aula mencionado acima. Essas atividades têm caráter complementar e de reforço e a participação dos alunos é altamente recomendada. Entretanto, a participação nessas aulas é opcional e não contam para efeito de contabilização de frequência.

Observações importantes

  1. Esta página tem objetivo de facilitar a comunicação e a organização do curso e será feito esforço para manter a informação aqui contida correta e atualizada. Entretanto, o conteúdo desta página tem caráter fudamentalmente informativo e não-vinculativo, podendo ser modificado a qualquer altura à discrição do professor responsável no melhor interesse dos objetivos didáticos e acadêmicos, bem como da observância às regras instituicionais.
  2. Sobrepõem-se às informações aqui contidas qualquer comunicado em contrário emitido publicamente em sala de aula pelo professor responsável.
  3. Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com o professor responsável.
  4. Documentos de referência:
    • Regimento da UFPE link
    • Calendário acadêmico UFPE 2015 link to PDF
    • Resolução n° 04/1994 - Estabelece normas complementares de avaliação de aprendizagem e controle da frequência nos Cursos de Graduaçãolink to document
    • Manual acadêmico UFPE 2014 link to PDF

Inscreva-se já no canal oficial de comunicação entre alunos, professores e monitores da disciplina (apenas para alunos matriculados com e-mail do CIn)

Anúncios e novidades

  • 17 Mai: Página do curso no ar.